Закрепление материала: Сортировки

Краткое резюме модуля

В этом модуле мы последовательно разобрали три группы алгоритмов сортировки:

• Простые O(N²): Сортировка вставкой, выборкой и пузырьковая сортировка. Интуитивно понятны, легко реализуются, но непригодны для больших массивов. Сортировка вставкой выделяется тем, что на почти отсортированных данных работает почти за O(N).
• Эффективные O(N log N): Сортировка Шелла (улучшение вставок, до O(N^4/3)), турнирная, пирамидальная, Хоара, слиянием, естественное слияние, Timsort. Это основные алгоритмы для задач сортировки в реальных программах. Сортировка Хоара - на практике самая быстрая. Сортировка слиянием - гарантированно быстрая и устойчивая.
• Линейные O(N): Сортировка подсчетом, поразрядная, карманная. Обходят нижнюю границу O(N log N), но применимы только к определенным типам данных.

На практике инженеру часто приходится выбирать инструмент под конкретные ограничения. Например, если массив малый - лучше подойдет сортировка Вставкой. Если числа имеют узкий диапазон - идеальна сортировка Подсчетом. Если жестко ограничен лимит памяти - выбираем Пирамидальную. А если нужна устойчивость - Слиянием. В остальных случаях по умолчанию часто используется сортировка Хоара.

Ключевые идеи

• Нижняя граница: Любая сортировка на основе сравнений не может работать быстрее O(N log N) в среднем/худшем случае.
• Устойчивость: Сохранение порядка равных элементов. Важна при сортировке по нескольким ключам (например, сначала по фамилии, потом по имени).
• Доп. память: Количество памяти сверх той, что нужна для хранения самого массива. O(1) означает сортировку на месте. Пирамидальная сортировка - единственная, дающая O(N log N) без доп. памяти.
• Разделяй и властвуй: Принцип, на котором построены Сортировка Хоара и Сортировка слиянием.

Проверьте себя