"Пузырьковая сортировка" (Bubble sort)

характеристики	значения
сложность в лучшем	$O (n)$ ¹
сложность в среднем	$O (n^{2})$
сложность в худшем	$O (n^{2})$
дополнительная память	$O (1)$
стабильная ли?	✅

¹ : В лучшем случае достигается линейная сложность, например, если массив отсортирован по возрастанию. Только в случае, если использовать ускоренную реализацию (реализация ниже с break)

Алгоритм

Пузырьковая сортировка состоит из $n$ раундов. На каждом раунде алгоритм выполняет итерацию по элементам массива. При обнаружении двух последовательных элементов которые расположены не в правильном порядке, алгоритм меняет их местами. Алгоритм можно реализовать следующим образом реализовать следующим образом

Данной сортировкой пользуются крайне редко из-за скорости её работы, поскольку при обработке массива с большим количеством элементов время может стремиться к бесконечности. Более предпочтительными будут сортировки, представленные в других разделах этой темы

Преимущества алгоритма

Не используется дополнительная память.
Для маленьких массивов предпочтительнее, чем другие алгоритмы. Я помню, что я находил статью в третьем классе на стакоферфлоу, там делали сети сортировок. TODO
Относительная простота в написание кода.

Недостатки алгоритма

Сложность - $O (n^{2})$ .

Почему такое название алгоритма?

Пузырьковая сортировка получила своё название потому, что элементы стремятся подняться в правильном порядке, как пузырьки, поднимающиеся на поверхность.

Обычная версия алгоритма

void bubbleSort(int* a, int n) {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n - 1; j++) {
      if (a[j] > a[j + 1]) {
        std::swap(a[j], a[j + 1]);
      }
    }
  }
}

Ускоренная версия алгоритма

Если во втором цикле ни один элемент не поменялся местами с соседом, значит, что массив уже отсортирован — можно выйти из функции сортировки.

void bubbleSort(int* a, int n) {
  for (int i = 0; i < n; i++) {
    bool is_any_swapped = false;
    for (int j = 0; j < n - 1; j++) {
      if (a[j] > a[j + 1]) {
        std::swap(a[j], a[j + 1]);
        is_any_swapped = true;
      }
    }
    if (!is_any_swapped) {
      break;
    }
  }
}

Запуск функции сортировки bubbleSort(array, size);

Доказательство сложности алгоритма

Временная сложность такого алгоритма всегда не менее $O (n^{2})$ , так как в худшем случае для сортировки массива требуется $O (n^{2})$ перестановок, а точнее количество инверсий. Я сделаю блок, про инверсии и как решать забавные задачи на инверсии но чуть попозже. TODO

Массив полностью отсортирован, если в нем нет инверсий. С другой стороны, если элементы массива расположены в обратном порядке, то количество инверсий будет максимально возможным.

$1 + 2 + \dots + (n - 1) = \frac{n ( n - 1 )}{2} = O (n^{2})$

Вообще можно всегда пользоваться такой мудростью "если в коде есть два цикла, то это похоже на $O (n^{2})$ ".

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

Ввод:

1 9 45 7 -2

Работа алгоритма: Алгоритм попарно сравнивает 1 с 9, 9 с 45, 45 с 7 (меняет их местами), 45 с -2 (меняет их местами), а потом идёт с самого начала, но уже с обновлённым массивом

Вывод:

-2 1 7 9 45

is-algo