Пузырьковая сортировка

Простой алгоритм сортировки сравнением

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

Этот простой алгоритм плохо работает в реальных условиях и используется в основном в качестве образовательного инструмента. Более эффективные алгоритмы, такие как быстрая сортировка , тимсортировка или сортировка слиянием, используются библиотеками сортировки, встроенными в популярные языки программирования, такие как Python и Java. Однако, если параллельная обработка разрешена, пузырьковая сортировка выполняется за время O(n), что делает ее значительно быстрее, чем параллельные реализации сортировки вставками или сортировки выбором, которые не распараллеливаются так эффективно. ^{[2] [3]}

История

Самое раннее описание алгоритма пузырьковой сортировки было в статье 1956 года математика и актуария Эдварда Гарри Френда, ^[4] Сортировка в электронных компьютерных системах , ^[5], опубликованной в третьем выпуске третьего тома Журнала Ассоциации компьютерных вычислений. Machinery (ACM), как «алгоритм сортирующего обмена». Френд описал основы алгоритма, и, хотя первоначально его статья осталась незамеченной, несколько лет спустя она была заново открыта многими учеными-компьютерщиками, включая Кеннета Э. Айверсона , который придумал его нынешнее название.

Анализ

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

Производительность

Пузырьковая сортировка имеет наихудшую и среднюю сложность , где — количество сортируемых элементов. Большинство практических алгоритмов сортировки имеют значительно лучшую сложность в наихудшем или среднем случае, часто . Даже другие алгоритмы сортировки, такие как сортировка вставками , обычно работают быстрее, чем пузырьковая сортировка, и не более сложны. По этой причине пузырьковая сортировка на практике используется редко. ${\displaystyle O(n^{2})}$ ${\displaystyle n}$ ${\displaystyle O(n\log n)}$ ${\displaystyle O(n^{2})}$

Как и сортировка вставками , пузырьковая сортировка является адаптивной , что дает ей преимущество перед такими алгоритмами, как быстрая сортировка . Это означает, что он может превзойти эти алгоритмы в тех случаях, когда список уже в основном отсортирован (имеет небольшое количество инверсий ), несмотря на то, что он имеет худшую временную сложность в среднем случае. Например, пузырьковая сортировка выполняется в уже отсортированном списке, а быстрая сортировка все равно будет выполнять весь процесс сортировки. ${\displaystyle O(n)}$ ${\displaystyle O(n\log n)}$

Хотя любой алгоритм сортировки можно реализовать на основе предварительно отсортированного списка, просто проверив его перед запуском алгоритма, повышение производительности на почти отсортированных списках труднее воспроизвести. ${\displaystyle O(n)}$

Кролики и черепахи

Расстояние и направление, в котором элементы должны двигаться во время сортировки, определяют производительность пузырьковой сортировки, поскольку элементы движутся в разных направлениях с разной скоростью. Элемент, который должен переместиться в конец списка, может перемещаться быстро, поскольку он может участвовать в последовательных заменах. Например, самый большой элемент в списке выиграет каждую замену, поэтому он перемещается на отсортированную позицию при первом проходе, даже если он начинается ближе к началу. С другой стороны, элемент, который должен двигаться к началу списка, не может двигаться быстрее, чем на один шаг за проход, поэтому элементы движутся к началу очень медленно. Если самый маленький элемент находится в конце списка, потребуется несколько проходов, чтобы переместить его в начало. Это привело к тому, что эти типы элементов были названы кроликами и черепахами соответственно в честь персонажей басни Эзопа « Черепаха и Заяц» . ${\displaystyle n-1}$

Были предприняты различные усилия по уничтожению черепах, чтобы повысить скорость сортировки пузырьков. Коктейльная сортировка — это двунаправленная пузырьковая сортировка, которая идет от начала до конца, а затем меняет направление, переходя от начала к началу. Он может довольно хорошо перемещать черепах, но сохраняет сложность наихудшего случая. Гребенчатая сортировка сравнивает элементы, разделенные большими промежутками, и может очень быстро перемещать черепах, прежде чем переходить к все меньшим и меньшим промежуткам, чтобы сгладить список. Его средняя скорость сравнима с более быстрыми алгоритмами, такими как быстрая сортировка . ${\displaystyle O(n^{2})}$

Пошаговый пример

Возьмите массив чисел «5 1 4 2 8» и отсортируйте его от наименьшего числа к наибольшему с помощью пузырьковой сортировки. На каждом этапе сравниваются элементы, выделенные жирным шрифтом . Потребуются три пропуска;

Первый проход

( 5 1 4 2 8 ) → ( 1 5 4 2 8 ). Здесь алгоритм сравнивает первые два элемента и меняет местами, поскольку 5 > 1.

( 1 5 4 2 8 ) → ( 1 4 5 2 8 ), Обмен с 5 > 4

( 1 4 5 2 8 ) → ( 1 4 2 5 8 ), Обмен с 5 > 2

( 1 4 2 5 8 ) → ( 1 4 2 5 8 ), Теперь, поскольку эти элементы уже в порядке (8 > 5), алгоритм не меняет их местами.

Второй проход

( 1 4 2 5 8 ) → ( 1 4 2 5 8 )

( 1 4 2 5 8 ) → ( 1 2 4 5 8 ), Обмен, так как 4 > 2

( 1 2 4 5 8 ) → ( 1 2 4 5 8 )

( 1 2 4 5 8 ) → ( 1 2 4 5 8 )

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

Третий проход

( 1 2 4 5 8 ) → ( 1 2 4 5 8 )

( 1 2 4 5 8 ) → ( 1 2 4 5 8 )

( 1 2 4 5 8 ) → ( 1 2 4 5 8 )

( 1 2 4 5 8 ) → ( 1 2 4 5 8 )

Выполнение

Реализация псевдокода

В псевдокоде алгоритм можно выразить как (массив с отсчетом от 0):

процедура bubbleSort ( A : список сортируемых элементов ) n := длина ( A ) повторение заменено := false for i := от 1 до n - 1 включительно do { если эта пара не в порядке } if A [ i - 1 ] > A [ i ] then { поменяйте их местами и запомните, что что-то изменилось } swap ( A [ i - 1 ] , A [ i ]) поменяно местами : = true end if end for до тех пор, пока не будет заменено завершение процедуры                                         

Оптимизация пузырьковой сортировки

Алгоритм пузырьковой сортировки можно оптимизировать, заметив, что n -й проход находит n -й по величине элемент и помещает его на последнее место. Таким образом, внутренний цикл может избежать просмотра последних n - 1 элементов при запуске в n -й раз:

процедура bubbleSort ( A : список сортируемых элементов ) n := длина ( A ) повторение заменено := false for i := от 1 до n - 1 включительно do if A [ i - 1 ] > A [ i ] затем поменяйте местами ( A [ i - 1 ] , A [ i ]) заменено := true end if end for n := n - 1 до тех пор, пока не будет заменена процедура завершения                                                  

В более общем плане может случиться так, что за один проход в конечное положение будет помещено более одного элемента. В частности, после каждого прохода все элементы после последней замены сортируются и их не нужно проверять повторно. Это позволяет нам пропускать многие элементы, что приводит к увеличению числа сравнений в наихудшем случае примерно на 50 % (хотя и без улучшения количества подкачек), и добавляет очень мало сложности, поскольку новый код включает в себя «подкачанную» переменную:

Чтобы реализовать это в псевдокоде, можно написать следующее:

процедура bubbleSort ( A : список сортируемых элементов ) n := длина ( A ) повторение newn := 0 for i := от 1 до n - 1 включительно do if A [ i - 1 ] > A [ i ] затем поменяйте местами ( A [ i - 1 ] , A [ i ]) newn := i end if end for n := newn до n ≤ 1 завершить процедуру                                                 

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

Использовать

Пузырьковая сортировка. Список был построен в декартовой системе координат, где каждая точка ( x , y ) указывает на то, что значение y хранится по индексу x . Затем список будет отсортирован пузырьковой сортировкой в ​​соответствии со значением каждого пикселя. Обратите внимание, что сначала сортируется самый большой конец, а более мелким элементам требуется больше времени, чтобы переместиться в правильные позиции.

Хотя пузырьковая сортировка является одним из самых простых для понимания и реализации алгоритмов сортировки, ее сложность O ( n2 ) означает, что ее эффективность резко падает в списках ^, содержащих большое количество элементов. Даже среди простых алгоритмов сортировки O ( n ^{2 ) такие алгоритмы, как} сортировка вставками , обычно значительно более эффективны.

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

The Jargon File , в котором известно, что bogosort называется «архетипическим [sic] извращенно ужасным алгоритмом», также называется пузырьковая сортировка «обычным плохим алгоритмом». ^[7] Дональд Кнут в книге «Искусство компьютерного программирования» пришел к выводу, что «пузырьковая сортировка, похоже, не дает никаких рекомендаций, кроме запоминающегося названия и того факта, что она приводит к некоторым интересным теоретическим проблемам», некоторые из которых он затем обсуждает. . ^[8]

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

Пузырьковая сортировка также плохо взаимодействует с современным оборудованием ЦП. Он производит как минимум в два раза больше операций записи, чем сортировка вставкой, в два раза больше промахов в кэше и асимптотически больше ошибочных предсказаний ветвей . ^{[ Требуется цитирование ]} Эксперименты Астрахана по сортировке строк в Java показывают, что пузырьковая сортировка примерно на одну пятую быстрее сортировки вставкой и на 70% быстрее сортировки выбором . ^[6]

В компьютерной графике пузырьковая сортировка популярна благодаря своей способности обнаруживать очень небольшие ошибки (например, замену всего двух элементов) в почти отсортированных массивах и исправлять их с линейной сложностью (2 n ). Например, он используется в алгоритме заполнения полигонов, где ограничивающие линии сортируются по координате x в конкретной строке развертки (линии, параллельной оси x ) и с увеличением y их порядок меняется (два элемента меняются местами) только при пересечения двух прямых. Пузырьковая сортировка — это стабильный алгоритм сортировки, подобный сортировке вставками.

Вариации

• Сортировка «нечет-чет» — это параллельная версия пузырьковой сортировки для систем передачи сообщений.
• Проходы могут осуществляться справа налево, а не слева направо. Это более эффективно для списков с несортированными элементами, добавленными в конец.
• Сортировка шейкера попеременно проходит влево и вправо.

Споры по поводу названия

Пузырьковую сортировку иногда называют «тонущей сортировкой». ^[9]

Например, Дональд Кнут описывает вставку значений в желаемое место или по направлению к нему как возможность «[значению] установиться на надлежащий уровень» и что «этот метод сортировки иногда называют методом просеивания или погружения ». ^[10]

Эти дебаты увековечиваются из-за легкости, с которой можно рассматривать этот алгоритм с двух разных, но одинаково обоснованных точек зрения:

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

В популярной культуре

В интервью 2007 года бывший генеральный директор Google Эрик Шмидт спросил тогдашнего кандидата в президенты Барака Обаму о том, как лучше всего отсортировать миллион целых чисел ; Обама сделал паузу на мгновение и ответил: «Я думаю, что сортировка по пузырю была бы неправильным путем». ^{[11] [12]}

Примечания

1. Кортези, Альдо (27 апреля 2007 г.). «Визуализация алгоритмов сортировки» . Проверено 16 марта 2017 г.
2. «[JDK-6804124] (coll) Замените «модифицированную сортировку слиянием» в java.util.Arrays.sort на timsort — система ошибок Java». bugs.openjdk.java.net . Проверено 11 января 2020 г.
3. Питерс, Тим (20 июля 2002 г.). «[Python-Dev] Сортировка» . Проверено 11 января 2020 г.
4. «Некролог ЭДВАРДА ФРЕНДА (2019) - Вашингтон, округ Колумбия - The Washington Post» . Legacy.com .
5. Друг, Эдвард Х. (1956). «Сортировка на электронно-вычислительных системах». Журнал АКМ . 3 (3): 134–168. дои : 10.1145/320831.320833 . S2CID  16071355.
6. Астрачан, Оуэн (2003). «Пузырьковая сортировка: археологический алгоритмический анализ» (PDF) . Бюллетень ACM SIGCSE . 35 (1): 1–5. дои : 10.1145/792548.611918. ISSN  0097-8418.
7. «Жаргон, узел: бого-сортировка» . www.jargon.net .
8. Дональд Кнут . Искусство компьютерного программирования , Том 3: Сортировка и поиск , Второе издание. Аддисон-Уэсли, 1998. ISBN 0-201-89685-0 . Страницы 106–110 раздела 5.2.2: Сортировка по обмену. «[А]хотя методы, используемые в расчетах [для анализа пузырьковой сортировки], поучительны, результаты разочаровывают, поскольку они говорят нам, что пузырьковая сортировка на самом деле не очень хороша. По сравнению с прямой вставкой […], сортировка пузырьками требует более сложной программы и занимает примерно вдвое больше времени!» (Цитата из первого издания 1973 года.) 
9. Блэк, Пол Э. (24 августа 2009 г.). «пузырьковая сортировка». Словарь алгоритмов и структур данных . Национальный институт стандартов и технологий . Проверено 1 октября 2014 г.
10. Кнут, Дональд (1997). Искусство компьютерного программирования: Том 3: Поиск и сортировка . Аддисон-Уэсли. п. 80. ИСБН 0201896850.
11. Лай Стирланд, Сара (14 ноября 2007 г.). «Обама проходит собеседование в Google» . Проводной . Проверено 27 октября 2020 г.
12. Барак Обама, Эрик Шмидт (14 ноября 2007 г.). Барак Обама | Кандидаты в Google (Видео) (YouTube). Маунтин-Вью, Калифорния 94043 Googleplex: переговоры в Google. Событие происходит в 23:20. Архивировано из оригинала 7 сентября 2019 года . Проверено 18 сентября 2019 г.{{cite AV media}}: CS1 maint: location (link)

Рекомендации

• Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Стейн . Введение в алгоритмы , второе издание. MIT Press и McGraw-Hill, 2001. ISBN 0-262-03293-7 . Задача 2-2, стр.40. 
• Сортировка при наличии прогнозирования ветвей и кэшей
• Основы структур данных Эллиса Горовица, Сартаджа Сахни и Сьюзен Андерсон-Фрид ISBN 81-7371-605-6 
• Оуэн Астрахан . Пузырьковая сортировка: археологический алгоритмический анализ
• Компьютерно-интегрированное производство, доктор философии Спасик, магистр наук, открытый исходный код, 1987. [1]

Внешние ссылки

• Мартин, Дэвид Р. (2007). «Анимированные алгоритмы сортировки: пузырьковая сортировка». Архивировано из оригинала 3 марта 2015 г.– графическая демонстрация
• «Сортировка пузырьком Лафоре».(анимация Java-апплета)
• Последовательность OEIS A008302 (Таблица (статистика) количества перестановок [n], требующих k парных перестановок во время сортировки)