Внимание! Практически весь материал этой лекции был в видеолекции.

class=»embed-responsive-item»



Если вы всё хорошо усвоили, просто пробегитесь глазами и переходите дальше.

Алгоритм у пузырьковой сортировки — один из простейших.

Идем вдоль всего массива и сравниваем 2 соседних элемента. Если они в неправильном порядке, меняем их местами. При первом проходе в конце окажется («всплывет») самый маленький элемент (если мы сортируем в порядке убывания). 

Повторять первый шаг, если хотя бы один обмен на предыдущем шаге был совершен.

Давайте отсортируем массив. 

Алгоритмы сортировки. Пузырьковая сортировка - 1

Шаг 1: идем по массиву. Алгоритм начинает работу с первых двух элементов, 8 и 6 и проверяет, находятся ли они в правильном порядке. 8 > 6, поэтому меняем их местами. Далее мы смотрим на второй и третий элементы, теперь это 8 и 4. Из тех же соображений меняем их местами. В третий раз сравниваем 8 и 2. Итого, мы делаем три обмена (8, 6), (8, 4), (8, 2). Значение 8 «всплыло» в конец списка на правильную позицию. 

Алгоритмы сортировки. Пузырьковая сортировка - 2

Шаг 2: меняем местами (6,4) и (6,2). 6 теперь на предпоследней позиции, и её можно не сравнивать с уже отсортированным «хвостом» списка. 

Алгоритмы сортировки. Пузырьковая сортировка - 3


Шаг 3: 
меняем местами 4 и 2. Четверка «всплывает» на свое законное место. 

Алгоритмы сортировки. Пузырьковая сортировка - 4

Шаг 4: проходимся по массиву, но менять нам уже нечего. Это сигнализирует о том, что массив полностью отсортирован. 

Алгоритмы сортировки. Пузырьковая сортировка - 5

А это — код алгоритма. Попробуйте реализовать его на Си! 

Алгоритмы сортировки. Пузырьковая сортировка - 6

Пузырьковая сортировка проходит за время O(n2) в худшем случае (все числа стоят неправильно), поскольку нам нужно сделать n шагов на каждой итерации, которых тоже n. На самом деле, как и в случае с алгоритма сортировки выбором, время будет несколько меньше (n2/2 – n/2), но этим можно пренебречь. 

В лучшем случае (если все элементы уже стоят на своем месте), мы справимся за n шагов, т.е. Ω(n), поскольку нам нужно будет просто пробежаться по массиву один раз и убедиться, что все элементы стоят на своих местах (т.е. даже n-1 элементов).