¿Por qué es quicksort mejor que mergesort?

Me hicieron esta pregunta durante una entrevista. Ambos son O (nlogn) y, sin embargo, la mayoría de las personas usan Quicksort en lugar de Mergesort. ¿Porqué es eso?

Quicksort tiene O ( n ² ) peor tiempo de ejecución y O ( n log n ) tiempo promedio de ejecución de casos. Sin embargo, es mejor combinar el orden en muchos escenarios porque muchos factores influyen en el tiempo de ejecución de un algoritmo y, cuando se combinan todos, gana la clasificación rápida.

En particular, el tiempo de ejecución a menudo citado de los algoritmos de clasificación se refiere a la cantidad de comparaciones o la cantidad de intercambios necesarios para realizar la clasificación de los datos. De hecho, esta es una buena medida de rendimiento, especialmente porque es independiente del diseño de hardware subyacente. Sin embargo, otras cosas, como la localidad de referencia (es decir, ¿leemos muchos elementos que probablemente están en caché?) También juegan un papel importante en el hardware actual. Quicksort en particular requiere poco espacio adicional y exhibe una buena ubicación de caché, y esto hace que sea más rápido que la fusión en muchos casos.

Además, es muy fácil evitar el tiempo de ejecución de O ( n ² ) en el peor de los casos de Quicksort casi por completo mediante el uso de una elección adecuada del pivote, como elegirlo al azar (esta es una estrategia excelente).

En la práctica, muchas implementaciones modernas de quicksort (en particular libstdc ++ 's std::sort) son en realidad introsort , cuyo peor caso teórico es O ( n log n ), igual que el tipo de fusión. Esto se logra limitando la profundidad de recursión y cambiando a un algoritmo diferente ( ordenamiento dinámico ) una vez que excede el log n .

Como muchas personas han notado, el rendimiento promedio de los casos para quicksort es más rápido que mergesort. Pero esto solo es cierto si está asumiendo un tiempo constante para acceder a cualquier pieza de memoria bajo demanda.

En RAM, este supuesto generalmente no es tan malo (no siempre es cierto debido a los cachés, pero no es tan malo). Sin embargo, si su estructura de datos es lo suficientemente grande como para vivir en el disco, entonces QuickSort es asesinado por el hecho de que su disco promedio hace algo así como 200 búsquedas aleatorias por segundo. Pero ese mismo disco no tiene problemas para leer o escribir megabytes por segundo de datos secuencialmente. Que es exactamente lo que hace mergesort.

Por lo tanto, si los datos deben clasificarse en el disco, realmente desea utilizar alguna variación en mergesort. (Generalmente, clasifica rápidamente las sublistas, luego comienza a fusionarlas por encima de un umbral de tamaño).

Además, si tiene que hacer algo con conjuntos de datos de ese tamaño, piense detenidamente cómo evitar las búsquedas en el disco. Por ejemplo, es por eso que es un consejo estándar que elimine los índices antes de realizar grandes cargas de datos en las bases de datos, y luego reconstruya el índice más tarde. Mantener el índice durante la carga significa buscar constantemente en el disco. Por el contrario, si suelta los índices, la base de datos puede reconstruir el índice al ordenar primero la información que se va a tratar (¡usando un mergesort, por supuesto!) Y luego cargarla en una estructura de datos BTREE para el índice. (Los BTREE se mantienen naturalmente en orden, por lo que puede cargar uno desde un conjunto de datos ordenado con pocas búsquedas en el disco).

En varias ocasiones, comprender cómo evitar las búsquedas de disco me ha permitido hacer que los trabajos de procesamiento de datos demoren horas en lugar de días o semanas.

En realidad, QuickSort es O (n ² ). Su tiempo promedio de ejecución de casos es O (nlog (n)), pero su peor caso es O (n ² ), que ocurre cuando lo ejecuta en una lista que contiene pocos elementos únicos. La aleatorización toma O (n). Por supuesto, esto no cambia su peor caso, solo evita que un usuario malintencionado haga que su clasificación tarde mucho tiempo.

QuickSort es más popular porque:

1. Está en su lugar (MergeSort requiere memoria adicional lineal para la cantidad de elementos que se ordenarán).
2. Tiene una pequeña constante oculta.

"y, sin embargo, la mayoría de la gente usa Quicksort en lugar de Mergesort. ¿Por qué es eso?"

Una razón psicológica que no se ha dado es simplemente que Quicksort tiene un nombre más inteligente. es decir, buen marketing.

Sí, Quicksort con partición triple es probablemente uno de los mejores algoritmos de ordenación de propósito general, pero no se puede superar el hecho de que la ordenación "rápida" suena mucho más poderosa que la ordenación "Fusionar".

Como otros han señalado, el peor caso de Quicksort es O (n ^ 2), mientras que merortort y heapsort permanecen en O (nlogn). En el caso promedio, sin embargo, los tres son O (nlogn); entonces son para la gran mayoría de los casos comparables.

Lo que hace que Quicksort sea mejor en promedio es que el ciclo interno implica comparar varios valores con uno solo, mientras que en los otros dos términos son diferentes para cada comparación. En otras palabras, Quicksort realiza la mitad de las lecturas que los otros dos algoritmos. En las CPU modernas, el rendimiento está fuertemente dominado por los tiempos de acceso, por lo que al final Quicksort termina siendo una excelente primera opción.

Me gustaría agregar que de los tres algoritmos mencionados hasta ahora (mergesort, quicksort y heap sort) solo mergesort es estable. Es decir, el orden no cambia para aquellos valores que tienen la misma clave. En algunos casos esto es deseable.

Pero, a decir verdad, en situaciones prácticas, la mayoría de las personas solo necesitan un buen rendimiento promedio y la clasificación rápida es ... rápida =)

Todos los algoritmos de clasificación tienen sus altibajos. Consulte el artículo de Wikipedia para ver los algoritmos de clasificación para obtener una buena descripción general.

De la entrada de Wikipedia en Quicksort :

Quicksort también compite con mergesort, otro algoritmo de ordenación recursiva pero con el beneficio del peor tiempo de ejecución Θ (nlogn). Mergesort es un tipo estable, a diferencia de Quicksort y Heapsort, y se puede adaptar fácilmente para operar en listas vinculadas y listas muy grandes almacenadas en medios de acceso lento como almacenamiento en disco o almacenamiento conectado a la red. Aunque se puede escribir quicksort para operar en listas vinculadas, a menudo sufrirá de malas opciones de pivote sin acceso aleatorio. La principal desventaja de mergesort es que, cuando se opera en matrices, requiere espacio auxiliar Θ (n) en el mejor de los casos, mientras que la variante de quicksort con partición en el lugar y recursión de cola usa solo espacio Θ (logn). (Tenga en cuenta que cuando se opera en listas vinculadas, mergesort solo requiere una pequeña cantidad constante de almacenamiento auxiliar).

Mu! Quicksort no es mejor, es adecuado para un tipo diferente de aplicación, que mergesort.

Vale la pena considerar Mergesort si la velocidad es esencial, no se puede tolerar el mal desempeño en el peor de los casos y hay espacio adicional disponible. 1

Dijiste que ellos «Ambos son O (nlogn) [...]». Esto está mal. «Quicksort utiliza aproximadamente n ^ 2/2 comparaciones en el peor de los casos». 1 .

Sin embargo, según mi experiencia, la propiedad más importante es la fácil implementación del acceso secuencial que puede usar mientras ordena al usar lenguajes de programación con el paradigma imperativo.

1 Sedgewick, Algoritmos

Quicksort es el algoritmo de clasificación más rápido en la práctica, pero tiene una serie de casos patológicos que pueden hacer que funcione tan mal como O (n2).

Heapsort está garantizado para ejecutarse en O (n * ln (n)) y solo requiere almacenamiento adicional finito. Pero hay muchas citas de pruebas del mundo real que muestran que el ordenamiento dinámico es significativamente más lento que el ordenamiento rápido en promedio.

La explicación de Wikipedia es:

Por lo general, quicksort es significativamente más rápido en la práctica que otros algoritmos Θ (nlogn), porque su bucle interno se puede implementar de manera eficiente en la mayoría de las arquitecturas, y en la mayoría de los datos del mundo real es posible tomar decisiones de diseño que minimizan la probabilidad de requerir tiempo cuadrático .

Ordenación rápida

Mergesort

Creo que también hay problemas con la cantidad de almacenamiento necesario para Mergesort (que es Ω (n)) que las implementaciones de ordenación rápida no tienen. En el peor de los casos, son la misma cantidad de tiempo algorítmico, pero mergesort requiere más almacenamiento.

Me gustaría agregar a las excelentes respuestas existentes algunas matemáticas sobre cómo se desempeña QuickSort cuando se desvía del mejor de los casos y la probabilidad de que eso sea, lo que espero ayude a las personas a comprender un poco mejor por qué el caso O (n ^ 2) no es real preocupación en las implementaciones más sofisticadas de QuickSort.

Fuera de los problemas de acceso aleatorio, hay dos factores principales que pueden afectar el rendimiento de QuickSort y ambos están relacionados con la forma en que el pivote se compara con los datos que se ordenan.

1) Un pequeño número de claves en los datos. Un conjunto de datos con el mismo valor se ordenará en n ^ 2 veces en un QuickSort de 2 particiones vainilla porque todos los valores, excepto la ubicación de pivote, se colocan en un lado cada vez. Las implementaciones modernas abordan esto mediante métodos como el uso de una clasificación de 3 particiones. Estos métodos se ejecutan en un conjunto de datos con el mismo valor en O (n) tiempo. Por lo tanto, el uso de dicha implementación significa que una entrada con un pequeño número de claves en realidad mejora el tiempo de rendimiento y ya no es una preocupación.

2) La selección de pivote extremadamente mala puede causar el peor de los casos. En un caso ideal, el pivote siempre será tal que el 50% de los datos es más pequeño y el 50% de los datos es más grande, de modo que la entrada se dividirá por la mitad durante cada iteración. Esto nos da n comparaciones y swaps veces log-2 (n) recursiones para el tiempo O (n * logn).

¿Cuánto afecta la selección de pivote no ideal al tiempo de ejecución?

Consideremos un caso en el que el pivote se elige consistentemente de tal manera que el 75% de los datos están en un lado del pivote. Todavía es O (n * logn) pero ahora la base del registro ha cambiado a 1 / 0.75 o 1.33. La relación en el rendimiento al cambiar de base siempre es una constante representada por log (2) / log (newBase). En este caso, esa constante es 2.4. Por lo tanto, esta calidad de elección de pivote tarda 2,4 veces más que la ideal.

¿Qué tan rápido empeora esto?

No muy rápido hasta que la opción de pivote se vuelva (consistentemente) muy mala:

• 50% en un lado: (caso ideal)
• 75% en un lado: 2.4 veces más largo
• 90% en un lado: 6.6 veces más largo
• 95% en un lado: 13.5 veces más largo
• 99% en un lado: 69 veces más

A medida que nos acercamos al 100% de un lado, la porción de registro de la ejecución se acerca a n y toda la ejecución se acerca asintóticamente a O (n ^ 2).

En una implementación ingenua de QuickSort, los casos como una matriz ordenada (para el pivote del primer elemento) o una matriz ordenada inversamente (para el último pivote del elemento) producirán de manera confiable un tiempo de ejecución O (n ^ 2) en el peor de los casos. Además, las implementaciones con una selección de pivote predecible pueden estar sujetas a ataques DoS por datos diseñados para producir la ejecución del peor de los casos. Las implementaciones modernas evitan esto mediante una variedad de métodos, como aleatorizar los datos antes de ordenarlos, elegir la mediana de 3 índices elegidos al azar, etc. Con esta aleatorización en la mezcla, tenemos 2 casos:

• Pequeño conjunto de datos. El peor de los casos es razonablemente posible, pero O (n ^ 2) no es catastrófico porque n es lo suficientemente pequeño como para que n ^ 2 también lo sea.
• Gran conjunto de datos. El peor de los casos es posible en teoría pero no en la práctica.

¿Qué tan probable es que veamos un desempeño terrible?

Las posibilidades son muy pequeñas. . Consideremos una especie de 5,000 valores:

Nuestra implementación hipotética elegirá un pivote utilizando una mediana de 3 índices elegidos al azar. Consideraremos que los pivotes que están en el rango del 25% -75% son "buenos" y los pivotes que están en el rango del 0% -25% o 75% -100% son "malos". Si observa la distribución de probabilidad utilizando la mediana de 3 índices aleatorios, cada recursión tiene una probabilidad de 11/16 de terminar con un buen pivote. Hagamos 2 supuestos conservadores (y falsos) para simplificar las matemáticas:

1. Los buenos pivotes siempre están exactamente en una división del 25% / 75% y funcionan en el caso ideal de 2.4 *. Nunca obtenemos una división ideal o una división mejor que 25/75.

2. Los malos pivotes son siempre el peor de los casos y esencialmente no contribuyen en nada a la solución.

Nuestra implementación de QuickSort se detendrá en n = 10 y cambiará a un tipo de inserción, por lo que requerimos 22 particiones pivote del 25% / 75% para dividir la entrada de valor de 5,000 hasta ese momento. (10 * 1.333333 ^ 22> 5000) O bien, requerimos 4990 pivotes en el peor de los casos. Tenga en cuenta que si acumulamos 22 pivotes buenos en cualquier momento , la clasificación se completará, por lo que el peor de los casos o cualquier cosa cercana requiere muy mala suerte. Si nos tomara 88 recursiones para lograr realmente los 22 buenos pivotes requeridos para ordenar a n = 10, eso sería 4 * 2.4 * caso ideal o aproximadamente 10 veces el tiempo de ejecución del caso ideal. ¿Cuán probable es que lo haría no logremos los 22 buenos pivotes requeridos después de 88 recursiones?

Las distribuciones de probabilidad binomiales pueden responder eso, y la respuesta es aproximadamente 10 ^ -18. (n es 88, k es 21, p es 0.6875) Su usuario tiene aproximadamente mil veces más probabilidades de ser alcanzado por un rayo en el 1 segundo que toma hacer clic en [CLASIFICAR] que ver que la clasificación de 5.000 elementos funciona peor de 10 * caso ideal. Esta posibilidad se reduce a medida que aumenta el conjunto de datos. Aquí hay algunos tamaños de matriz y sus posibilidades correspondientes de ejecutar más de 10 * ideal:

• Matriz de 640 elementos: 10 ^ -13 (requiere 15 buenos puntos de pivote de 60 intentos)
• Matriz de 5,000 artículos: 10 ^ -18 (requiere 22 pivotes buenos de 88 intentos)
• Matriz de 40,000 artículos: 10 ^ -23 (requiere 29 pivotes buenos de 116)

Recuerde que esto es con 2 supuestos conservadores que son peores que la realidad. Por lo tanto, el rendimiento real es aún mejor, y el equilibrio de la probabilidad restante está más cerca del ideal que no.

Finalmente, como otros han mencionado, incluso estos casos absurdamente inverosímiles se pueden eliminar cambiando a un montón si la pila de recursión es demasiado profunda. Entonces, el TLDR es que, para buenas implementaciones de QuickSort, el peor de los casos realmente no existe porque se ha diseñado y la ejecución se completa en tiempo O (n * logn).

¿Por qué Quicksort es bueno?

• QuickSort toma N ^ 2 en el peor de los casos y el caso promedio de NlogN. El peor de los casos ocurre cuando se ordenan los datos. Esto puede mitigarse mediante un aleatorio aleatorio antes de comenzar la clasificación.
• QuickSort no toma memoria adicional que se toma por tipo de fusión.
• Si el conjunto de datos es grande y hay elementos idénticos, la complejidad de Quicksort se reduce mediante el uso de la partición de 3 vías. Más el no de artículos idénticos mejor el tipo. Si todos los elementos son idénticos, se ordena en tiempo lineal. [Esta es la implementación predeterminada en la mayoría de las bibliotecas]

¿Quicksort siempre es mejor que Mergesort?

Realmente no.

• Mergesort es estable pero Quicksort no lo es. Entonces, si necesita estabilidad en la salida, usaría Mergesort. Se requiere estabilidad en muchas aplicaciones prácticas.
• La memoria es barata hoy en día. Entonces, si la memoria adicional utilizada por Mergesort no es crítica para su aplicación, no hay ningún daño al usar Mergesort.

Nota: en java, la función Arrays.sort () usa Quicksort para tipos de datos primitivos y Mergesort para tipos de datos de objetos. Debido a que los objetos consumen sobrecarga de memoria, por lo tanto, agregar un poco de sobrecarga para Mergesort puede no ser un problema para el punto de vista del rendimiento.

Referencia : Vea los videos de QuickSort de la Semana 3, Curso de Algoritmos de Princeton en Coursera

Quicksort NO es mejor que mergesort. Con O (n ^ 2) (el peor de los casos que rara vez ocurre), la clasificación rápida es potencialmente mucho más lenta que la O (nlogn) del tipo de fusión. Quicksort tiene menos sobrecarga, por lo que con computadoras pequeñas y lentas, es mejor. Pero las computadoras son tan rápidas hoy en día que la sobrecarga adicional de un mergesort es insignificante, y el riesgo de un quicksort muy lento supera con creces la sobrecarga insignificante de un mergesort en la mayoría de los casos.

Además, un mergesort deja elementos con claves idénticas en su orden original, un atributo útil.

La respuesta se inclinaría ligeramente hacia wrt de ordenación rápida a los cambios generados con DualPivotQuickSort para valores primitivos. Se usa en JAVA 7 para ordenar en java.util.Arrays

It is proved that for the Dual-Pivot Quicksort the average number of
comparisons is 2*n*ln(n), the average number of swaps is 0.8*n*ln(n),
whereas classical Quicksort algorithm has 2*n*ln(n) and 1*n*ln(n)
respectively. Full mathematical proof see in attached proof.txt
and proof_add.txt files. Theoretical results are also confirmed
by experimental counting of the operations.

Puede encontrar la implicación de JAVA7 aquí: http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7-b147/java/util/Arrays.java

Lecturas impresionantes adicionales en DualPivotQuickSort - http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628

En merge-sort, el algoritmo general es:

1. Ordenar el subconjunto izquierdo
2. Ordenar la submatriz correcta
3. Combinar las 2 sub-matrices ordenadas

En el nivel superior, fusionar las 2 sub-matrices ordenadas implica tratar con N elementos.

Un nivel por debajo de eso, cada iteración del paso 3 implica tratar con elementos N / 2, pero debe repetir este proceso dos veces. Entonces todavía estás tratando con 2 * N / 2 == N elementos.

Un nivel por debajo de eso, está fusionando 4 * N / 4 == N elementos, y así sucesivamente. Cada profundidad en la pila recursiva implica fusionar el mismo número de elementos, en todas las llamadas para esa profundidad.

Considere el algoritmo de clasificación rápida en su lugar:

1. Elige un punto de pivote
2. Coloque el punto de pivote en el lugar correcto de la matriz, con todos los elementos más pequeños a la izquierda y elementos más grandes a la derecha
3. Ordenar el subarreglo izquierdo
4. Ordenar el subarreglo derecho

En el nivel superior, se trata de una matriz de tamaño N. Luego, elige un punto de pivote, lo coloca en su posición correcta y luego puede ignorarlo por completo para el resto del algoritmo.

Un nivel por debajo de eso, se trata de 2 sub-matrices que tienen un tamaño combinado de N-1 (es decir, restar el punto de pivote anterior). Elige un punto de pivote para cada subconjunto, que viene hasta 2 puntos de pivote adicionales.

Un nivel por debajo de eso, se trata de 4 subconjuntos con tamaño combinado N-3, por las mismas razones que arriba.

Luego N-7 ... Luego N-15 ... Luego N-32 ...

La profundidad de su pila recursiva permanece aproximadamente igual (logN). Con merge-sort, siempre se trata de una fusión de elementos N, en cada nivel de la pila recursiva. Sin embargo, con la ordenación rápida, la cantidad de elementos con los que está tratando disminuye a medida que avanza en la pila. Por ejemplo, si observa la profundidad a la mitad de la pila recursiva, el número de elementos con los que está tratando es N - 2 ^ ((logN) / 2)) == N - sqrt (N).

Descargo de responsabilidad: en merge-sort, dado que divide la matriz en 2 trozos exactamente iguales cada vez, la profundidad recursiva es exactamente logN. En la ordenación rápida, dado que es poco probable que su punto de pivote esté exactamente en el medio de la matriz, la profundidad de su pila recursiva puede ser ligeramente mayor que logN. No he hecho los cálculos para ver qué tan importante es este factor y el factor descrito anteriormente en la complejidad del algoritmo.

A diferencia de Merge Sort, Quick Sort no utiliza un espacio auxiliar. Mientras que Merge Sort usa un espacio auxiliar O (n). Pero Merge Sort tiene la complejidad de tiempo en el peor de los casos de O (nlogn), mientras que la peor complejidad de Quick Sort es O (n ^ 2), que ocurre cuando la matriz ya está ordenada.

Quicksort tiene una mejor complejidad de caso promedio, pero en algunas aplicaciones es la elección incorrecta. Quicksort es vulnerable a ataques de denegación de servicio. Si un atacante puede elegir la entrada a ordenar, puede construir fácilmente un conjunto que tome la peor complejidad de tiempo de o (n ^ 2).

La complejidad del caso promedio de Mergesort y la peor complejidad del caso son las mismas, y como tal no sufren el mismo problema. Esta propiedad de tipo de fusión también la convierte en la mejor opción para sistemas en tiempo real, precisamente porque no hay casos patológicos que hagan que funcione mucho, mucho más lento.

Soy un fanático más grande de Mergesort que de Quicksort, por estas razones.

Eso es difícil de decir. Lo peor de MergeSort es n (log2n) -n + 1, que es exacto si n es igual a 2 ^ k (ya lo he probado). Y para cualquier n, está entre (n lg n - n + 1) y (n lg n + n + O (lg n)). Pero para quickSort, lo mejor es nlog2n (también n es igual a 2 ^ k). Si divide Mergesort por quickSort, es igual a uno cuando n es infinito. es como si el peor caso de MergeSort fuera mejor que el mejor caso de QuickSort, ¿por qué usamos quicksort? Pero recuerde, MergeSort no está en su lugar, requiere 2n de espacio de memero y MergeSort también necesita hacer muchas copias de matriz, que nosotros no incluir en el análisis del algoritmo. En una palabra, MergeSort es realmente más faseter que quicksort en theroy, pero en realidad necesita tener en cuenta el espacio de memoria, el costo de la copia de la matriz, la fusión es más lenta que la clasificación rápida. experimento donde me dieron 1000000 dígitos en Java por clase aleatoria,y tomó 2610ms por mergesort, 1370ms por quicksort.

La clasificación rápida es el peor de los casos O (n ^ 2), sin embargo, el caso promedio consistentemente realiza una clasificación de fusión. Cada algoritmo es O (nlogn), pero debe recordar que cuando hablamos de Big O dejamos de lado los factores de menor complejidad. La clasificación rápida tiene mejoras significativas sobre la clasificación de fusión cuando se trata de factores constantes.

La ordenación por fusión también requiere memoria O (2n), mientras que la ordenación rápida puede realizarse en su lugar (solo requiere O (n)). Esta es otra razón por la que la ordenación rápida generalmente se prefiere a la ordenación por fusión.

Información extra:

El peor caso de ordenación rápida ocurre cuando el pivote está mal elegido. Considere el siguiente ejemplo:

[5, 4, 3, 2, 1]

Si se elige el pivote como el número más pequeño o más grande del grupo, la ordenación rápida se ejecutará en O (n ^ 2). La probabilidad de elegir el elemento que se encuentra en el 25% más grande o más pequeño de la lista es 0.5. Eso le da al algoritmo una probabilidad de 0.5 de ser un buen pivote. Si empleamos un algoritmo de elección de pivote típico (por ejemplo, elegir un elemento aleatorio), tenemos 0.5 posibilidades de elegir un buen pivote para cada elección de un pivote. Para colecciones de gran tamaño, la probabilidad de elegir siempre un pivote deficiente es 0.5 * n. En base a esta probabilidad, la ordenación rápida es eficiente para el caso promedio (y típico).

Esta es una pregunta bastante antigua, pero como he tratado con ambas recientemente, aquí están mis 2c:

Combinar las necesidades de clasificación en promedio ~ N log N comparaciones. Para arreglos ya ordenados (casi) ordenados, esto se reduce a 1/2 N log N, ya que al fusionar nosotros (casi) siempre seleccionamos la parte "izquierda" 1/2 N de veces y luego simplemente copiamos elementos 1/2 N derechos. Además, puedo especular que la entrada ya ordenada hace que el predictor de rama del procesador brille pero adivinando casi todas las ramas correctamente, evitando así las paradas de la tubería.

La clasificación rápida en promedio requiere ~ 1.38 N log N comparaciones. No se beneficia mucho de una matriz ya ordenada en términos de comparaciones (sin embargo, lo hace en términos de intercambios y probablemente en términos de predicciones de rama dentro de la CPU).

Mis puntos de referencia en un procesador bastante moderno muestran lo siguiente:

Cuando la función de comparación es una función de devolución de llamada (como en la implementación de qsort () libc), quicksort es más lento que mergesort en un 15% en la entrada aleatoria y en un 30% para una matriz ya ordenada para enteros de 64 bits.

Por otro lado, si la comparación no es una devolución de llamada, mi experiencia es que quicksort supera a mergesort en hasta un 25%.

Sin embargo, si su matriz (grande) tiene muy pocos valores únicos, la ordenación por fusión comienza a ganar sobre la clasificación rápida en cualquier caso.

Entonces, tal vez el resultado final sea: si la comparación es costosa (por ejemplo, la función de devolución de llamada, la comparación de cadenas, la comparación de muchas partes de una estructura en su mayoría llegando a un "si" de segundo a tercio para marcar la diferencia), lo más probable es que usted sea mejor con fusión tipo. Para tareas más simples, quicksort será más rápido.

Dicho esto, todo lo dicho anteriormente es cierto: - Quicksort puede ser N ^ 2, pero Sedgewick afirma que una buena implementación aleatoria tiene más posibilidades de que una computadora realice una operación para ser alcanzada por un rayo que ir N ^ 2 - Mergesort requiere espacio adicional

Cuando experimenté con ambos algoritmos de clasificación, contando el número de llamadas recursivas, quicksort consistentemente tiene menos llamadas recursivas que mergesort. Esto se debe a que quicksort tiene pivotes, y los pivotes no se incluyen en las próximas llamadas recursivas. De esta forma, quicksort puede alcanzar el caso base recursivo más rápido que mergesort.

Esta es una pregunta común que se hace en las entrevistas que, a pesar del mejor desempeño en el peor de los casos, la clasificación rápida se considera mejor que la clasificación combinada, especialmente para una gran entrada. Hay ciertas razones por las cuales QuickSort es mejor:

1- Espacio auxiliar: la clasificación rápida es un algoritmo de clasificación en el lugar. La clasificación en el lugar significa que no se necesita espacio de almacenamiento adicional para realizar la clasificación. La ordenación por fusión, por otro lado, requiere una matriz temporal para fusionar las matrices ordenadas y, por lo tanto, no está en su lugar.

2- Peor caso: el peor caso de clasificación rápida O(n^2)se puede evitar mediante el uso de clasificación rápida aleatoria. Se puede evitar fácilmente con alta probabilidad eligiendo el pivote correcto. La obtención de un comportamiento de caso promedio al elegir el elemento pivote correcto hace que improvise el rendimiento y se vuelva tan eficiente como el tipo de combinación.

3- Localidad de referencia: Quicksort, en particular, exhibe una buena ubicación de caché y esto hace que sea más rápido que la fusión en muchos casos, como en el entorno de memoria virtual.

4- Recurrencia de cola : QuickSort es recursiva de cola, mientras que la clasificación de fusión no lo es. Una función recursiva de cola es una función donde la llamada recursiva es lo último que ejecuta la función. Las funciones recursivas de cola se consideran mejores que las funciones recursivas no de cola, ya que el compilador puede optimizar la recursividad de cola.

Si bien ambos están en la misma clase de complejidad, eso no significa que ambos tengan el mismo tiempo de ejecución. Quicksort suele ser más rápido que mergesort, solo porque es más fácil codificar una implementación estricta y las operaciones que realiza pueden ir más rápido. Es porque ese ordenamiento rápido es generalmente más rápido que las personas lo usan en lugar de combinar.

¡Sin embargo! Personalmente, a menudo usaré mergesort o una variante de quicksort que se degrada a mergesort cuando quicksort funciona mal. Recuerda. Quicksort es solo O (n log n) en promedio . ¡Su peor caso es O (n ^ 2)! Mergesort es siempre O (n log n). En los casos en los que el rendimiento o la capacidad de respuesta en tiempo real son imprescindibles y sus datos de entrada pueden provenir de una fuente maliciosa, no debe usar el ordenamiento rápido simple.

En igualdad de condiciones, esperaría que la mayoría de la gente use lo que esté más convenientemente disponible, y eso tiende a ser qsort (3). Aparte de eso, se sabe que quicksort es muy rápido en matrices, al igual que mergesort es la opción común para las listas.

Lo que me pregunto es por qué es tan raro ver radix o tipo de cubo. Son O (n), al menos en listas vinculadas y todo lo que se necesita es algún método para convertir la clave en un número ordinal. (las cuerdas y los flotadores funcionan bien).

Creo que la razón tiene que ver con cómo se enseña la informática. Incluso tuve que demostrarle a mi profesor en el análisis de algoritmos que de hecho era posible ordenar más rápido que O (n log (n)). (Tenía la prueba de que no se puede ordenar por comparación más rápido que O (n log (n)), lo cual es cierto).

En otras noticias, los flotantes pueden clasificarse como enteros, pero luego debe cambiar los números negativos.

Editar: en realidad, aquí hay una forma aún más viciosa de ordenar flotantes como enteros: http://www.stereopsis.com/radix.html . Tenga en cuenta que el truco de cambio de bits se puede utilizar independientemente del algoritmo de clasificación que utilice realmente ...

Pequeñas adiciones a los tipos de fusión rápida vs.

También puede depender del tipo de elementos de clasificación. Si el acceso a los elementos, el intercambio y las comparaciones no son operaciones simples, como comparar enteros en la memoria plana, entonces el ordenamiento por fusión puede ser un algoritmo preferible.

Por ejemplo, clasificamos los elementos utilizando el protocolo de red en el servidor remoto.

Además, en contenedores personalizados como "lista vinculada", no hay beneficio de la ordenación rápida.
1. Combine la clasificación en la lista vinculada, no necesita memoria adicional. 2. El acceso a elementos en ordenación rápida no es secuencial (en memoria)

La clasificación rápida es un algoritmo de clasificación en el lugar, por lo que es más adecuado para matrices. La ordenación por fusión, por otro lado, requiere un almacenamiento adicional de O (N), y es más adecuada para listas vinculadas.

A diferencia de las matrices, en la lista de Me gusta podemos insertar elementos en el medio con O (1) espacio y O (1) tiempo, por lo tanto, la operación de fusión en el orden de fusión se puede implementar sin ningún espacio adicional. Sin embargo, la asignación y desasignación de espacio adicional para matrices tiene un efecto adverso en el tiempo de ejecución de la ordenación por fusión. La ordenación por fusión también favorece la lista vinculada ya que se accede a los datos secuencialmente, sin mucho acceso aleatorio a la memoria.

Por otro lado, la ordenación rápida requiere mucho acceso aleatorio a la memoria y con una matriz podemos acceder directamente a la memoria sin tener que atravesar como lo requieren las listas vinculadas. También la ordenación rápida cuando se usa para matrices tiene una buena localidad de referencia ya que las matrices se almacenan contiguamente en la memoria.

Aunque la complejidad promedio de ambos algoritmos de clasificación es O (NlogN), generalmente las personas para tareas ordinarias usan una matriz para el almacenamiento, y por esa razón la clasificación rápida debería ser el algoritmo de elección.

EDITAR: Acabo de descubrir que la combinación de clasificación peor / mejor / promedio de casos siempre es nlogn, pero la clasificación rápida puede variar de n2 (peor caso cuando los elementos ya están ordenados) a nlogn (promedio / mejor caso cuando pivot siempre divide la matriz en dos mitades).

Considere la complejidad de tiempo y espacio ambos. Para Combinar clasificación: Complejidad de tiempo: O (nlogn), Complejidad de espacio: O (nlogn)

Para Clasificación rápida: Complejidad de tiempo: O (n ^ 2), Complejidad de espacio: O (n)

Ahora, ambos ganan en un escenario cada uno. Pero, utilizando un pivote aleatorio, casi siempre puede reducir la complejidad del tiempo de ordenación rápida a O (nlogn).

Por lo tanto, se prefiere la clasificación rápida en muchas aplicaciones en lugar de la combinación.

En c / c ++ land, cuando no uso los contenedores stl, tiendo a usar quicksort, porque está integrado en el tiempo de ejecución, mientras que mergesort no lo está.

Así que creo que en muchos casos, es simplemente el camino de menor resistencia.

Además, el rendimiento puede ser mucho mayor con la ordenación rápida, para los casos en que todo el conjunto de datos no cabe en el conjunto de trabajo.

Una de las razones es más filosófica. Quicksort es la filosofía Top-> Down. Con n elementos para ordenar, hay n! posibilidades Con 2 particiones de m & nm que son mutuamente excluyentes, el número de posibilidades disminuye en varios órdenes de magnitud. ¡metro! * (nm)! es más pequeño en varias órdenes que n! solo. imagina 5! vs 3! * 2 !. 5! Tiene 10 veces más posibilidades que 2 particiones de 2 y 3 cada una. y extrapolar a 1 millón de factorial frente a 900K! * 100K! vs. Entonces, en lugar de preocuparse por establecer un orden dentro de un rango o una partición, simplemente establezca el orden a un nivel más amplio en las particiones y reduzca las posibilidades dentro de una partición. Cualquier orden establecido anteriormente dentro de un rango se verá afectado más adelante si las particiones no son mutuamente excluyentes.

Cualquier enfoque de orden de abajo hacia arriba, como la clasificación de fusión o la clasificación de montón, es como el enfoque de un trabajador o empleado donde uno comienza a comparar a un nivel microscópico temprano. Pero este orden se perderá tan pronto como se encuentre un elemento entre ellos más adelante. Estos enfoques son muy estables y extremadamente predecibles, pero hacen una cierta cantidad de trabajo extra.

La clasificación rápida es como un enfoque de gestión en el que uno no está inicialmente preocupado por ningún pedido, solo por cumplir un criterio amplio sin tener en cuenta el orden. Luego, las particiones se reducen hasta obtener un conjunto ordenado. El verdadero desafío en Quicksort es encontrar una partición o criterio en la oscuridad cuando no sabes nada acerca de los elementos para ordenar. Es por eso que necesitamos gastar un poco de esfuerzo para encontrar un valor medio o elegir 1 al azar o algún enfoque arbitrario "de gestión". Encontrar una mediana perfecta puede requerir una cantidad considerable de esfuerzo y lleva a un enfoque estúpido de abajo hacia arriba nuevamente. Entonces Quicksort dice que solo debe elegir un pivote aleatorio y esperar que esté en algún lugar en el medio o haga algún trabajo para encontrar una mediana de 3, 5 o algo más para encontrar una mejor mediana, pero no planee ser perfecto y no ' No pierdas el tiempo en pedidos iniciales. Eso parece funcionar bien si tiene suerte o, a veces, se degrada a n ^ 2 cuando no obtiene una mediana, pero simplemente se arriesga. De cualquier forma, los datos son aleatorios. Derecha. Por lo tanto, estoy más de acuerdo con el enfoque lógico de arriba a abajo de quicksort y resulta que la posibilidad que tiene sobre la selección de pivote y las comparaciones que guarda antes parece funcionar mejor más veces que cualquier enfoque de abajo hacia arriba estable meticuloso y completo como tipo de fusión Pero Las comparaciones que guarda antes parecen funcionar mejor más veces que cualquier enfoque de fondo -> arriba estable meticuloso y completo como el tipo de fusión. Pero Las comparaciones que guarda antes parecen funcionar mejor más veces que cualquier enfoque de fondo -> arriba estable meticuloso y completo como el tipo de fusión. Pero