Интроспективная сортировка :: Introsort
В основе алгоритма лежит быстрая сортировка. На случай, если имеем дело с "массивом-убийцей" (т.е. являющийся для быстрой сортировки вырожденным случаем), происходит переключение на пирамидальную сортировку.
Массивы-убийцы
Быстрая сортировка, по всей видимости, в самом общем случае является наиболее эффективным методом для упорядочивания данных. Однако не всё так просто. Самое слабое звено алгоритма - подбор базовых элементов для подмассивов при рекурсивных вызовах. При неудачном раскладе сортировка сама себя вызывает максимальное количество раз, а рекурсия - процесс дорогостоящий для памяти.
Никлаус Вирт предложил для преодоления проблемы выбор опоры осуществлять по принципу "медиана из трёх", т.е. в качестве базового ключа подмассива брать средний по величине элемент из 3-х претендентов: первого элемента подмассиса, последнего элемента подмассива и элемента посередине.
Хотя в абсолютном большинстве случаев это позволяло избежать неприятностей, оно не гарантировало 100%-го решения проблемы. Оставалась возможность специально подобрать такой массив, на котором быстрая сортировка, даже реализованная с помощью принципа "медиана из 3-х", всё равно быстро деградировала. Если использовать вместо правила "медиана из 3-х" какое-нибудь другое, то это принципиально ничего не меняет - вырожденный случай подбирается в соответствии с конкретной реализацией.
С помощью "массива-убийцы" теоретически можно было атаковать веб-сервер, написанный на языке, использующего быструю сортировку по умолчанию (то есть, в 90-х годах практически на любом ЯП). Предложив серверу для обработки "массив-убийцу" из миллиона элементов, можно было вызвать перегрузку и вывести из строя объект атаки.
Решение проблемы
В качестве отражения потенциальных угроз Девид Мюссер предложил контролировать максимальную глубину рекурсии, допустимую для алгоритма быстрой сортировки (например, можно ориентироваться на величину log n). Если глубина рекурсии достигала этой величины, то дальнейшее упорядочивание подмассива, от которого поступил тревожный сигнал, производится с помощью пирамидальной сортировки. Пирамидальная сортировка характерна тем, что у неё нет ни вырожденных, ни лучших наборов данных, любые массивы она сортирует всегда с одинаковой временной сложностью - O(n log n).
Мюссер подобрал "киллер" из 100 тысяч элементов и протестировал его. Introsort обработал массив в 200 раз быстрее чем QuickSort.
Характеристики алгоритма
Характеристики алгоритма
| Название | Интроспективная сортировка (Introsort, Introspective sort) | |
|---|---|---|
| Автор | Дэвид Мюссер (David Musser) | |
| Год | 1997 | |
| Класс | Гибридные сортировки (быстрая + кучей) | |
| Устойчивость | Нет | |
| Сравнения | Да | |
| Сложность по времени | Лучшая | O (n) |
| Средняя | O (n log n) | |
| Худшая | ||
| Сложность по памяти | Общая | O(n) |
| Дополнительная | O(1) | |
Introsort