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

Оптимизированная пузырьковая сортировка

Оптимизация для пузырьковой сортировки

Оптимизация

В процессе обработки массива в его начале формируется упорядоченная область, которая постоянно изменяется в размерах (может как уменьшаться так и увеличиваться после каждой итерации алгоритма).

Не составляет особого труда фиксировать размер этой области и не обрабатывать её, когда при новой итерации снова приходится начинать проходить по массиву слева-направо.

Существенного выигрыша данная оптимизация не даёт.

Характеристики алгоритма

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

Ссылки

Сортировки обменами

Пузырьковая сортировка и все-все-все

Пузьрьковая сортировка

Bubble sort

Реализация на различных ЯП