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

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

Алгоритм

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

Псевдокод

Ниже приведен псевдокод сортировки пузырьком, на вход которой подается массив [math] A [/math], состоящий из [math] n [/math] элементов.

 BubbleSort(A)
   for i = 0 to n - 2
     for j = 0 to n - 2
       if A[j] > A[j + 1]
         swap(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 прохода, на которых ничего не изменится.

См. также

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

Ссылки

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