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

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

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

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

Этот простой алгоритм плохо работает в реальном мире и используется в основном как обучающий инструмент. Более эффективные алгоритмы, такие как быстрая сортировка , временная сортировка или сортировка слиянием , используются библиотеками сортировки, встроенными в популярные языки программирования, такие как Python и Java.

Анализ

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

Представление

Пузырьковая сортировка имеет наихудший случай и среднюю сложность О ( n ² ), где n - количество сортируемых элементов. Большинство практических алгоритмов сортировки имеют существенно лучшую сложность в худшем случае или в среднем, часто O ( n  log  n ). Даже другое О ( п ² ) алгоритмы сортировки, такие как вставки рода , как правило , не работать быстрее , чем пузырьковой сортировки, а не более сложным. Следовательно, пузырьковая сортировка не является практическим алгоритмом сортировки.

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

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

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

Были предприняты различные попытки уничтожить черепах, чтобы повысить скорость сортировки пузырей. Сортировка коктейлей - это двунаправленная сортировка пузырьков, которая идет от начала до конца, а затем меняет свое направление, идя от конца к началу. Он может довольно хорошо перемещать черепах, но сохраняет сложность наихудшего случая O (n ² ) . Сортировка гребенкой сравнивает элементы, разделенные большими промежутками, и может очень быстро перемещать черепах, прежде чем переходить к все меньшим и меньшим промежуткам, чтобы сгладить список. Его средняя скорость сопоставима с более быстрыми алгоритмами вроде быстрой сортировки .

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

Возьмите массив чисел «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 ² ) такие алгоритмы, как сортировка вставкой , обычно значительно более эффективны.

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

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

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

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

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

Вариации

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

Споры по поводу имени

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

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

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

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

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

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

Примечания

использованная литература

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

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

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