Сортировка пузырьком - это алгоритм сортировки, который производит сортировку путем перестановки двух соседних элементов массива.
История возникновения сортировки пузырьком
Существует 2 версии возникновения сортировки пузырьком:
- Изобретателем данного метода считается Джон Франклин Элдер, который изобрел сортировку пузырьком в 1956 году. Название "сортировки пузырьком" дал на основе аналогии с пузырьками воздуха в воде, которые поднимаются вверх.
- Во второй версии не указывается кто автор, однако бытует мнение, что в 1946 году данный метод сортировки применялся в машине IBM 405 для сортировки перфокарт.
Сложность сортировки пузырьком
Сложность сортировки пузырьком оценивается формулой O(n^2), где n - количество элементов массива.
Исходя из рисунка выше - можно сказать, что данный метод очень плох для сортировки массивов с большим количеством элементов.
Алгоритм сортировки пузырьком
Для начала необходимо загрузить массив данных А, после узнать его длину n. Если n<=1, то сортировка не свершится, в противном случае начинается процесс сортировки пузырьком. Создается двойной цикл, в котором совершается пошаговое сравнение всех элементов друг с другом и так до тех пор, пока не закончатся элементы. После происходит вывод массива А и программа должна закончить свою работу.
Ручной пример работы сортировки пузырьком
На рисунке выше представлен ручной просчет сортировки пузырьком. Было произведено 28 шагов, чтобы полностью отсортировать массив из 8 элементов.
Достоинства и недостатки сортировки пузырьком
К достоинством можно отнести следующее:
- Легко понять и реализовать.
- Эффективна для небольших массивов или уже отсортированных данных.
- Устойчива, то есть не меняет порядок равных элементов.
- Не требует дополнительной памяти.
К недостатка можно отнести следующее:
- Очень медленная, так как выполняет много лишних сравнений и обменов.
- Имеет квадратичную сложность времени выполнения.
- Неэффективна для больших объемов данных.