Внедрение и сложность Introsort (quicksort + heapsort)
Я читал, что C ++ использует introsort (интроспективная сортировка) для встроенного std :: sort, где он начинается с быстрой сортировки и переключается на heapsort, когда вы достигнете предела глубины.
Я также читал, что предел глубины должен быть 2 * log (2, N).
Это значение чисто экспериментальное? Или за этим стоит какая-то математическая теория?
Решение
Если у вас есть интервал (диапазон или массив), количество раз, которое вам придется разделить интервал пополам, прежде чем вы получите пустой (или один элемент) интервал, равно log(2,N)Это просто математический факт, вы можете легко разобраться, если хотите. Если с quicksort все идет отлично, следует log(2,N) раз, по той же причине (и на каждом уровне рекурсии, он должен обрабатывать все значения интервала, что приводит к O(N*log(2,N)) сложность для общего алгоритма). Проблема в том, что для быстрой сортировки может потребоваться гораздо больше рекурсий (если она продолжает «не везти» с выбором значений сводных значений, что означает, что она не делит интервал пополам, а вместо этого дисбалансирует). В худшем случае, быстрая сортировка может закончиться повторением N раз, что определенно неприемлемо для реализации с качеством производства.
Переключение на сортировку кучи в 2*log(2,N) это просто хорошая эвристика в целом, чтобы обнаружить слишком глубокое количество рекурсий.
Технически, вы могли бы основывать это на эмпирической производительности сортировки кучи и быстрой сортировки, чтобы выяснить, какой предел является лучшим. Но такие тесты сильно зависят от приложения (что вы сортируете? Как вы сравниваете элементы? Насколько дешевы замены элементов? И т. Д.). Таким образом, наиболее универсальная реализация, как std::sort, выбрал бы разумный предел, как 2*log(2,N),
Другие решения
То, что @Mikael Persson сказал относительно того, почему предел глубины составляет 2 * log (2, N), отчасти правильно. Это не просто хорошая эвристика или разумный предел.
На самом деле, как вы, вероятно, догадались (показано из вашего второго вопроса), для этого есть важная математическая причина: тильда обозначение (поиск обозначения тильды), быстрая сортировка в среднем ~ 2 * журнал (2, N) сравнения. В о большом обозначение, это эквивалентно O (N * журнал (2, N)).
Вот почему интросорт переключается на heapsort (который имеет асимптотическую сложность O (N * log (2, N))), когда глубина рекурсии становится больше 2 * log (2, N). Вы можете думать об этом, как о чем-то необычном, и, скорее всего, это означает, что что-то пошло не так, если выбрать только сводную последовательность и быструю сортировку, что приведет к сложности O (N ^ 2).
Вы можете найти краткое математическое доказательство среднего числа сравнений, которые выполняет быстрая сортировка. здесь (слайд 21).