¿Por qué introsort usa el montón en lugar del mergesort?

Como parte de una tarea que cubre la implementación de introsort , me preguntan por qué se usa heapsort en lugar de mergesort (u otros algoritmos para el caso). $O(n\log(n))$

Introsort es un algoritmo de clasificación híbrido que proporciona un rendimiento promedio rápido y (asintóticamente) un rendimiento óptimo en el peor de los casos. Comienza con el ordenamiento rápido y cambia al ordenamiento dinámico cuando la profundidad de recursión excede un nivel basado en (el logaritmo de) el número de elementos que se ordenan. ( Wikipedia , recuperado 2014-mayo-06.)

La única razón por la que puedo pensar es que el montón está "en su lugar" ... Pero tbh, realmente no entiendo por qué esto sería importante aquí.

algorithms algorithm-analysis sorting usuario672009
fuente

Si el introsort es parte de la pregunta, tendrá que decirnos qué es antes de que podamos decir algo.

Louis

¡Bienvenido a Computer Science ! Tenga en cuenta que puede usar LaTeX aquí para componer las matemáticas de una manera más legible. Vea aquí para una breve introducción.

FrankW

Simplemente se nos pide que creemos un pseudocódigo para la clasificación de introducción y más adelante se nos pregunta por qué utiliza el ordenamiento dinámico en lugar del ordenamiento combinado.

user672009

@ user672009 En ese caso, escriba el código para cualquiera de los dos y vea lo que encuentra. La razón puede o no estar relacionada con el rendimiento.

Raphael

Llegué a la conclusión de que, dado que el ordenamiento rápido está en su lugar, necesitamos usar otro algoritmo de clasificación en el lugar. Sin embargo, estoy abierto a la entrada.

user672009

Respuestas:

Las 2 desventajas de quicksort es que requiere espacio adicional (para mantener los intervalos no ordenados) y una mala selección de pivote (o secuencias artificiales diseñadas para hacer que seleccione un pivote incorrecto) puede causar que sea un tiempo y algoritmo de espacio extra. $O(\log n)$ $O(n^2)$ $O(n)$

Cambiar a la ordenación en grupo cuando la profundidad de recursión es demasiado grande (alrededor de ) significa que tenemos un límite superior garantizado que es tiempo y espacio extra. $\log n$ $O(n \log n )$ $O( \log n)$

El requisito de espacio adicional de Heapsort lo convierte en una mejor opción para combinar donde para una matriz ideada que aún podría ser grande. $O(1)$ $O(n)$ $n$

La razón por la que no se usa el ordenamiento dinámico para la ordenación completa es porque es más lento que el ordenamiento rápido (debido en parte a las constantes ocultas en la gran expresión O y en parte al comportamiento del caché)

monstruo de trinquete
fuente

Pero se usa heapsort ... y sospecho que es porque está en su lugar como quicksort.

user672009

Sospecho que @ user672009 está confundido por su última oración. Sugeriría aclarar que introsort no comienza con heapsort porque es más lento.

Wandering Logic

O (1)

$O(1)$

O (\lg n)

$O(\lg n)$

Además, heapsort tiene muchos más errores de caché que introsort.

noɥʇʎԀʎzɐɹƆ

Una buena implementación de Quicksort no necesita espacio O (n) en el peor de los casos, siempre que recuerde el subintervalo más grande en la pila y maneje el más pequeño inmediatamente.

gnasher729