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

Идея

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

Пример

Сортируем [5, 2, 4, 6, 1, 3]. Отсортированный хвост выделен жирным.

Проход	Массив после прохода	Что произошло
1	2, 4, 5, 1, 3, 6	6 всплыла в конец (4 обмена)
2	2, 4, 1, 3, 5, 6	5 на месте (2 обмена)
3	2, 1, 3, 4, 5, 6	4 на месте (2 обмена)
4	1, 2, 3, 4, 5, 6	3 и 2 на месте (1 обмен)
5	1, 2, 3, 4, 5, 6	обменов нет — стоп

15 сравнений, 9 обменов. Число обменов равно числу инверсий — пар, стоящих не по порядку.

Попробуйте сами

Тот же пример по шагам. Измените данные или нажмите «Старт».

Псевдокод

BUBBLE-SORT(A)
  for pass = 0 to n − 2
    swapped = false
    for i = 0 to n − pass − 2
      if A[i] > A[i + 1]
        swap A[i] and A[i + 1]
        swapped = true
    if not swapped
      return

Сложность

Лучший	Средний	Худший	Память	Устойчивая	На месте
O(n)	O(n²)	O(n²)	O(1)	да	да

• Худший случай (массив по убыванию): проходы из n − 1, n − 2, …, 1 сравнений — всего $\frac{n(n-1)}{2}$, и каждое сравнение заканчивается обменом.
• Лучший случай (уже отсортирован): один проход из n − 1 сравнений без обменов — благодаря флагу swapped.
• Устойчивая: меняются только соседи, где левый строго больше, поэтому равные элементы никогда не перескакивают друг через друга.

Когда применять

На практике почти никогда — сортировка вставками так же проста и быстрее. Ценность пузырька — как первого алгоритма: он показывает, что такое «отсортировано», «проход», «обмен» и «инверсия».

Использование

import { bubbleSort } from 'ts-ds';

const array = [5, 2, 4, 6, 1, 3];
bubbleSort(array);
bubbleSort(array, (a, b) => b - a); // по убыванию

Справочник API

Литература

• Кнут, Искусство программирования, т. 3, §5.2.2 «Сортировка обменами».
• Кормен, задача 2-2 «Корректность пузырьковой сортировки».