¿Cuándo cambia introsort de quicksort a heapsort?
Introsort comienza con quicksort y cambia a heapsort cuando la profundidad de la recursión supera un nivel basado en la cantidad de elementos que se ordenan. ¿Cuál es ese número? ¿Hay un rango específico o un valor límite?
Respuestas a la pregunta(2)
Acabo de intentar leer la introducciónArtículo de Wikipedia. Dice
Cuenta la profundidad de la recursión. Si se excede una profundidad logarítmica, el algoritmo cambia a Heapsort desde Quicksort para mantener el resultado de peor caso de Quicksort abajo
ya través del artículo original de Musser sobre Introsort.
Dice que introsort es más lento que heapsort porque realiza 2 * log (2, N) cálculos antes de que cambie a heapsort.
Mi entendimiento es que la profundidad de la recursión es 2 * log (2, N)
Para N = 300 elementos a ordenar, será 2 * 8 = 16
El punto en el que elAlgoritmo introsort los cambios de Quicksort a Heapsort están determinados pordeep_limit:
deep_limit = 2 · ⎣log2(l) ⎦
Dóndel es la longitud de la secuencia que se va a ordenar, por lo quel = n Para toda la secuencia. Con cada llamada recursivadeep_limit Se decrementa en uno. Cuandodeep_limit llega a 0, cambia de Quicksort a Heapsort.