Алгоритмы
O(n^2) сортировки: Простые, но медленные
Цели урока
- Понять и реализовать Bubble, Selection, Insertion Sort
- Знать когда O(n²) допустимо и почему Timsort использует Insertion Sort
- Различать стабильную и нестабильную сортировку
- Выбирать алгоритм исходя из характеристик данных
Предварительные знания
- Big O нотация
- Базовое программирование
2003 год. Tim Peters пишет Timsort для Python 2.3 - и внутри O(n log n) алгоритма прячет Insertion Sort для подмассивов. Java 7 копирует этот подход. Почему? Потому что на реальных данных O(n²) с маленькими константами бьёт O(n log n) с рекурсией. Знание 'плохих' алгоритмов - это знание того, когда они становятся хорошими.
- **Timsort** (Python, Java) использует Insertion Sort для подмассивов < 64 элементов
- **Embedded системы** с ограниченной памятью - in-place O(1) сортировки
- **Визуализации алгоритмов** - Bubble Sort наглядно демонстрирует инварианты
- **Coding interview** - классика, которую просят реализовать на собеседованиях
Исторический контекст
Merge Sort изобрёл Джон фон Нейман в 1945 году, но до появления быстрых O(n log n) алгоритмов программисты 1950-60-х годов пользовались именно простыми O(n²) сортировками. Bubble Sort впервые описан в учебнике Айверсона 1962 года. Selection Sort и Insertion Sort активно применялись при сортировке перфокарт - материальный носитель данных делал минимизацию swap-ов не просто теоретической задачей.
Зачем учить медленные алгоритмы?
2003 год. Python 2.3 выходит с новым алгоритмом сортировки - Timsort. Tim Peters написал его на основе Insertion Sort для малых подмассивов. Производительность sort() вырастает в 1.5-2x на реальных данных. Мораль: O(n²) алгоритм внутри O(n log n) - не ошибка проектирования, а осознанная оптимизация.
- **Простота** - минимум кода, максимум понимания инварианта цикла
- **Паттерны** - вложенные циклы, swap, sentinel, early exit
- **Малые данные** - на n < 32 элементах O(n²) быстрее из-за cache locality
- **Собеседования** - Insertion Sort реализуют в каждом втором coding interview
| Алгоритм | Лучший | Средний | Худший | Память |
|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) |
Python Timsort и Java Arrays.sort используют Insertion Sort для подмассивов менее 64 элементов - там он быстрее из-за низких констант и cache-friendly доступа.
Timsort (Python, Java) использует Insertion Sort для подмассивов. Почему не применить O(n log n) везде?
Bubble Sort: Пузырьки всплывают
Представьте очередь студентов по росту - каждый шаг код сравниваете соседей и меняете местами, если левый выше правого. Высокие 'всплывают' вправо. После первого прохода самый высокий стоит последним. После k проходов k самых высоких стоят на местах.
Bubble Sort - самый медленный из O(n²): много swap-ов и плохой cache locality. Используется только в учебных целях - в production его применять не стоит.
Оптимизация с флагом swapped улучшает какой случай?
Selection Sort: Выбираем минимум
Стратегия: находим минимальный элемент в неотсортированной части и ставим его на своё место. Ровно n-1 swap-ов - это уникальное свойство. Если каждый swap дорог (например, большие объекты или запись на flash-память), Selection Sort выигрывает.
Преимущество Selection Sort: ровно n-1 swap-ов независимо от входа. При дорогом swap-е (большие объекты, flash-память) это лучше Bubble Sort с O(n²) swap-ами.
Selection Sort делает сколько swap-ов для массива из 10 элементов?
Insertion Sort: Вставляем на место
Карточная игра: берёте карту из колоды и вставляете в правильное место в уже отсортированной руке. Insertion Sort работает так же - каждый новый элемент сдвигает влево тех, кто больше его, и встаёт на нужное место. На почти отсортированных данных (k инверсий) работает за O(n + k).
Insertion Sort - единственный online-алгоритм из трёх: сортирует данные по мере поступления, без доступа ко всему массиву. Bubble и Selection требуют весь массив заранее.
На почти отсортированных массивах (log n инверсий) Insertion Sort даёт O(n log n) - такой же результат как Quick Sort, но без рекурсии и overhead-а.
Insertion Sort работает за O(n) когда:
Сравнение: когда что использовать
| Критерий | Bubble | Selection | Insertion |
|---|---|---|---|
| Простота кода | ★★★ | ★★★ | ★★☆ |
| Best case | O(n) | O(n²) | O(n) |
| Количество swap | O(n²) | O(n) | O(n²) |
| Стабильность | Да | Нет | Да |
| Online | Нет | Нет | Да |
| Почти отсортировано | Хорошо | Плохо | Отлично |
Стабильность - сохраняет ли алгоритм относительный порядок одинаковых элементов. Важно при многоуровневой сортировке.
В реальных проектах используйте встроенные сортировки: sorted() в Python, Arrays.sort() в Java, std::sort() в C++. Они оптимизированы, используют O(n log n) и прошли production-проверку.
Нужно отсортировать список из 1000 событий, уже почти упорядоченных по времени (несколько событий не по порядку). Какой алгоритм выбрать?
O(n²) сортировки: итого
- Bubble: swap соседей, большие всплывают; best case O(n) с флагом swapped
- Selection: находим min, ставим на место; всегда ровно n-1 swap-ов
- Insertion: вставляем в отсортированную часть; O(n + k) на k-инверсных данных
- Все O(n²) в худшем случае, O(1) дополнительная память
- Insertion лучший для почти отсортированных данных - Timsort использует его внутри
- В production используйте встроенные sorted() / Arrays.sort()
Следующие шаги
O(n²) недостаточно для больших данных. Следующий уровень - O(n log n) сортировки.
- Merge Sort — Divide and Conquer, O(n log n), стабильный
- Quick Sort — Самый быстрый на практике, O(n log n) среднее
- Heap Sort — In-place O(n log n), O(1) память