Сортировка пузырьком , иногда называемая сортировкой с погружением , представляет собой простой алгоритм сортировки , который многократно проходит по входному списку элемент за элементом, сравнивая текущий элемент с тем, который следует за ним, меняя их значения при необходимости. Эти проходы по списку повторяются до тех пор, пока не останется необходимости в выполнении обменов во время прохода, что означает, что список стал полностью отсортированным. Алгоритм, который является сортировкой сравнений , назван так из-за способа, которым более крупные элементы «всплывают» наверх списка.
Этот простой алгоритм плохо работает в реальном мире и используется в основном как образовательный инструмент. Более эффективные алгоритмы, такие как быстрая сортировка , сортировка по времени или сортировка слиянием, используются библиотеками сортировки, встроенными в популярные языки программирования, такие как Python и Java. [2] [3] Однако, если параллельная обработка разрешена, пузырьковая сортировка сортируется за время O(n), что делает ее значительно быстрее параллельных реализаций сортировки вставкой или сортировки выбором, которые не так эффективно распараллеливаются. [ требуется ссылка ]
Самое раннее описание алгоритма пузырьковой сортировки было в статье 1956 года математика и актуария Эдварда Гарри Френда [4] Сортировка в электронных компьютерных системах [5] , опубликованной в третьем выпуске третьего тома журнала Ассоциации вычислительной техники (ACM), как «Алгоритм сортировочного обмена». Френд описал основы алгоритма, и, хотя изначально его статья осталась незамеченной, несколько лет спустя он был заново открыт многими компьютерными учеными, включая Кеннета Э. Айверсона , который и придумал его нынешнее название.
Сортировка пузырьком имеет наихудшую и среднюю сложность , где — количество сортируемых элементов. Большинство практических алгоритмов сортировки имеют существенно лучшую наихудшую или среднюю сложность, часто . Даже другие алгоритмы сортировки, такие как сортировка вставкой , обычно работают быстрее, чем сортировка пузырьком, и не сложнее. По этой причине сортировка пузырьком редко используется на практике.
Как и сортировка вставкой , пузырьковая сортировка адаптивна , что может дать ей преимущество перед такими алгоритмами, как быстрая сортировка . Это означает, что она может превзойти эти алгоритмы в случаях, когда список уже в основном отсортирован (имеет небольшое количество инверсий ), несмотря на то, что у нее худшая средняя временная сложность. Например, пузырьковая сортировка выполняется для списка, который уже отсортирован, в то время как быстрая сортировка все равно выполнит весь свой процесс сортировки.
В то время как любой алгоритм сортировки можно реализовать на предварительно отсортированном списке, просто проверив список перед запуском алгоритма, улучшенную производительность на почти отсортированных списках воспроизвести сложнее.
Расстояние и направление, на которые должны перемещаться элементы во время сортировки, определяют производительность пузырьковой сортировки, поскольку элементы перемещаются в разных направлениях с разной скоростью. Элемент, который должен перемещаться к концу списка, может перемещаться быстро, поскольку он может принимать участие в последовательных обменах. Например, самый большой элемент в списке будет выигрывать каждый обмен, поэтому он перемещается в свою отсортированную позицию на первом проходе, даже если он начинается недалеко от начала. С другой стороны, элемент, который должен перемещаться к началу списка, не может перемещаться быстрее одного шага за проход, поэтому элементы перемещаются к началу очень медленно. Если самый маленький элемент находится в конце списка, потребуется несколько проходов, чтобы переместить его в начало. Это привело к тому, что эти типы элементов были названы кроликами и черепахами соответственно в честь персонажей басни Эзопа « Черепаха и заяц» .
Были предприняты различные попытки устранить черепах, чтобы улучшить скорость пузырьковой сортировки. Коктейльная сортировка — это двунаправленная пузырьковая сортировка, которая идет от начала к концу, а затем разворачивается, переходя от конца к началу. Она может довольно хорошо перемещать черепах, но сохраняет сложность наихудшего случая. Сортировка гребнем сравнивает элементы, разделенные большими промежутками, и может перемещать черепах чрезвычайно быстро, прежде чем перейти к меньшим и меньшим промежуткам, чтобы сгладить список. Ее средняя скорость сопоставима с более быстрыми алгоритмами, такими как быстрая сортировка .
Возьмите массив чисел "5 1 4 2 8" и отсортируйте массив от наименьшего числа к наибольшему с помощью пузырьковой сортировки. На каждом шаге сравниваются элементы, выделенные жирным шрифтом . Потребуется три прохода;
Теперь массив уже отсортирован, но алгоритм не знает, завершен ли он. Алгоритму нужен еще один полный проход без какого-либо обмена, чтобы узнать, что он отсортирован.
В псевдокоде алгоритм можно выразить как (массив с отсчетом от 0):
procedure bubbleSort ( A : список сортируемых элементов ) n := length ( A ) repeat swapped := false for i : = 1 to n - 1 inclusive do { if эта пара не упорядочена } if A [ i - 1 ] > A [ i ] then { поменять их местами и запомнить, что что-то изменилось } swap ( A [ i - 1 ] , A [ i ]) swapped := true end if end for until not swapped end procedure Алгоритм пузырьковой сортировки можно оптимизировать, наблюдая, что n -й проход находит n -й наибольший элемент и помещает его на свое последнее место. Таким образом, внутренний цикл может избежать просмотра последних n − 1 элементов при запуске в n -й раз:
procedure bubbleSort ( A : список сортируемых элементов ) n := length ( A ) repeat swapped := false for i := 1 to n - 1 inclusive do if A [ i - 1 ] > A [ i ] then swap ( A [ i - 1 ] , A [ i ]) swapped : = true end if end for n := n - 1 until not swapped end procedure В более общем случае может случиться, что более одного элемента помещаются в их конечную позицию за один проход. В частности, после каждого прохода все элементы после последнего обмена сортируются и не нуждаются в повторной проверке. Это позволяет нам пропускать много элементов, что приводит к улучшению примерно на 50% количества сравнений в худшем случае (хотя улучшения количества обменов нет), и добавляет очень мало сложности, поскольку новый код включает в себя «переставленную» переменную:
Чтобы сделать это в псевдокоде, можно написать следующее:
procedure bubbleSort ( A : список сортируемых элементов ) n := length ( A ) repeat newn := 0 for i := 1 to n - 1 inclusive do if A [ i - 1 ] > A [ i ] then swap ( A [ i - 1 ] , A [ i ]) newn := i end if end for n : = newn until n ≤ 1 end procedure Альтернативные модификации, такие как сортировка с помощью шейкера, пытаются улучшить производительность пузырьковой сортировки, сохраняя при этом ту же идею многократного сравнения и перестановки соседних элементов.
Хотя сортировка пузырьком является одним из самых простых алгоритмов сортировки для понимания и реализации, его сложность O ( n 2 ) означает, что его эффективность резко снижается в списках, содержащих больше, чем небольшое количество элементов. Даже среди простых алгоритмов сортировки O ( n 2 ) такие алгоритмы, как сортировка вставкой, обычно значительно эффективнее.
Благодаря своей простоте, пузырьковая сортировка часто используется для введения концепции алгоритма или алгоритма сортировки для студентов, изучающих компьютерные науки . Однако некоторые исследователи, такие как Оуэн Астрахан, приложили немало усилий, чтобы очернить пузырьковую сортировку и ее постоянную популярность в образовании в области компьютерных наук, рекомендуя даже не преподавать ее. [6]
Jargon File , который, как известно, называет bogosort «архетипичным [sic] извращенно ужасным алгоритмом», также называет пузырьковую сортировку «плохим обобщенным алгоритмом». [7] Дональд Кнут в своей книге «Искусство программирования » пришел к выводу, что «пузырьковая сортировка, похоже, не имеет ничего, что заслуживало бы ее рекомендовать, кроме броского названия и того факта, что она приводит к некоторым интересным теоретическим проблемам», некоторые из которых он затем обсуждает. [8]
Сортировка пузырьком асимптотически эквивалентна по времени выполнения сортировке вставкой в худшем случае, но эти два алгоритма сильно различаются по количеству необходимых перестановок. Экспериментальные результаты, такие как результаты Астрахана, также показали, что сортировка вставкой работает значительно лучше даже на случайных списках. По этим причинам многие современные учебники по алгоритмам избегают использования алгоритма сортировки пузырьком в пользу сортировки вставкой.
Пузырьковая сортировка также плохо взаимодействует с современным оборудованием ЦП. Она производит как минимум вдвое больше записей, чем сортировка вставкой, вдвое больше промахов кэша и асимптотически больше неверных предсказаний ветвлений . [ требуется цитата ] Эксперименты Астрахана по сортировке строк в Java показывают, что пузырьковая сортировка примерно в пять раз быстрее сортировки вставкой и на 70% быстрее сортировки выбором . [6]
В компьютерной графике пузырьковая сортировка популярна из-за своей способности обнаруживать очень маленькую ошибку (например, перестановку всего двух элементов) в почти отсортированных массивах и исправлять ее с помощью линейной сложности (2 n ). Например, она используется в алгоритме заполнения многоугольника, где ограничивающие линии сортируются по своей координате x на определенной строке сканирования (линия, параллельная оси x ), а с увеличением y их порядок меняется (два элемента меняются местами) только на пересечениях двух линий. Пузырьковая сортировка — это устойчивый алгоритм сортировки, как и сортировка вставкой.
Пузырьковую сортировку иногда называют «тонущей сортировкой». [9]
Например, Дональд Кнут описывает вставку значений в желаемое место или по направлению к нему как возможность «[значению] установиться на надлежащем уровне», и что «этот метод сортировки иногда называют методом просеивания или погружения ». [10]
Этот спор поддерживается той легкостью, с которой можно рассматривать этот алгоритм с двух разных, но одинаково обоснованных точек зрения:
В интервью 2007 года бывший генеральный директор Google Эрик Шмидт спросил тогдашнего кандидата в президенты Барака Обаму о лучшем способе сортировки миллиона целых чисел ; Обама на мгновение задумался и ответил: «Я думаю, что пузырьковая сортировка — это неправильный способ». [11] [12]
{{cite AV media}}: CS1 maint: местоположение ( ссылка )
