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

Анимация, показывающая пример работы алгоритма.

Наглядная демонстрация алгоритма.

Сортиро́вка пузырько́м (иногда встречается под названием «сортировка методом обмена» или «sinking sort») — простой алгоритм сортировки, основанный на попарном сравнении соседних элементов^[1]. Хотя он легко понимается и реализуется, практическая эффективность этого метода невысока, поэтому на практике его обычно заменяют более быстрыми алгоритмами, такими как сортировка слиянием или быстрая сортировка. Сортировка пузырьком часто рассматривается в образовательных целях как первая иллюстрация работы алгоритмов сортировки^[2].

Описание алгоритма

Принцип работы основывается на последовательных «проходах» по списку (или массиву). Во время каждого прохода алгоритм сравнивает две соседние позиции:

Если элемент слева больше (или, в зависимости от порядка сортировки, меньше) элемента справа, происходит обмен местами.
Проход продолжается, пока не будут проверены все пары соседних элементов.

После первого прохода самый большой элемент «всплывает» (англ. bubble up) в конец списка. На втором проходе то же самое происходит со вторым по величине элементом, и так далее. Для списка из $n$ элементов требуется не более $n-1$ прохода. Алгоритм завершается либо по достижении указанного числа проходов, либо раньше (если за прошедший цикл не было ни одного обмена, значит, список уже отсортирован)^[3].

Пример работы

Пусть имеется массив: 5 1 4 2 8. Требуется отсортировать его по возрастанию:

Сравниваем 5 и 1, меняем их (так как 5 > 1): получаем 1 5 4 2 8.
Сравниваем 5 и 4, меняем местами: 1 4 5 2 8.
Сравниваем 5 и 2, меняем местами: 1 4 2 5 8.
Сравниваем 5 и 8, не меняем (5 < 8): 1 4 2 5 8.

Теперь максимальный элемент (8) уже «всплыл» на нужную позицию (конец массива). Следующие проходы продолжаются с оставшимися элементами.

Псевдокод

Ниже приведён упрощённый вариант на языке, похожем на Pascal:

procedure bubbleSort(A : array of integer)
    n := length(A)
    repeat
        swapped := false
        for i := 1 to n - 1 do
            if A[i-1] > A[i] then
                swap(A[i-1], A[i])
                swapped := true
            end if
        end for
        // Если ни одного обмена не произошло, список отсортирован
    until not swapped
end procedure

При каждом проходе, если не было осуществлено ни одной перестановки, значит, массив отсортирован и алгоритм может завершиться досрочно^[2].

Сложность

В худшем и среднем случаях время работы — $O(n^{2})$ , где $n$ — число элементов^[1].
В лучшем случае (если массив уже отсортирован) алгоритму требуется всего один проход без обменов, то есть $O(n)$ сравнений.
По памяти сортировка пузырьком требует $O(1)$ дополнительного места, так как все операции идут «на месте».

При сравнении с другими методами сортировки (например, сортировка вставками или выбором) у пузырька обычно больше реальных затрат на каждую итерацию и, следовательно, больше общее время сортировки^[3]. Также современные процессоры менее эффективно обрабатывают такой метод, ведь при пузырьковой сортировке часто происходят непредсказуемые ветвления (branch misprediction) и больше операций записи в память.

Оптимизации

Можно сократить число проверок при каждом последующем проходе, так как после $k$ -го прохода последние $k$ элементов уже окажутся на своих местах.
Если в ходе прохода не было ни одного обмена, цикл прекращается досрочно.
Вариант сортировки под названием «Cocktail shaker sort» («коктейльная сортировка») идёт по массиву сначала слева направо, затем справа налево, что позволяет быстрее перемещать «мелкие» элементы к началу^[3].

Использование и критика

Сортировка пузырьком служит наглядным примером для начинающих программистов. Она хорошо иллюстрирует принципы работы алгоритмов на базе сравнительной сортировки. Однако в реальных задачах этот метод почти не применяется из-за низкой производительности. Дональд Кнут отмечал, что у пузырьковой сортировки нет серьёзных преимуществ, кроме простоты кода и наглядности процесса^[2].

Исследования показали, что даже другие простые алгоритмы с оценкой $O(n^{2})$ , такие как сортировка вставками, часто оказываются быстрее пузырька на практике^[3]. По этой причине некоторые преподаватели не рекомендуют тратить много времени на изучение пузырьковой сортировки и предпочитают использовать более эффективные и практически применимые примеры.

См. также

Примечания

↑ ^{Перейти обратно: 1,0} ^1,1 Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C. Introduction to Algorithms, 2nd ed. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7.
↑ ^{Перейти обратно: 2,0} ^2,1 ^2,2 Knuth, D. The Art of Computer Programming, Volume 3: Sorting and Searching. Addison-Wesley, 2nd ed., 1998.
↑ ^{Перейти обратно: 3,0} ^3,1 ^3,2 ^3,3 Bubble sort: an archaeological algorithmic analysis (неопр.). Duke University. Дата обращения: 4 февраля 2025.

[Cormen-1] {Перейти обратно: 1,0} ^1,1 Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C. Introduction to Algorithms, 2nd ed. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7.

[Knuth-2] {Перейти обратно: 2,0} ^2,1 ^2,2 Knuth, D. The Art of Computer Programming, Volume 3: Sorting and Searching. Addison-Wesley, 2nd ed., 1998.

[Astrachan-3] {Перейти обратно: 3,0} ^3,1 ^3,2 ^3,3 Bubble sort: an archaeological algorithmic analysis (неопр.). Duke University. Дата обращения: 4 февраля 2025.

[1]

[2]

[3]