Вопрос по sorting, introsort, algorithm – Когда интросортировка переключается с быстрой сортировки на heapsort?

6

Introsort начинается с быстрой сортировки и переключается на heapsort, когда глубина рекурсии превышает уровень, основанный на количестве сортируемых элементов. Что это за номер? Есть ли определенный диапазон или предельное значение?

Ваш Ответ

2   ответа
6

Точка, в которойАлгоритм интросортировки Переключение из быстрой сортировки в Heapsort определяетсяdepth_limit:

depth_limit = 2 · ⎣log2(l)⎦

кудаl длина последовательности, которая должна быть отсортирована, такl& # X200D; = & # x200D;n для всей последовательности. С каждым рекурсивным вызовомdepth_limit уменьшается на единицу. когдаdepth_limit достигает 0, переключается с быстрой сортировки на Heapsort.

@self. Почему ты так думаешь?
@self. Ну, лучше всего разделить пополам; в худшем случае последовательность будет разбита на (1, N-1). В этом случае глубина_предела достигает 0.
По вашей логике Heapsort никогда не произойдет, так как предел глубины никогда не будет достигнут.
Прочитайте мой комментарий ниже; другой пример: массив из 10000 членов будет иметь предел глубины (13 * 2), если массив, если он приблизительно разделен пополам на каждой рекурсии, то на 14-м уровне подмассивы будут иметь 0 элементов.
2

Статья в википедии, Это говорит

It counts the recursion depth. If a logarithmic depth is exceeded, the algorithm switches to Heapsort from Quicksort to keep the worst case outcome of Quicksort down

и через оригинальную статью Musser о Introsort.

It says that introsort is slower than heapsort because it performs 2*log(2,N) computations before it switches to heapsort.

Насколько я понимаю, глубина рекурсии составляет 2 * log (2, N)

For N=300 elements to sort, it will be 2*8 = 16

Если использовать ограничение глубины 16 на массиве из 300 элементов примерно на 10-м уровне глубины, у подмассива будет 0 элементов.

Похожие вопросы