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

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

Сортировка пузырько́м (англ. bubble sort), сортиро́вка простыми обменами, метод сортировки обменами — один из алгоритмов сортировки. По сравнению с другими алгоритмами считается простейшим для понимания и реализации. Эффективен для массивов небольшого размера. $n$ — размер массива, количество элементов массива. Сложность алгоритма: $O$$(n^{2})$.

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

Алгоритм

Выполняется некоторое количество проходов по массиву — начиная от начала массива, перебираются пары соседних элементов массива. Если 1-й элемент пары больше 2-го, элементы переставляются (выполняется обмен).

Пары элементов массива перебираются (проходы по массиву повторяются) либо $(n-1)$ раз, либо до тех пор, пока на очередном проходе не обнаружится, что более не требуется выполнять перестановки (обмены) (массив отсортирован).

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

Реализация

Сложность: $O(n^{2})$.

Для наихудшего случая верно следующее.

• Элементы массива упорядочены по убыванию (например, «3 2 1»).
• Количество сравнений, выполняемых в теле цикла, равно $(n-1)\cdot {\frac {n}{2}}$.
• Количество сравнений, выполняемых в заголовках циклов, равно $(n-1)\cdot {\frac {n}{2}}$.
• Суммарное количество сравнений равно $(n-1)\cdot n$.
• Количество присваиваний в заголовках циклов равно $(n-1)\cdot {\frac {n}{2}}$.
• Количество перестановок равно $(n-1)\cdot {\frac {n}{2}}$ (что в ${\frac {n}{2}}$ раз больше, чем при сортировке выбором).

Для наилучшего случая верно следующее.

• Элементы массива упорядочены по возрастанию (например, «1 2 3»).
• Количество сравнений, выполняемых в теле цикла, равно $(n-1)\cdot {\frac {n}{2}}$.
• Количество сравнений, выполняемых в заголовках циклов, равно $(n-1)\cdot {\frac {n}{2}}$.
• Суммарное количество сравнений равно $(n-1)\cdot n$.
• Количество перестановок равно числу 0.

Особенность алгоритма. После 1-го прохода (завершения внутреннего цикла) максимальный элемент массива находится в позиции номер $(n-1)$. После 2-го прохода следующий по значению максимальный элемент находится в позиции номер $(n-2)$. И так далее. Для каждого следующего прохода по сравнению с текущим проходом количество обрабатываемых элементов меньше на единицу. Нет необходимости каждый проход перебирать все пары элементов («обходить» весь массив) от начала массива к концу массива.

Если $n=1$ (массив содержит один элемент), то не требуется сортировать массив. Если $n>1$, для сортировки массива требуется выполнить не более $(n-1)$ итераций внешнего цикла. Некоторые реализации выполняют тело внешнего цикла $(n-1)$ раз и не учитывают (не отслеживают) информацию о том, были ли или не были перестановки на каждой итерации цикла.

Если на вход подаётся частично отсортированный массив, то можно уменьшить количество проходов по массиву — ввести индикатор произошедших перестановок (флажок F). Перед каждым проходом по внутреннему циклу флажок F сбрасывается в 0, а после перестановки — устанавливается в 1. Если после выполнения внутреннего цикла флажок F равен 0, то при выполнении внутреннего цикла перестановок не было; то есть, массив отсортирован и можно досрочно выйти из программы сортировки.

Псевдокод улучшенного алгоритма — алгоритма с проверкой, были ли перестановки во внутреннем цикле.

На входе: массив $A[n]$ — массив, содержащий $n$ элементов. 1-й элемент обозначен как $A[0]$, последний — как $A[n-1]$.

 ЦИКЛ ДЛЯ J=1 ДО n-1 ШАГ 1                       FOR J=1 TO n-1 STEP 1
   F=0                                             F=0
   ЦИКЛ ДЛЯ I=0 ДО n-1-J ШАГ 1                     FOR I=0 TO n-1-J STEP 1
     ЕСЛИ A[I] > A[I+1] ТО ОБМЕН A[I],A[I+1]:F=1     IF A[I]>A[I+1] THEN SWAP A[I],A[I+1]:F=1
   СЛЕДУЮЩЕЕ I                                     NEXT I
   ЕСЛИ F=0 ТО ВЫХОД ИЗ ЦИКЛА                      IF F=0 THEN EXIT FOR
 СЛЕДУЮЩЕЕ J                                     NEXT J

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

Для наихудшего (не улучшаемого) случая верно следующее.

• Количество сравнений, выполняемых в теле цикла, равно $(n-1)\cdot {\frac {n}{2}}$.
• Количество сравнений, выполняемых в заголовках циклов, равно $(n-1)\cdot {\frac {n}{2}}$.
• Суммарное количество сравнений равно $(n-1)\cdot n$.
• Количество присваиваний в заголовках циклов равно $(n-1)\cdot {\frac {n}{2}}$.
• Количество перестановок равно $(n-1)\cdot {\frac {n}{2}}$.

Для наилучшего случая верно следующее.

• Количество сравнений, выполняемых в теле цикла, равно $(n-1)$.
• Количество сравнений, выполняемых в заголовках циклов, равно $(n-1)$.
• Суммарное количество сравнений равно $2\cdot (n-1)$.
• Количество перестановок (обменов) равно числу 0.

На программно-аппаратном комплексе, выполняющем сравнение примерно 3.4 мкс и выполняющем перестановку примерно 2.3 мкс, время сортировки 10 000 коротких целых чисел реализацией алгоритма сортировки выбором составило примерно 40 с, ещё более улучшенной сортировкой пузырьком — примерно 30 с, а быстрой сортировкой — примерно 0.027 с.

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

Если во внутреннем цикле просматривать массив не от начала к концу, а поочерёдно то от начала к концу, то от конца к началу, то получится алгоритм, называемый алгоритмом сортировки перемешиванием (шейкерной сортировки). Сложность полученного алгоритма равна $O(n\cdot n)$, не меньше сложности исходного алгоритма.

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

Псевдокод устойчивой реализации объединнного алгоритма сортировки пузырьком и сортировки выбором:

Пример работы алгоритма

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

Наглядная демонстрация алгоритма.

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

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

(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)

Теперь массив отсортирован и алгоритм может быть завершён.

Ссылки

• Динамическая визуализация 7 алгоритмов сортировки с открытым исходным кодом
• Левитин А. В. Глава 3. Метод грубой силы: Пузырьковая сортировка // Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006. — С. 144—146. — 576 с. — ISBN 978-5-8459-0987-9