Пузырьковая сортировка
Снова и снова проходит по списку и меняет местами соседей, стоящих не в том порядке. После каждого прохода наибольшее из оставшихся значений оказывается в конце.
- Ω(n)
- Θ(n²)
- O(n²)
- O(1)
- да
- да
Лучший случай: как растёт время с размером списка n, когда входные данные самые удобные для алгоритма.
Средний случай: обычный рост времени с n. При n² вдвое больше значений сортируются вчетверо дольше; n log n растёт намного медленнее.
Худший случай: рост времени на самых неудобных данных. Важно, когда скорость не должна падать никогда.
Память: сколько памяти нужно сверх самого списка. 1 значит несколько переменных, n значит копию списка.
Стабильное: равные значения сохраняют исходный порядок. Это важно, когда записи сортируют по одному полю.
Без дополнительной памяти: сортирует внутри самого списка, без второго списка.
- сравнение
- перемещение
- на окончательном месте
Попробуйте: Выберите почти отсортированный список. После прохода без единого обмена алгоритм останавливается раньше.
Как это работает
Сравнивает два соседних значения и меняет их местами, если левое больше. Так за каждый проход самое большое значение доходит до правого края, как всплывающий пузырёк. Если за проход не было ни одного обмена, список уже отсортирован.
Когда стоит применять
В реальных программах почти никогда, потому что на длинных списках она медленная. Зато хорошо подходит для обучения: показывает саму идею сортировки сравнениями и обменами. Быстрая она только на уже отсортированном списке.