sort bubble algorithm sorting heapsort

algorithm - bubble - insertion sort



¿Por qué no usar la ordenación de montón siempre? (5)

Cuando trabajé durante un corto período de tiempo en las computadoras Tandem Non-Stop a mediados de los 80, noté que la rutina de ordenación in-core del sistema era HeapSort, precisamente porque proporcionaba un rendimiento NlogN garantizado. No conozco a nadie que tenga alguna razón para usarlo, así que no sé cómo funcionó en la práctica. Me gusta el heapsort, pero además de los inconvenientes mencionados anteriormente, he oído decir que hace un uso pobre de los recuerdos modernos, porque hace que la memoria acceda a todos lados, mientras que el quicksort e incluso los tipos de radix pequeños terminan entremezclándose un número relativamente pequeño de flujos de lecturas y escrituras secuenciales, por lo que los cachés son más efectivos.

Esta pregunta ya tiene una respuesta aquí:

El algoritmo de ordenación Heap Sort parece tener la peor complejidad de caso de O (nlogn) y usa O (1) espacio para la operación de clasificación.

Esto parece mejor que la mayoría de los algoritmos de clasificación. Entonces, ¿por qué uno no usaría Heap Sort siempre como un algoritmo de clasificación (y por qué la gente usa mecanismos de clasificación como Merge sort o Quick sort)?

Además, he visto a personas usar el término ''inestabilidad'' con el tipo Heap. ¿Qué implica eso?

Los algoritmos de clasificación estables mantienen el orden relativo de los registros con las mismas claves

Algunas aplicaciones como tener ese tipo de estabilidad, a la mayoría no le importa, por ejemplo, Google es tu amigo.

En cuanto a su afirmación de que "la gente usa mecanismos de clasificación como Merge sort o Quick sort", apostaría a que la mayoría de las personas usan lo que está incorporado en su lenguaje y no piensan demasiado en el algoritmo de clasificación. Aquellos que tienen su propia cuenta probablemente no hayan escuchado sobre el tipo de montón (la última es experiencia personal).

La última y más importante razón es que no todos van a querer un montón ordenado. Algunas personas quieren la lista ordenada. Si el jefe promedio de Joe Programmer dice "ordena esta lista", y Joe dice "¡Aquí está esta estructura de datos de montón de la que nunca has oído hablar, jefe!", La próxima revisión de desempeño de Joe no será tan buena.

No hay bala de plata...

Solo para mencionar otro argumento que no he visto aquí todavía:

Si su conjunto de datos es realmente enorme y no cabe en la memoria, el tipo de combinación funciona como un amuleto. Se usa con frecuencia en clusters donde el conjunto de datos puede abarcar cientos de máquinas.

The Heap Sort tiene la peor complejidad de caso de O(n log(n)) . Sin embargo, los estudios empíricos muestran que, en general, la Clasificación rápida (y otros algoritmos de clasificación) es considerablemente más rápida que la ordenación en pila, aunque su peor complejidad es O(n²) : http://www.cs.auckland.ac.nz/~jmor159/PLDS210/qsort3.html

Además, del artículo de clasificación rápida en Wikipedia:

El competidor más directo de quicksort es heapsort. El peor tiempo de ejecución de Heapsort es siempre O (n log n). Sin embargo, se supone que el heapsort es en promedio algo más lento que el quicksort estándar en el lugar. Esto todavía se debate y en la investigación, con algunas publicaciones que indican lo contrario. [13] [14] Introsort es una variante de quicksort que cambia a heapsort cuando se detecta un caso grave para evitar el peor tiempo de ejecución de la quicksort. Si se sabe de antemano que heapsort va a ser necesario, usarlo directamente será más rápido que esperar a que introsort cambie a él.

Sin embargo, la ordenación rápida nunca debe usarse en aplicaciones que requieren una garantía de tiempo de respuesta.

Fuente en : Quicksort vs heapsort

Una clasificación estable mantiene el orden relativo de los elementos que tienen la misma clave. Por ejemplo, imagine que su conjunto de datos contiene registros con una identificación de empleado y un nombre. El orden inicial es:

1, Jim 2, George 3, Jim 4, Sally 5, George

Quieres ordenar por nombre. Un tipo estable organizará los artículos en este orden:

2, George 5, George 1, Jim 3, Jim 4, Sally

Tenga en cuenta que los registros duplicados para "George" están en el mismo orden relativo que estaban en la lista inicial. Lo mismo con los dos registros de "Jim".

Un tipo inestable podría organizar los elementos como este:

5, George 2, George 1, Jim 3, Jim 4, Sally

Heapsort no es estable porque las operaciones en el montón pueden cambiar el orden relativo de elementos iguales. No todas las implementaciones de Quicksort son estables. Depende de cómo implemente la partición.

Aunque Heapsort tiene la peor complejidad de caso de O(n log(n)) , eso no cuenta toda la historia. En la implementación en el mundo real, hay factores constantes que el análisis teórico no tiene en cuenta. En el caso de Heapsort vs. Quicksort, resulta que hay formas (mediana de 5, por ejemplo) de hacer que los peores casos de Quicksort sean muy raros. Además, mantener un montón no es gratis.

Dado un conjunto con una distribución normal, Quicksort y Heapsort se ejecutarán en O(n log(n)) . Pero Quicksort se ejecutará más rápido porque sus factores constantes son más pequeños que los factores constantes para Heapsort. Para decirlo simplemente, la partición es más rápida que mantener el montón.