¿Qué ventaja tiene heapsort sobre smoothsort?

8

Wikipedia afirma que las ventajas de smoothsort sobre heapsort es que a veces se acerca más al tiempo O (n).

Ahora me preguntaba ¿qué ventaja tiene la ordenación dinámica sobre la ordenación suave?

O para reformular esta pregunta, ¿la ordenación suave siempre es una mejor opción que la ordenación dinámica (incluso si la entrada no está ordenada en ningún grado)?

ds.algorithms sorting Pacerier
fuente
¿Has comparado implementaciones? Quizás la diferencia es que smoothsort tiene una sobrecarga mayor tanto en términos de tiempo de ejecución como de memoria utilizada.
Dave Clarke
8
En el montón, puede construir el montón en el tiempo O (n), mientras que en el ordenamiento suave, lleva tiempo O (n log n) construir el montón. Esto sugiere (pero no implica) que el tiempo para ordenar la entrada aleatoria podría ser más largo para la ordenación sin problemas.
Peter Shor
@DaveClarke Quiero decir, no en la implementación (que puede variar) sino en el algoritmo en sí mismo
Pacerier
@PeterShor ¿Está seguro de que se necesita O (n log n) para generar el montón en smoothsort? ¿Eso parecería ir en contra de la afirmación de que smoothsort es O (n) cuando la entrada ya está ordenada?
Paul Wagland
1
@PeterShor: una variante de smoothsort que utiliza una lista binaria sesgada, ya que el bosque de montones puede acumularse en el tiempo O (n). Para hacer esto, convierta la longitud de la entrada a binario sesgado (O (log (n)). Los bits de este número le indican los tamaños de almacenamiento dinámico en el bosque. Imagine que dicho bosque ya existe sin la propiedad de almacenamiento dinámico. Esto es similar a en el montón que finge que ya tiene un montón sin la propiedad del montón. Sin embargo, incluso con este cambio, el ordenamiento uniforme (usando binario sesgado) es solo más rápido que el montón para 10% o menos sin ordenar (usando inversiones para ordenar).
ScootyPuff

Respuestas:

10

Después de leer un poco sobre los dos algoritmos, parece que el ordenamiento dinámico no tiene una ventaja O implícita sobre el ordenamiento uniforme. Esto tiene sentido cuando crees que smoothsort es solo un tipo especial de montón, usando un tipo especial de montón.

Donde el montón tiene una ventaja es que es más fácil de entender y está mucho mejor documentado. Hay muy pocas implementaciones disponibles públicamente de smoothsort, y muy poca literatura sobre ellas, sin embargo, hay mucha literatura sobre el montón.

De hecho, la única literatura accesible real es este artículo de Keith Schwarz. También es la base del artículo de Wikipedia .

Paul Wagland
fuente