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

Сортировка простыми обменами, сортиро́вка пузырько́м (англ. bubble sort) — простой алгоритм сортировки. Сложность алгоритма: [math]O(n^2)[/math]

Алгоритм

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

Псевдокод

Вход: массив A, состоящий из элементов A[0], A[1], ..., A[n-1], который требуется отсортировать по возрастанию

  цикл для i = 0, 1, ..., n − 1:
    цикл для j = i + 1, ..., n − 2:
      если A[j] > A[j+1], то:
        обменять местами элементы A[j] и A[j+1]

Оптимизация

• Внутренний цикл можно выполнять для [math]j = 0, 1, ..., n - i - 1[/math], где [math]i[/math] — номер итерации внешнего цикла, так как на [math]i[/math]-й итерации последние [math]i[/math] элементов массива уже будут правильно упорядочены.
• Внешний цикл можно заменить на цикл вида: пока произведится хотя бы один обмен на очередной итерации внешнего цикла, продолжать выполнение.

И тогда псевдокод будет выглядеть так:

t := истина
цикл пока t:
  t := ложь
  цикл для j = 0, 1, ..., n − 2:
    если A[j] > A[j+1], то:
      обменять местами элементы A[j] и A[j+1]
      t := истина

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

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

Теперь массив полностью отсортирован, но неоптимизированный алгоритм проведет еще 2 прохода, на которых ничего не изменится.

См. также

• Сортировка выбором
• Сортировка вставками
• Сортировка кучей
• Сортировка слиянием
• Быстрая сортировка
• Сортировка подсчетом

Источники

• Википедия - свободная энциклопедия