algorithm sorting language-agnostic quicksort mergesort

algorithm - ¿Por qué quicksort es mejor que mergesort?



sorting language-agnostic (27)

"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".

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?

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); por lo 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.

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

En la 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, entonces Quicksort muere por el hecho de que su disco promedio realiza aproximadamente 200 búsquedas aleatorias por segundo. Pero ese mismo disco no tiene problemas para leer o escribir megabytes por segundo de datos de forma secuencial. 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, ordena las sublistas y luego comienza a combinarlas por encima de un umbral de tamaño).

Además, si tiene que hacer algo 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 descarte los índices antes de realizar grandes cargas de datos en las bases de datos y luego reconstruya el índice más adelante. Mantener el índice durante la carga significa buscar constantemente el disco. Por el contrario, si elimina los índices, la base de datos puede reconstruir el índice al ordenar primero la información con la que se tratará (¡por supuesto, mediante una combinación) 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 de un conjunto de datos ordenados con pocas búsquedas en el disco).

Ha habido varias ocasiones en 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.

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 esa manera, Quicksort puede llegar a un caso base recursivo más rápido que Mergesort.

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 worst (nlogn). Mergesort es un tipo estable, a diferencia de quicksort y heapsort, y puede adaptarse fácilmente para operar en listas enlazadas y en 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 constante de almacenamiento auxiliar).

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 arriba.

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 la ordenación rápida, 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 ordenación rápida, 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.

En realidad, QuickSort es O (n 2 ). Su tiempo promedio de ejecución del caso es O (nlog (n)), pero su peor caso es O (n 2 ), 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, 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 al número de elementos a clasificar).
  2. Tiene una pequeña constante oculta.

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 fusión cuando se trata de factores constantes.

La clasificación de fusión también requiere memoria O (2n), 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 0.5 * n. En base a esta probabilidad, la clasificación rápida es eficiente para el caso promedio (y típico).

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.

La respuesta se inclinaría ligeramente hacia la ordenación rápida ante cambios introducidos con DualPivotQuickSort para valores primitivos. Se utiliza en JAVA 7 para clasificar 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 lecturas impresionantes en DualPivotQuickSort - http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628

Me gustaría agregar a las grandes respuestas existentes algunos cálculos matemáticos sobre cómo se comporta QuickSort cuando se desvía 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 clasifican.

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 2 particiones de 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 de todos los mismos valores en tiempo O (n). 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á a 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. Así que esta calidad de elección de pivote lleva 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 aleatorizar los datos antes de ordenarlos, elegir la mediana de 3 índices elegidos al azar, etc. Con esta aleatorización 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.

¿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 25% -75% son "buenos" y los pivotes que están en el rango 0% -25% o 75% -100% como "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 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 momento , la clasificación se completará, por lo que el peor de los casos o cualquier cosa cercana requerirá una 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 no logremos los 22 buenos pivotes requeridos después de 88 recursiones?

Las distribuciones de probabilidad binomial pueden responder a 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 se tarda en hacer clic en [SORT] que en ver que la clasificación de 5,000 elementos es peor de 10 * caso ideal. Esta posibilidad se reduce a medida que el conjunto de datos se hace más grande. Aquí hay algunos tamaños de matriz y sus posibilidades correspondientes de ejecutar 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 es más cercano al ideal que no.

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).

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 el artículo de Wikipedia para los algoritmos de clasificación para una buena visión general.

Quicksort NO es mejor que mergesort. Con O (n ^ 2) (el caso más desfavorable que ocurre raramente), la ordenación rápida es potencialmente mucho más lenta que la O (nlogn) del tipo de combinació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 supera con creces 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.

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.

Quicksort tiene O ( n 2 ) tiempo de ejecución de peor caso y O ( n log n ) tiempo de ejecución promedio de caso. Sin embargo, es superior a la clasificación combinada en muchos escenarios, ya que muchos factores influyen en el tiempo de ejecución de un algoritmo y, cuando se combinan todos, la ordenación rápida gana.

En particular, el tiempo de ejecución de los algoritmos de clasificación a menudo 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 caché?) También juegan un papel importante en el hardware actual. En particular, Quicksort requiere poco espacio adicional y exhibe una buena ubicación de caché, y esto lo hace más rápido que la ordenación por fusión en muchos casos.

Además, es muy fácil evitar el tiempo de ejecución de O ( n 2 ) en el peor de los casos de quicksort 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, introsort std::sort libstdc ++) son en realidad introsort , cuyo peor caso teórico es O ( n log n ), igual que la ordenación de combinación. Esto se logra al limitar la profundidad de la recursión y cambiar a un algoritmo diferente ( heapsort ) una vez que supera el registro n .

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 de peor caso de tiempo (o ^ 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.

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 quicksort que se degrada a mergesort cuando quicksort lo hace mal. Recuerda. Quicksort es solo O (n log n) en promedio . ¡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 sean indispensables y sus datos de entrada provengan de una fuente maliciosa, no debe utilizar una ordenación rápida.

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. Mu!

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

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.

Mu! Sedgewick, Algoritmos

¿Por qué Quicksort es bueno?

  • QuickSort toma N ^ 2 en el peor de los casos y el promedio de NlogN. El peor caso ocurre cuando se ordenan los datos. Esto se puede mitigar mediante una orden aleatoria antes de iniciar la clasificación.
  • QuickSort no toma memoria extra que es tomada 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?

Realmente 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 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, Princeton Algorithms Course en Coursera

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

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

Además, el rendimiento puede ser mucho mayor con una ordenación rápida, en los casos en que el conjunto de datos no se ajusta al conjunto de trabajo.

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 los 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 de fusión comienza a ganar más de lo 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 al 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 ir N ^ 2 - Mergesort requiere espacio adicional

Pequeñas adiciones a las clasificaciones de vs vs rápido.

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, entonces la clasificación de mezcla puede ser un algoritmo preferible.

Por ejemplo, ordenamos los elementos usando 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. Combinar 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)

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.

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 la clase de radix o balde. 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 demostrar a mi profesor en el análisis de algoritmos que era posible clasificar más rápido que O (n log (n)). (Tenía la prueba de que no se puede comparar 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 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 ...

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 matriz, la fusión es más lenta que la ordenación rápida.Una vez realicé un experimento en el que recibí 1000000 dígitos en java por clase aleatoria, y tomé 2610ms por mergesort, 1370ms por quicksort.

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

A diferencia de las matrices, en la lista de gustos podemos insertar elementos en el medio con espacio O (1) y tiempo O (1), por lo tanto, la operación de combinación en la ordenación de combinación se puede implementar sin ningún espacio adicional. 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 se accede a los datos 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 comunes 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 de 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).

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 por 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 vs 900K! * 100K! vs. Entonces, en lugar de preocuparse por establecer cualquier orden dentro de un rango o una partición, simplemente establezca el orden en un nivel más amplio en las particiones y reduzca las posibilidades dentro de una partición. Cualquier orden establecida anteriormente dentro de un rango se alterará más adelante si las particiones no se excluyen mutuamente.

Cualquier enfoque de abajo hacia arriba, como el ordenamiento por fusión o el ordenamiento en pilas, es como el enfoque de un empleado o empleado, donde uno comienza a comparar a un nivel microscópico temprano. Pero este orden está destinado a perderse tan pronto como un elemento entre ellos se encuentre más adelante. Estos enfoques son muy estables y extremadamente predecibles, pero hacen una cierta cantidad de trabajo adicional.

La clasificación rápida es como el enfoque gerencial en el que uno no está inicialmente preocupado por ningún orden, 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 se sabe nada sobre los elementos a ordenar. Es por eso que necesitamos hacer un esfuerzo para encontrar un valor mediano o elegir 1 al azar o algún enfoque "administrativo" arbitrario. Encontrar una mediana perfecta puede requerir una gran cantidad de esfuerzo y conduce a un enfoque ascendente estúpido nuevamente. Entonces, Quicksort dice que solo debes elegir un pivote aleatorio y esperar que esté en algún lugar en el medio o hacer un trabajo para encontrar una mediana de 3, 5 o algo más para encontrar una mejor mediana, pero no planeas ser perfecto y no lo hagas.t perder cualquier momento en el pedido inicial. Parece que te va bien si tienes suerte o, a veces, se degrada a n ^ 2 cuando no obtienes una mediana, sino que simplemente te arriesgas. De cualquier manera los datos son aleatorios. Correcto. Así que estoy más de acuerdo con el enfoque lógico superior -> descendente de quicksort y resulta que la posibilidad de que la selección y las comparaciones dinámicas que se guardan antes funcionen mejor más veces que cualquier enfoque meticuloso y minucioso y estable desde abajo - como arriba fusionar ordenlas comparaciones que se guardan antes parecen funcionar mejor más veces que cualquier enfoque meticuloso y minucioso y estable desde abajo hacia arriba, como la clasificación por fusión.las comparaciones que se guardan antes parecen funcionar mejor más veces que cualquier enfoque meticuloso y minucioso y estable desde abajo hacia arriba, como la clasificación por fusión. Pero