Пузырьковая сортировка (оптимизированная) :: Bubble Sort (optimization)

Оптимизация для пузырьковой сортировки
Оптимизация
В процессе обработки массива в его начале формируется упорядоченная область, которая постоянно изменяется в размерах (может как уменьшаться так и увеличиваться после каждой итерации алгоритма).
Не составляет особого труда фиксировать размер этой области и не обрабатывать её, когда при новой итерации снова приходится начинать проходить по массиву слева-направо.
Существенного выигрыша данная оптимизация не даёт.
Характеристики алгоритма
Название | Пузырьковая сортировка (Bubble sort) | |
---|---|---|
Другие названия | Сортировка простыми обменами | |
Класс | Сортировки обменами | |
Устойчивость | Да | |
Сравнения | Да | |
Сложность по времени | Худшая | O(n2) |
Средняя | O(n2) | |
Лучшая | O(n) | |
Сложность по памяти | Общая | O(n) |
Дополнительная | O(1) |