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

Сортировка простыми обменами, сортировка пузырьком (англ. bubble sort) — один из квадратичных алгоритмов сортировки.

Алгоритм

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

Псевдокод

Ниже приведен псевдокод сортировки пузырьком, на вход которой подается массив [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] i [/math]-ой итерации внешнего цикла [math] i [/math] последних элементов уже находятся на своих местах в отсортированном порядке, поэтому нет необходимости производить их сравнения друг с другом. Следовательно, внутренний цикл можно выполнять не до [math] n - 2 [/math], а до [math] n - i - 2 [/math].
• Также заметим, что если после выполнения внутреннего цикла не произошло ни одного обмена, то массив уже отсортирован, и продолжать что-то делать бессмысленно. Поэтому внутренний цикл можно выполнять не [math] n - 1 [/math] раз, а до тех пор, пока во внутреннем цикле происходят обмены.

Тогда сортировка примет такой вид:

 BubbleSort(A)
   i = 0;
   t = true;
   while t == true
     t = false;
     for j = 0 to n - i - 2
       if A[j] > A[j + 1]
         swap(A[j], A[j + 1]);
         t = true;
     i = i + 1;

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

Возьмём массив с числами «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 прохода, на которых ничего не изменится.

См. также

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

Ссылки

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