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