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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

Алгоритм[править | править исходный текст]

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

Псевдокод[править | править исходный текст]

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

На входе: массив A[N], состоящий из N элементов, с нумерацией от A[1] до A[N]

 ЦИКЛ ДЛЯ J=1 ДО N-1 ШАГ 1                   FOR J=1 TO N-1 STEP 1 
   ЦИКЛ ДЛЯ I=1 ДО N-J ШАГ 1                   FOR I=1 TO N-J STEP 1 
     ЕСЛИ A[I]>A[I+1] ТО ОБМЕН A[I],A[I+1]       IF A[I]>A[I+1] THEN SWAP A[I],A[I+1]
     СЛЕДУЮЩЕЕ I                                 NEXT I
   СЛЕДУЮЩЕЕ J                                 NEXT J

В улучшенном алгоритме количество повторов во внутреннем цикле уменьшается на 1 с каждой итерацией внешнего цикла.

Если нет функции обмена (SWAP A[I],A[I+1]), то её можно заменить тремя операторами присваивания:

 TEMP=A[I]
 A[I]=A[I+1]
 A[I+1]=TEMP

Сложность: O(n·n), не уменьшается.

Наихудший случай:

  • Число сравнений в теле цикла равно (N-1)*N/2.
  • Число сравнений в заголовках циклов равно (N-1)*N/2.
  • Суммарное число сравнений равно (N-1)*N.
  • Число присваиваний в заголовках циклов равно (N-1)*N/2.
  • Число обменов равно (N-1)*N/2, что в N/2 раз больше, чем в сортировке выбором.

Наилучший случай (на вход подаётся уже отсортированный массив):

  • Число сравнений в теле цикла равно (N-1)*N/2.
  • Число сравнений в заголовках циклов равно (N-1)*N/2.
  • Суммарное число сравнений равно (N-1)*N.
  • Число обменов равно 0.

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

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

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

Псевдокод ещё более улучшенного алгоритма с проверкой действительно произошедших обменов во внутреннем цикле.

На входе: массив A[N], состоящий из N элементов, с нумерацией от A[1] до A[N]

 ЦИКЛ ДЛЯ J=1 ДО N-1 ШАГ 1                       FOR J=1 TO N-1 STEP 1
   F=0                                             F=0 
   ЦИКЛ ДЛЯ I=1 ДО N-J ШАГ 1                       FOR I=1 TO N-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)*N/2.
  • Число сравнений в заголовках циклов (N-1)*N/2.
  • Суммарное число сравнений равно (N-1)*N.
  • Число присваиваний в заголовках циклов равно (N-1)*N/2.
  • Число обменов равно (N-1)*N/2.

Наилучший случай (улучшается):

  • Число сравнений в теле цикла равно (N-1).
  • Число сравнений в заголовках циклов (N-1).
  • Суммарное число сравнений равно 2*(N-1).
  • Число обменов равно 0.

Время сортировки 10000 коротких целых чисел на одном и том же программно-аппаратном комплексе (операция сравнения ≈3.4мкс, обмена ≈2.3мкс) сортировкой выбором составило ≈40сек., ещё более улучшенной сортировкой пузырьком ≈30сек, а быстрой сортировкой ≈0,027сек.

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

Алгоритм можно немного улучшить, сделав следующее:

  • Внутренний цикл можно модифицировать так, чтобы он поочерёдно просматривал массив то с начала, то с конца. Модифицированный таким образом алгоритм называется сортировкой перемешиванием или шейкерной сортировкой. Сложность при этом O(n·n) не уменьшается.

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

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

 FOR J=1 TO N-1 STEP 1
    F=0
    MIN=J
    FOR I=J TO N-J STEP 1 
       IF Y[I]>Y[I+1] THEN SWAP Y[I],Y[I+1]:F=1
       IF Y[I]<Y[MIN] THEN MIN=I
       NEXT I
    IF F=0 THEN EXIT FOR
    IF MIN<>J THEN SWAP Y[J],Y[MIN]
    NEXT J

Пример работы алгоритма[править | править исходный текст]

Возьмём массив с числами «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)
(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)

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

Примеры реализаций[править | править исходный текст]

Java/C++[править | править исходный текст]

 for (int j = 0; j < n - 1; j++)
 {
     f = 0;
     min = j;
     for(int i = j; i < (n - j - 1); i++)
     {
         if (list[i] > list[i + 1])
         {
             temp = list[i];
             list[i] = list[i + 1];
             list[i + 1] = temp;
             f = 1;
         }
         if (list[i] < list[min])
         min = i;
     }
     if (f == 0)
         break;
     if (min != j)
     {
         temp = list[j];
         list[j] = list[min];
         list[min] = temp;
     }
 }

Erlang[править | править исходный текст]

bubble(List) ->
	bubble_loop0(List, []).
 
bubble_loop0([], Result) ->
	Result;
bubble_loop0([Head|Tail], Result) ->
	{Value, List} = bubble_loop1(Head, Tail, []),
	bubble_loop0(List, [Value|Result]).
 
bubble_loop1(Value, [], Result) ->
	{Value, Result};
bubble_loop1(Value, [Head|Tail], Result) ->
	if
		Value > Head ->
			bubble_loop1(Head, Tail, [Value|Result]);
		true ->
			bubble_loop1(Value, Tail, [Head|Result])
	end.

Python3.x[править | править исходный текст]

# Реализация в виде функции
def bubble_sort(arr):
    for i in range(len(arr)-2):
        for j in range(len(arr) - i - 1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

Примечания[править | править исходный текст]

Ссылки[править | править исходный текст]

Литература[править | править исходный текст]

  • Ананий В. Левитин. Глава 3. Метод грубой силы: Пузырьковая сортировка // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Algorithms. — М.: Вильямс, 2006. — С. 144-146. — ISBN 5-8459-0987-2