it-swarm-es.tech

¿Por qué quicksort es 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?

337

Quicksort tiene O (norte2) peor tiempo de ejecución y O (norteiniciar sesiónnorte) tiempo promedio de ejecución. Sin embargo, es superior a la clasificación combinada en muchos escenarios porque muchos factores influyen en el tiempo de ejecución de un algoritmo y, cuando se combinan todos, el orden se resuelve rápidamente.

En particular, el tiempo de ejecución de los algoritmos de clasificación, a menudo citado, se refiere al número de comparaciones o al número de intercambios necesarios para realizar la clasificación de los datos. De hecho, esta es una buena medida del 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 la memoria caché?) También juegan un papel importante en el hardware actual. En particular, Quicksort requiere poco espacio adicional y muestra una buena ubicación de caché, y esto hace que sea más rápido que la ordenación por fusión en muchos casos.

Además, es muy fácil evitar el peor tiempo de ejecución de Quicksort de O (norte2) casi en su totalidad mediante el uso de una elección adecuada del pivote, como seleccionarlo al azar (esta es una estrategia excelente).

En la práctica, muchas implementaciones modernas de quicksort (en particular, std::sort de libstdc ++ ’) son en realidad introsort , cuyo peor caso teórico es O (norteiniciar sesiónnorte), igual que la ordenación por fusión. Esto se logra al limitar la profundidad de la recursión y cambiar a un algoritmo diferente ( heapsort ) una vez que excede el registronorte.

251
Konrad Rudolph

Como muchas personas han notado, el rendimiento promedio de los casos para la ordenación rápida es más rápido que la combinación. Pero esto solo es cierto si está asumiendo un tiempo constante para acceder a cualquier parte de la memoria a pedido.

En RAM esta suposición generalmente no es tan mala (no siempre es así debido a los cachés, pero no es tan mala). Sin embargo, si su estructura de datos es lo suficientemente grande como para vivir en el disco, quicksort obtiene matado 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 mergesort hace.

Por lo tanto, si los datos deben ordenarse en el disco, realmente desea utilizar alguna variación en mergesort. (Por lo general, usted ordena las listas secundarias y luego comienza a combinarlas por encima de un umbral de tamaño).

Además, si tiene que hacer cualquier cosa con conjuntos de datos de ese tamaño, piense bien en cómo evitar las búsquedas en el disco. Por ejemplo, esta es la razón por la que es un consejo estándar que elimine los índices antes de realizar grandes cargas de datos en las bases de datos y luego vuelva a generar el índice más adelante. Mantener el índice durante la carga significa buscar constantemente el disco. Por el contrario, si elimina los índices, entonces la base de datos puede reconstruir el índice, primero clasificando la información con la que se tratará (¡por supuesto! (Los BTREE se mantienen naturalmente en orden, por lo que puede cargar uno de un conjunto de datos ordenados con pocas búsquedas en el disco).

Ha habido varias ocasiones en las que la comprensión de cómo evitar las búsquedas de discos me ha permitido hacer que los trabajos de procesamiento de datos tomen horas en lugar de días o semanas.

270
user11318

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

QuickSort es más popular porque:

  1. Está en el lugar (MergeSort requiere una memoria adicional lineal a la cantidad de elementos a clasificar).
  2. Tiene una pequeña constante oculta.
87
Dark Shikari

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

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

Sí, Quicksort con triple partición es probablemente uno de los mejores algoritmos de clasificación de propósito general, pero no hay que olvidar el hecho de que la clasificación "Rápida" suena mucho más poderosa que la clasificación "Combinar".

31
Ash

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

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

15
Javier

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 el orden rápido es ... rápido =)

Todo tipo de algoritmos tienen sus altibajos. Vea Artículo de Wikipedia para los algoritmos de clasificación para una buena visión general.

8
Antti Rasinen

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 n (nlogn). Mergesort es un tipo estable, a diferencia de quicksort y heapsort, y se puede adaptar fácilmente para operar en listas enlazadas y listas muy grandes almacenadas en medios de acceso lento, como el almacenamiento en disco o el almacenamiento conectado a la red. Si bien Quicksort puede escribirse para operar en listas enlazadas, a menudo sufrirá de malas opciones de pivote sin acceso aleatorio. La principal desventaja de mergesort es que, cuando se opera en arreglos, requiere Θ (n) espacio auxiliar 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 al operar en listas vinculadas, la combinación solo requiere una pequeña cantidad de almacenamiento auxiliar constante).

7
gnobal

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

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

Usted declaró que ellos "Ambos son O(nlogn) [...]". Esto está mal. "Quicksort utiliza alrededor de n ^ 2/2 comparaciones en el peor de los casos." 1 .

Sin embargo, la propiedad más importante de acuerdo con mi experiencia es la fácil implementación del acceso secuencial que puede utilizar al ordenar los lenguajes de programación con el paradigma imperativo.

1 Sedgewick, Algoritmos

7
Roman Glass

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 se desempeñe tan mal como O (n2).

Se garantiza que Heapsort se ejecute en O (n * ln (n)) y solo requiere almacenamiento adicional finito. Pero hay muchas citas de pruebas del mundo real que muestran que Heapsort es significativamente más lento que el promedio rápido.

6
Niyaz

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 quicksort no tienen. En el peor de los casos, son la misma cantidad de tiempo algorítmico, pero mergesort requiere más almacenamiento.

5
Mat Mannion

Me gustaría agregar a las grandes respuestas existentes algunos cálculos matemáticos sobre el rendimiento de QuickSort cuando se desvían del mejor de los casos y qué tan probable es, lo cual espero que 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 manera 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 de todos los mismos valores se ordenará n ^ 2 en un QuickSort de partición Vanilla 2 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 de todos los mismos valores en O(n) time. Por lo tanto, usar una implementación de este tipo significa que una entrada con un número pequeño de claves realmente mejora el tiempo de rendimiento y ya no es una preocupación.

2) La selección de pivote extremadamente mala puede causar el peor desempeño de caso. En un caso ideal, el pivote siempre será tal que el 50% de los datos sea más pequeño y el 50% que los datos sean más grandes, 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 O (n * logn) tiempo.

¿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 de manera consistente, de manera que el 75% de los datos se encuentran 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 la 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 lo ideal.

¿Qué tan rápido empeora esto?

No muy rápido hasta que la elección de pivote se pone (constantemente) muy mal:

  • 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 largo

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

En una implementación ingenua de QuickSort, los casos como una matriz ordenada (para pivote del primer elemento) o una matriz ordenada inversa (para el pivote del último 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 dinámica predecible pueden ser sometidas a ataques DoS por datos diseñados para producir la ejecución en el peor de los casos. Las implementaciones modernas evitan esto mediante una variedad de métodos, como la asignación aleatoria de los datos antes de la clasificación, la elección de la mediana de 3 índices elegidos al azar, etc. Con esta asignación al azar en la combinación, 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 sea pequeño.
  • Gran conjunto de datos. El peor de los casos es posible en teoría pero no en la práctica.

¿Cuán 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 25% -75% son "buenos" y los pivotes que están en el rango 0% -25% o 75% -100% como "malos". Si observas 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 suposiciones conservadoras (y falsas) para simplificar las matemáticas:

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

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

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

Distribuciones de probabilidad binomial puedo 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 golpeado por un rayo en el primer segundo que tarda en hacer clic en [SORT] que en ver que se ejecutan 5.000 elementos de ordenación lo que sea peor que 10 * caso ideal. Esta posibilidad se vuelve más pequeña a medida que el conjunto de datos se hace más grande. Aquí hay algunos tamaños de matriz y sus posibilidades correspondientes de correr más de 10 * ideal:

  • Conjunto de 640 elementos: 10 ^ -13 (requiere 15 buenos puntos de pivote de los 60 intentos)
  • Conjunto de 5,000 elementos: 10 ^ -18 (requiere 22 buenos pivotes de 88 intentos)
  • Conjunto de 40,000 artículos: 10 ^ -23 (requiere 29 buenos pivotes 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 balance de la probabilidad restante está más cerca de lo ideal que de lo contrario.

Finalmente, como han mencionado otros, incluso estos casos absurdamente improbables pueden eliminarse cambiando a una clasificación de pila si la pila de recursión es demasiado profunda. Entonces, el TLDR es que, para las buenas implementaciones de QuickSort, el peor de los casos no existe realmente porque se diseñó y la ejecución se completa en el tiempo O (n * logn).

4
Lance Wisely

Quicksort NO es mejor que mergesort. Con O (n ^ 2) (el caso más desfavorable que ocurre raramente), quicksort es potencialmente mucho más lento que O(nlogn) de la ordenación de fusión. Quicksort tiene menos gastos generales, por lo que con computadoras pequeñas y lentas, es mejor. Pero las computadoras son tan rápidas hoy que la sobrecarga adicional de una combinación es insignificante, y el riesgo de una ordenación muy lenta es mucho mayor que la sobrecarga insignificante de una combinación en la mayoría de los casos.

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

4
xpda

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

3
Shantam Mittal

La respuesta se inclinaría levemente hacia la ordenación rápida ante cambios introducidos con DualPivotQuickSort para valores primitivos. Se utiliza 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 implementación de Java7 aquí - http://grepcode.com/file/repository.grepcode.com/Java/root/jdk/openjdk/7-b147/Java/util/Arrays.Java

Más impresionante lectura en DualPivotQuickSort - http://permalink.gmane.org/gmane.comp.Java.openjdk.core-libs.devel/2628

3
SSR

En la combinación de ordenación, el algoritmo general es:

  1. Ordenar la sub-matriz izquierda
  2. Ordenar la sub-matriz derecha
  3. Combinar los 2 sub-arreglos ordenados

En el nivel superior, la fusión de las 2 subarreglas 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. Así que 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 ordenació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 los elementos más grandes a la derecha
  3. Ordenar la subarray izquierda
  4. Ordenar la sub-matriz derecha

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 durante el resto del algoritmo.

Un nivel por debajo de eso, estás tratando con 2 subarreglos que tienen un tamaño combinado de N-1 (es decir, restar el punto de pivote anterior). Elige un punto de pivote para cada sub-matriz, que llega a 2 puntos de pivote adicionales.

Un nivel por debajo de eso, estás tratando con 4 subarreglos con tamaño combinado N-3, por las mismas razones que anteriormente.

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

La profundidad de su pila recursiva permanece aproximadamente igual (logN). Con la combinación de ordenación, siempre se trata de una combinación de elementos N, en cada nivel de la pila recursiva. Sin embargo, con el ordenamiento rápido, la cantidad de elementos con los que estás tratando disminuye a medida que avanzas en la pila. Por ejemplo, si observa la profundidad a 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 la combinación de ordenación, porque divide la matriz en 2 partes exactamente iguales cada vez, la profundidad recursiva es exactamente logN. En ordenamiento rápido, debido a que es poco probable que su punto de pivote esté exactamente en el centro de la matriz, la profundidad de su pila recursiva puede ser ligeramente mayor que logN. No he hecho los cálculos matemáticos para ver qué tan importante es este papel y el factor descrito anteriormente, que realmente juegan en la complejidad del algoritmo.

3
RvPr

Quicksort tiene una complejidad de casos promedio mejor, 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 que se ordenará, puede construir fácilmente un conjunto que tome la complejidad del peor caso posible de o (n ^ 2).

La complejidad promedio de los casos de Mergesort y la complejidad del caso más desfavorable son las mismas, y como tales no sufren el mismo problema. Esta propiedad de la combinación de ordenación también la convierte en la mejor opción para los sistemas en tiempo real, precisamente porque no hay casos patológicos que hagan que se ejecute mucho, mucho más lentamente.

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

2
Simon Johnson

Si bien ambos están en la misma clase de complejidad, eso no significa que ambos tengan el mismo tiempo de ejecución. Por lo general, Quicksort es más rápido que mergesort, solo porque es más fácil codificar una implementación ajustada y las operaciones que puede realizar son más rápidas. Esto se debe a que la ordenación rápida es generalmente más rápida que la gente lo usa en lugar de mergesort.

¡Sin embargo! Personalmente, a menudo utilizo mergesort o una variante de orden rápido que se degrada a mergesort cuando quicksort lo hace mal. Recuerda. Quicksort es solo O (n log n) en average . ¡El peor de los casos es O (n ^ 2)! Mergesort siempre es O (n log n). En los casos en los que el rendimiento o la capacidad de respuesta en tiempo real son una necesidad y sus datos de entrada podrían provenir de una fuente maliciosa, no debe usar una ordenación rápida.

2
DJ Capelis

La clasificación rápida es el caso más desfavorable O (n ^ 2), sin embargo, el caso promedio de forma consistente supera la clasificación combinada. Cada algoritmo es O (nlogn), pero debe recordar que cuando se habla de Big O, dejamos de lado los factores de menor complejidad. La ordenación rápida tiene mejoras significativas sobre la ordenación de mezcla cuando se trata de factores constantes.

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

Información extra:

El peor de los casos 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 está 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, la elección de 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 pobre es de 0.5 * n. En base a esta probabilidad, la clasificación rápida es eficiente para el caso promedio (y típico).

2
Wade Anderson

¿Por qué Quicksort es bueno?

  • QuickSort toma N ^ 2 en el caso más desfavorable y NlogN. El peor de los casos ocurre cuando se ordenan los datos. Esto se puede mitigar mediante una orden aleatoria antes de comenzar la clasificación.
  • QuickSort no toma memoria extra que se toma por la ordenación de fusión.
  • Si el conjunto de datos es grande y hay elementos idénticos, la complejidad de Quicksort se reduce al usar una partición de 3 vías. Más el no de elementos idénticos mejor el género. Si todos los elementos son idénticos, se ordenan en tiempo lineal. [Esta es la implementación por defecto en la mayoría de las bibliotecas]

¿Es Quicksort siempre mejor que Mergesort?

En realidad no.

  • Mergesort es estable pero Quicksort no lo es. Entonces, si necesita estabilidad en la salida, usaría Mergesort. La estabilidad es necesaria en muchas aplicaciones prácticas.
  • La memoria es barata hoy en día. Por lo tanto, si la memoria adicional utilizada por Mergesort no es crítica para su aplicación, no hay ningún problema en utilizar 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 una sobrecarga de memoria, por lo tanto, agregar una pequeña sobrecarga para Mergesort puede no ser un problema para el punto de vista del rendimiento.

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

2

Cuando experimenté con ambos algoritmos de clasificación, al contar el número de llamadas recursivas, el ordenamiento rápido siempre tiene menos llamadas recursivas que la combinación. Se debe a que quicksort tiene pivotes, y los pivotes no se incluyen en las siguientes llamadas recursivas. De esta manera, Quicksort puede llegar a un caso base recursivo más rápido que Mergesort.

2
Aldian Fazrihady

Pequeñas adiciones para clasificaciones rápidas y combinadas.

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 la comparación de enteros en la memoria del plano, el ordenamiento por combinación puede ser un algoritmo preferible.

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

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

1
minorlogic

Es difícil decirlo. Lo peor de MergeSort es n (log2n) -n + 1, que es preciso si n es igual a 2 ^ k (ya he probado esto). 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 de los casos de MergeSort es mejor que el mejor de QuickSort, ¿por qué usamos quicksort? Pero recuerde, MergeSort no está en su lugar, requiere 2n espacio memeroy. Y MergeSort también necesita hacer muchas copias de matriz, que nosotros no se incluye en el análisis del algoritmo. En una palabra, MergeSort es realmente más rápido que el de orden rápida, pero en realidad es necesario tener en cuenta el espacio de memoria, el costo de la copia de la matriz, la fusión es más lenta que la ordenación rápida. experimento donde me dieron 1000000 dígitos en Java por clase aleatoria, y tomó 2610ms por mergesort, 1370ms por quicksort.

1
Peter

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

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

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

Mis puntos de referencia en el procesador bastante moderno muestra lo siguiente:

Cuando la función de comparación es una función de devolución de llamada (como en qsort () implementación de libc), quicksort es más lenta que la combinación en un 15% en entradas aleatorias 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 la ordenación rápida supera a la combinación en un 25%.

Sin embargo, si su matriz (grande) tiene muy pocos valores únicos, la ordenación por fusión comienza a ganar más de lo que es el orden rápido 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, comparando cadenas, comparando muchas partes de una estructura en su mayoría llegando a un segundo-tercio "si" para hacer la diferencia), es probable que sea mejor. con la ordenación de fusión. Para tareas más sencillas, quicksort será más rápido.

Dicho esto, todo lo que se dijo 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 un ataque de un rayo que para ir N ^ 2 - Mergesort requiere espacio adicional

1
virco

En igualdad de condiciones, esperaría que la mayoría de la gente use lo que esté más convenientemente disponible, y eso suele ser qsort (3). Aparte de eso, se sabe que quicksort es muy rápido en arreglos, 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 una clasificación de cubeta. 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. (cuerdas y flotadores funcionan bien).

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

En otras noticias, los flotadores se pueden clasificar como enteros, pero después hay que convertir los números negativos.

Edición: En realidad, aquí hay una manera aún más cruel de ordenar los floats-as-integers: 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 ...

1
Anders Eurenius

Considere la complejidad tanto del tiempo como del espacio. Para la clasificación de mezcla: complejidad de tiempo: O(nlogn), complejidad de espacio: O (nlogn)

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

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

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

0
pankaj

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

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 combinación en la clasificación de fusión se puede implementar sin ningún espacio extra. Sin embargo, la asignación y la desasignación de espacio adicional para los arreglos tienen un efecto adverso en el tiempo de ejecución de la ordenación de combinación. La clasificación de fusión también favorece la lista enlazada, ya que los datos se acceden de forma secuencial, sin mucho acceso aleatorio a la memoria.

Por otro lado, la clasificación rápida requiere una gran cantidad de acceso aleatorio a la memoria y, con una matriz, podemos acceder directamente a la memoria sin necesidad de realizar ningún desplazamiento como lo requieren las listas vinculadas. También la clasificación rápida cuando se usa para arreglos tiene una buena localidad de referencia, ya que los arreglos se almacenan de forma contigua en la memoria.

A pesar de que la complejidad promedio de ambos algoritmos de clasificación es O (NlogN), por lo general las personas para tareas ordinarias usan una matriz para el almacenamiento, y por esa razón, la clasificación rápida debe ser el algoritmo de elección.

EDITAR: acabo de descubrir que la combinación de ordenación peor/mejor/caso avg siempre es nlogn, pero la ordenación rápida puede variar desde n2 (el peor caso cuando los elementos ya están ordenados) a nlogn (avg/mejor caso cuando el pivote siempre divide la matriz en dos mitades).

0
Saad