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

Материал из Циклопедии
Перейти к навигации Перейти к поиску
Файл:Bubble sort animation.gif
Наглядная демонстрация алгоритма.

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

Хотя он легко понимается и реализуется, практическая эффективность этого метода невысока, поэтому на практике его обычно заменяют более быстрыми алгоритмами, такими как сортировка слиянием или быстрая сортировка. Сортировка пузырьком часто рассматривается в образовательных целях как первая иллюстрация работы алгоритмов сортировки[2].

Описание алгоритма[править]

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

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

После первого прохода самый большой элемент «всплывает» (англ. bubble up) в конец списка. На втором проходе то же самое происходит со вторым по величине элементом, и так далее. Для списка из Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle n } элементов требуется не более Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle 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: <syntaxhighlight lang="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 </syntaxhighlight> При каждом проходе, если не было осуществлено ни одной перестановки, значит, массив отсортирован и алгоритм может завершиться досрочно[2].

Сложность[править]

  • В худшем и среднем случаях время работы — Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle O(n^2) } , где Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle n }  — число элементов[1].
  • В лучшем случае (если массив уже отсортирован) алгоритму требуется всего один проход без обменов, то есть Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle O(n)} сравнений.
  • По памяти сортировка пузырьком требует Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle O(1) } дополнительного места, так как все операции идут «на месте».

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

Оптимизации[править]

  • Можно сократить число проверок при каждом последующем проходе, так как после Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle k} -го прохода последние Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle k} элементов уже окажутся на своих местах.
  • Если в ходе прохода не было ни одного обмена, цикл прекращается досрочно.
  • Вариант сортировки под названием «Cocktail shaker sort» («коктейльная сортировка») идёт по массиву сначала слева направо, затем справа налево, что позволяет быстрее перемещать «мелкие» элементы к началу[3].

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

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

Исследования показали, что даже другие простые алгоритмы с оценкой Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle O(n^2)} , такие как сортировка вставками, часто оказываются быстрее пузырька на практике[3]. По этой причине некоторые преподаватели не рекомендуют тратить много времени на изучение пузырьковой сортировки и предпочитают использовать более эффективные и практически применимые примеры.

См. также[править]

Примечания[править]

  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.
  2. ↑ 2,0 2,1 2,2 Knuth, D. The Art of Computer Programming, Volume 3: Sorting and Searching. Addison-Wesley, 2nd ed., 1998.
  3. ↑ 3,0 3,1 3,2 3,3 Bubble sort: an archaeological algorithmic analysis. Duke University. Проверено 4 февраля 2025.
Знание.Вики

Одним из источников, использованных при создании данной статьи, является статья из википроекта «Знание.Вики» («znanierussia.ru») под названием «Сортировка пузырьком», расположенная по следующим адресам:

—«https://baza.znanierussia.ru/mediawiki/index.php/Сортировка_пузырьком»
—«https://znanierussia.ru/articles/Сортировка_пузырьком»

Материал указанной статьи полностью или частично использован в Циклопедии по лицензии CC-BY-SA 4.0 и более поздних версий.

Всем участникам Знание.Вики предлагается прочитать материал «Почему Циклопедия?».

Источник — http://cyclowiki.org/w/index.php?title=Сортировка_пузырьком&oldid=2244276