¿Por qué es quicksort mejor que mergesort?

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

En RAM esta suposición generalmente no es tan mala (no siempre es cierta debido a las 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 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 tienen que ser ordenados en el disco, realmente, realmente desea utilizar alguna variación en mergesort. (Por lo general, las sublistas de quicksort, luego comienzan a fusionarlas por encima de algún umbral de tamaño.)

Además, si tiene que hacer cualquier cosa con conjuntos de datos de ese tamaño, piense mucho sobre cómo evitar las búsquedas al disco. Por ejemplo, esta es la razón por la que es un consejo estándar que suelte los índices antes de hacer 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 el disco. Por el contrario, si elimina los índices, entonces la base de datos puede reconstruir el índice ordenando primero la información a tratar (¡usando un mergesort, por supuesto!) y luego cargarlo en una estructura de datos BTREE para el índice. (Btres se mantienen naturalmente en orden, por lo que puede cargar uno desde un conjunto de datos ordenado con pocas búsquedas en disco.)

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

En realidad, QuickSort es O (n²). Su tiempo medio de ejecución es O (nlog (n)), pero su peor caso es O (n²), que ocurre cuando se 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 malicioso haga que su clasificación tome mucho tiempo.

QuickSort es más popular porque:

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

Los Algoritmos de Ordenación animados muestran una serie de algoritmos en 4 condiciones iniciales diferentes (aleatorias, casi ordenadas, invertidas, pocas únicas) y podrían ayudar.

"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 se nombra más inteligentemente. es decir, buen marketing.

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

Como otros han señalado, 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 ambos términos son diferentes para cada comparación. En otras palabras, Quicksort hace la mitad de lecturas que los otros dos algoritmos. En el rendimiento de las CPU modernas está fuertemente dominado por los tiempos de acceso, por lo que al final Quicksort termina siendo una gran primera opción.

Me gustaría añadir 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 quicksort es... quick=)

Todos los algoritmos de ordenación tienen sus altibajos. Ver Artículo de Wikipedia para algoritmos de ordenación para una buena descripción.

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

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

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

Sin embargo, la propiedad más importante según mi experiencia es la fácil implementación del acceso secuencial que puede usar mientras ordena cuando usa 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).

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 quicksort en promedio.

De la entrada de Wikipedia en Quicksort :

Quicksort también compite con mergesort, otro tipo recursivo algoritmo pero con el beneficio de en el peor de los casos Θ(nlogn) tiempo de ejecución. Mergesort es un tipo estable, a diferencia de quicksort y heapsort, y puede ser se adapta fácilmente para operar en listas y listas muy grandes almacenadas en medios de acceso lento, como el disco almacenamiento o almacenamiento conectado a la red. Aunque quicksort se puede escribir en operar en linked listas, a menudo sufren de malas opciones de pivote sin acceso aleatorio. La principal desventaja de mergesort es que, al operar en matrices, requiere Θ (n) auxiliar espacio en el mejor de los casos, mientras que el variante de quicksort con in-place usos de partición y recursión de cola solo espacio Θ (logn). (Tenga en cuenta que cuando operando en listas enlazadas, mergesort solo requiere una cantidad pequeña y constante de almacenamiento auxiliar.)

La explicación de Wikipedia es:

Normalmente, quicksort es significativamente más rápido en la práctica que otros algoritmos Θ(nlogn), porque su bucle interno puede implementarse 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.

Quicksort

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.

Quicksort NO es mejor que mergesort. Con O (n^2) (el peor de los casos que rara vez sucede), quicksort es potencialmente mucho más lento que el O (nlogn) del tipo merge. 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 los elementos con claves idénticas en su orden original, un atributo útil.

Me gustaría añadir a las grandes respuestas existentes algunas matemáticas sobre cómo funciona QuickSort cuando se aleja del mejor caso y qué tan probable es, lo que espero ayude a la gente a entender un poco mejor por qué el caso O(n^2) no es de verdadera 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 ordenada.

1) Un pequeño número de claves en los datos. Un conjunto de datos de todo el mismo valor se ordenará en n^2 tiempo 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 del mismo valor en O (n) tiempo. Por lo tanto, el uso de una implementación de este tipo significa que una entrada con un pequeño número de claves realmente mejora tiempo de rendimiento y ya no es una preocupación.

2) Una selección de pivote extremadamente mala puede causar el peor rendimiento. En un caso ideal, el pivote siempre será tal que el 50% de los datos sean más pequeños y el 50% de los datos sean más grandes, de modo que la entrada se rompa a la mitad durante cada iteración. Esto nos da n comparaciones e intercambios tiempos 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 donde el pivote se elige consistentemente de tal manera que el 75% de los datos está 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 base es siempre una constante representada por log (2) / log(newBase). En este caso, esa constante es 2.4. Por lo tanto, esta calidad de la opción de pivote toma 2.4 veces más que la ideal.

¿Qué tan rápido empeora esto?

No muy rápido hasta la elección del pivote se pone (consistentemente) 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% por un lado, la porción de registro de la ejecución se aproxima a n y toda la ejecución se aproxima asintóticamente a O(n^2).

En una implementación ingenua de QuickSort, casos como un ordenado array (para el pivote del 1er elemento) o un array ordenado inversamente(para el pivote del último elemento) producirá confiablemente 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 que están diseñados para producir la ejecución del peor caso. Las implementaciones modernas evitan esto mediante una variedad de métodos, como aleatorizar los datos antes de ordenar, 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 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 rendimiento 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 de 25% -75% son " buenos "y los pivotes que están en el rango de 0% -25% o 75% -100% son"malos". Si nos fijamos en 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 siempre están exactamente en una división del 25%/75% y funcionan en una caja ideal de 2.4*. Nunca obtenga 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 clasificación de inserción, por lo que requerimos 22 particiones pivot 25%/75% para romper la entrada de 5,000 valores hasta ese momento. (10 * 1.333333^22 > 5000) O, requerimos 4990 pívots en el peor de los casos. Tenga en cuenta que si acumulamos 22 buenos pivotes en cualquier punto entonces el sort se completará, por lo que el peor de los casos o cualquier cosa cerca de él requiere extremadamente mala suerte. Si nos tomó 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é probabilidad hay de que no logremos los 22 buenos pivotes requeridos después de 88 recursiones?

Las distribuciones binomiales de probabilidad pueden responder a eso, y la respuesta es aproximadamente 10^-18. (y 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 segundo 1 que toma hacer clic en [ORDENAR] de lo que son para ver que 5,000 elemento de ordenación ejecutar cualquier peor que 10*caso ideal. Esta posibilidad se reduce a medida que el conjunto de datos se hace más grande. Estos son algunos tamaños de matriz y sus correspondientes posibilidades de correr más de 10*ideal:

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

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

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

La respuesta se inclinaría ligeramente hacia quicksort w.r.t a los cambios traídos con DualPivotQuickSort para valores primitivos . Se utiliza en JAVA 7 para ordenar en java.útil.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.

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

Otra lectura impresionante en DualPivotQuickSort - http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628

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 ajustada y las operaciones que hace pueden ir más rápido. Es debido a que quicksort es generalmente más rápido que la gente lo usa en lugar de mergesort.

Sin embargo! Personalmente, a menudo utilizo mergesort o una variante quicksort que se degrada a mergesort cuando quicksort funciona mal. Recordar. Quicksort es solo O (n log n) en promedio . El peor de los casos es O (n^2)! Mergesort es siempre O (n log n). En los casos en los que el rendimiento en tiempo real o la capacidad de respuesta es una necesidad y sus datos de entrada podrían provenir de una fuente maliciosa, no debe usar quicksort simple.

Quicksort tiene una mejor complejidad media de casos, pero en algunas aplicaciones es la elección equivocada. Quicksort es vulnerable a ataques de denegación de servicio. Si un atacante puede elegir la entrada a ser ordenada, puede construir fácilmente un conjunto que toma la complejidad de tiempo del peor caso de o(n^2).

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

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

Siendo todas las cosas iguales, 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, quicksort es conocido por ser 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 una especie de cubo. Son O (n), al menos en las listas enlazadas 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 demostrar a mi profesor en el análisis de algoritmos que era de hecho posible ordenar más rápido que O(n log(n)). (Él tenía la prueba de que no se puede comparación ordenar más rápido que O(n log(n)), que es cierto.)

En otras noticias, los flotadores se pueden ordenar como enteros, pero tienes que girar los números negativos después.

Editar: En realidad, aquí hay una manera aún más viciosa de ordenar 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 ordenación que realmente utilice...

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 demostrado).Y para cualquier n,es entre (n lg n - n + 1) y (n lg n + n + O(lg n)).Pero para quickSort, su mejor es nlog2n (también n es igual a 2^k).Si divide Mergesort por quickSort, es igual a uno cuando n es infinite.So 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 memeroy espacio.Y MergeSort también necesita hacer muchas copias de matriz, que no incluimos en el análisis de algorithm.In una palabra, MergeSort es realmente más rápido que quicksort en theroy, pero en realidad es necesario considerar el espacio memeory, el costo de copia de matriz, fusión es más lento que la clasificación rápida.Una vez hice un experimento donde me dieron 1000000 dígitos en Java por clase aleatoria,y tomó 2610ms por mergesort,1370ms por quicksort.

¿Por qué Quicksort es bueno?

• QuickSort toma N^2 en el peor de los casos y NlogN caso promedio. El peor caso ocurre cuando se ordenan los datos. Esto puede ser mitigado por aleatorio antes de comenzar la clasificación.
• QuickSort no toma memoria extra que se toma por merge sort.
• 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éntico, se clasifica en tiempo lineal. [Esta es la implementación predeterminada en la mayoría de las bibliotecas]

¿Quicksort siempre es mejor que Mergesort?

En realidad no.

• Mergesort es estable pero Quicksort no lo es. Por lo tanto, 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 daño en usando Mergesort.

Nota: En java, Arrays.la función sort () utiliza 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 que se agregó un poco de sobrecarga para Mergesort puede no ser ningún problema para el punto de vista de rendimiento.

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

La ordenación rápida es el peor caso O(n^2), sin embargo, el caso promedio realiza consistentemente la ordenación combinada. Cada algoritmo es O (nlogn), pero debes recordar que cuando hablamos de Big O dejamos fuera los factores de menor complejidad. Quick sort tiene mejoras significativas sobre merge sort cuando se trata de factores constantes.

Merge sort también requiere memoria O(2n), mientras que quick sort se puede hacer en su lugar (requiriendo solo O(n)). Esta es otra razón por la que quick sort generalmente se prefiere sobre ordenar por fusión.

Información Adicional:

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

[5, 4, 3, 2, 1]

Si el pivote se elige como el número más pequeño o más grande del grupo, entonces quick sort 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 pivote típico elegir algoritmo (digamos 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 pobre es de 0.5 * n. Basado en esta probabilidad, quick sort es eficiente para el caso promedio (y típico).

En merge-sort, el algoritmo general es:

1. Ordenar el sub-array izquierdo
2. Ordenar el sub-array derecho
3. Fusionar los 2 subarrays ordenados

En el nivel superior, fusionar los 2 subarrays ordenados implica tratar con N elementos.

Un nivel por debajo de eso, cada iteración del paso 3 implica tratar con N/2 elementos, pero tiene que 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ás 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. Elija un punto de pivote
2. Coloque el punto de pivote en el lugar correcto en la matriz, con todos los elementos más pequeños a la izquierda y los elementos más grandes a la derecha
3. Ordenar el subarray izquierdo
4. Ordenar el subarray de la derecha

En el nivel superior, estás tratar con una matriz de tamaño N. A continuación, elegir un punto de pivote, ponerlo 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). Usted elige un punto de pivote para cada sub-matriz, que viene hasta 2 puntos de pivote adicionales.

Un nivel por debajo de eso, está tratando con 4 sub-arreglos con tamaño combinado N-3, por las mismas razones como arriba.

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

La profundidad de tu pila recursiva sigue siendo aproximadamente la misma (logN). Con merge-sort, siempre se trata de una combinación de N elementos, en cada nivel de la pila recursiva. Sin embargo, con quick-sort, el número de elementos con los que estás tratando disminuye a medida que avanzas por la pila. Por ejemplo, si observa la profundidad a mitad de camino a través 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, debido a que divide la matriz en 2 trozos exactamente iguales cada vez, la profundidad recursiva es exactamente logN. En quick-sort, debido a 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 las matemáticas para ver qué tan grande un papel de este factor y el factor descrito anteriormente, en realidad juegan en la complejidad del algoritmo.

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

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

Pequeñas adiciones a quick vs merge sorts.

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 la ordenación combinada puede ser un algoritmo preferible.

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

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

Algo a considerar es la memoria también. Mergesort requiere una matriz adicional, digamos una "matriz de espacio de trabajo". Si su memoria es apenas lo suficientemente grande como para almacenar su matriz original, entonces mergesort no funcionará.

Quick sort es un algoritmo de ordenación in situ, por lo que es más adecuado para matrices. Merge sort por otro lado requiere almacenamiento adicional de O(N), y es más adecuado para listas vinculadas.

A diferencia de los arrays, en liked list podemos insertar elementos en el medio con O(1) espacio y O(1) tiempo, por lo tanto la operación merge en merge sort 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 merge sort. Merge sort también favorece la lista vinculada ya que los datos se acceden secuencialmente, sin mucho acceso a la memoria aleatoria.

Quick sort por otro lado requiere una gran cantidad de acceso a la memoria aleatoria y con una matriz podemos acceder directamente a la memoria sin ningún tipo de recorrido como lo requieren las listas vinculadas. También quick sort cuando se usa para arrays tiene una buena localidad de referencia ya que los arrays se almacenan contiguamente en la memoria.

Aunque la complejidad media de ambos algoritmos de ordenación es O (NlogN), para las tareas ordinarias utiliza una matriz de almacenamiento, y por esa razón quick sort debe ser el algoritmo de elección.

EDIT: Acabo de descubrir que merge sort worst/best/avg case es siempre nlogn, pero quick sort puede variar de n2(el peor caso cuando los elementos ya están ordenados) a nlogn(avg/mejor caso cuando pivot siempre divide la matriz en dos mitades).

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

Merge sort necesita en promedio ~ N log N comparaciones. Para los arrays ordenados ya (casi) ordenados, 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 ramas del procesador brille, pero adivinando casi todas las ramas correctamente, evitando así paradas de tuberías.

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

Mis puntos de referencia sobre 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 entrada aleatoria y un 30% para 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, merge sort comienza a ganar sobre quicksort en cualquier caso.

Así que tal vez la línea de fondo es: si la comparación es costosa (por ejemplo, función de devolución de llamada, comparando cadenas, comparando muchas partes de una estructura en su mayoría llegar a un segundo-tercer-cuarto " si " para hacer diferencia) - lo más probable es que usted será mejor con merge sort. Para tareas más simples quicksort será más rápido.

Que dicho 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 un ordenador realizar ordenar a ser golpeado por un rayo que ir N^2 - Mergesort requiere espacio adicional

En c / c++ land, cuando no uso contenedores stl, tiendo a usar quicksort, porque está construido 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 quick sort, para los casos en los 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! posibilidad. Con 2 particiones de m & n-m que son mutuamente excluyentes, el número de posibilidades bajan en varios órdenes de magnitud. m! *(n-m)! es más pequeño en varios órdenes que n! solo. imagine 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 factorial vs 900K!* 100K! frente Así que en lugar de preocuparse de estableciendo cualquier orden dentro de un rango o una partición,simplemente establezca un 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 será perturbado más tarde si las particiones en sí no son mutuamente excluyentes.

Cualquier enfoque de orden ascendente como merge sort o heap sort es como un enfoque de trabajadores o empleados donde uno comienza a comparar a un nivel microscópico temprano. Pero esta orden está destinada a perderse tan pronto como un elemento entre ellos se encuentra más adelante. Estos enfoques son muy estables y extremadamente predecibles, pero hacen una cierta cantidad de trabajo adicional.

La ordenación rápida es como un enfoque gerencial donde uno no está preocupado inicialmente por ningún orden , solo por cumplir con un criterio amplio sin tener en cuenta el orden. Luego, las particiones se estrechan 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 sobre los elementos para tipo. Es por eso que necesitamos gastar algún esfuerzo para encontrar un valor mediano o elegir 1 al azar o algún enfoque "gerencial" arbitrario . Encontrar una mediana perfecta puede tomar una cantidad significativa de esfuerzo y conduce a un estúpido enfoque de abajo hacia arriba de nuevo. Por lo tanto, Quicksort dice que solo elija un pivote aleatorio y espere 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 pierda el tiempo inicialmente ordenar. Eso parece hacer bien si usted tiene suerte o a veces se degrada a n^2 cuando usted no consigue una mediana, pero simplemente tomar una oportunidad. De cualquier manera los datos son aleatorios. derecho. Así que estoy más de acuerdo con el enfoque lógico de arriba a abajo de quicksort y resulta que la oportunidad que toma sobre la selección de pivote y las comparaciones que guarda antes parece funcionar mejor más veces que cualquier enfoque meticuloso y completo estable de abajo a arriba como merge sort. Pero