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

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

Статическая визуализация пузырьковой сортировки
Сорт	Алгоритм сортировки
Структура данных	Множество
Худшая производительность	$O(n^{2})$ сравнения, $O(n^{2})$ свопы
Лучшая производительность	$O(n)$ сравнения, $O(1)$ свопы
Средняя производительность	$O(n^{2})$ сравнения, $O(n^{2})$ свопы
Наихудшая пространственная сложность	$O(n)$ общий, $O(1)$ вспомогательный
Оптимальный	Нет

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

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

История

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

Анализ

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

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

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

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

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

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

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

Были предприняты различные усилия по уничтожению черепах, чтобы повысить скорость сортировки пузырьков. Коктейльная сортировка — это двунаправленная пузырьковая сортировка, которая идет от начала до конца, а затем меняет направление, переходя от начала к началу. Он может довольно хорошо перемещать черепах, но сохраняет $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):

procedure bubbleSort(A : list of sortable items)
    n := length(A)
    repeat
        swapped := false
        for i := 1 to n-1 inclusive do
            { if this pair is out of order }
            if A[i-1] > A[i] then
                { swap them and remember something changed }
                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 : list of sortable items)
    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 : list of sortable items)
    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

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

Используйте

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

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

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

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

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

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

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

Вариации

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

Дебаты по поводу названия

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

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

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

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

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

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

Ссылки

• Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Стейн . Введение в алгоритмы , второе издание. 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 парных перестановок во время сортировки)