Сортировка массива методом пузырька - алгоритм и задачи

Общая характеристика

Сортировка — упорядочение списка объектов. Выделяют 2 основных типа. Если количество объектов достаточно мало для размещения в основной памяти, она называется внутренней. Внешняя — число данных настолько велико, что некоторые находятся во внешнем хранилище.

Примеры алгоритмов сортировки:

• блочная;
• пузырьковая;
• пирамидальная;
• вставками;
• выбором;
• слиянием.

Все они имеют общую цель — вывести отсортированный список или массив, но способ, которым каждый выполняет эту задачу, отличается. При работе с любым типом важно знать, насколько быстро он работает и какое количество памяти использует, другими словами, его сложность, пространственную и временную.

Сложность алгоритмов

Тему сложности алгоритмов часто трудно понять многим программистам и студентам, они стараются пропускать ее. На сам деле она довольна проста. Сложность — это способ измерения того, как быстро работает программа.

Время выполнения описывает, сколько операций должен выполнить алгоритм до его завершения. Пространственная сложность — сколько места должно быть выделено для запуска. Например, если алгоритм принимает список размером n и по какой-то причине создает новый с таким же для каждого элемента в n, то требуется пространство n² . Кроме того, иногда полезно знать устойчивость выполнения. Алгоритм стабилен, если он сохраняет исходный порядок элементов с одинаковыми значениями.

Таблица сложности алгоритмов:

* Большинство реализаций быстрой сортировки не стабильны, хотя они существуют.

При выборе используемого алгоритма нужно взвесить эти факторы. Например, быстрая является очень шустрой, но ее может быть довольно сложно реализовать. Пузырьковая сортировка — медленный алгоритм, но его очень легко сделать. Для небольших наборов данных может быть лучше использовать вторую, поскольку она может быть реализована не так трудно, но для больших стоит использовать быструю.

Сортировка пузырьком

Этот метод, вероятно, является первым достаточно сложным модулем, который должен написать любой начинающий программист. Это очень простая конструкция, которая знакомит учащихся с основами работы алгоритмов.

Пузырьковая (обменная) использует двумерный или одномерный массив и механизм обмена. Большинство языков программирования имеют встроенную функцию для перестановки элементов. Даже если функция обмена не существует, требуется всего пара дополнительных строк кода. Вместо перебора массива, пузырьковая работает по схеме сравнения соседних пар объектов. Шаги:

1. Если элементы расположены не в правильном порядке, они меняются местами так, что самый большой из двух перемещается вверх. Этот процесс продолжается до тех пор, пока самый большой из объектов, не окажется на первом месте.
2. После этого начинается поиск следующего по величине элемента.
3. Перестановка остановится, когда весь массив окажется в правильном порядке.

Сортировка пузырьком на Pascal (Паскаль):

Сортировка массива методом пузырька на Python (Питон):

На Java:

Из-за своей простоты этот метод часто используется для представления концепции алгоритма сортировки. В компьютерной графике она популярна благодаря своей способности выявлять очень маленькую ошибку (например, перестановку всего двух элементов) в почти отсортированных массивах и исправлять ее с помощью линейной сложности.

Также используется в алгоритме заполнения полигонов, где ограничивающие линии сортируются по их координате «x» на конкретной сканирующей прямой (параллельной оси абсцисс), а с увеличением «y» их порядок изменяется только на пересечениях двух контурах.

Какой способ обработки данных выбрать, специалист решает сам, в зависимости от времени и объема информации.