¿Por qué la ordenación rápida es mejor que la ordenación combinada?

https://stackoverflow.com/questions/70402

09-06-2019
|

Pregunta

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

Solución

Quicksort tiene O(norte²) tiempo de ejecución en el peor de los casos y O(norteregistronorte) tiempo de ejecución promedio del caso.Sin embargo, es superior la ordenación por combinación en muchos escenarios porque muchos factores influyen en el tiempo de ejecución de un algoritmo y, cuando se los toma todos juntos, gana la ordenación rápida.

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

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

En la práctica, muchas implementaciones modernas de Quicksort (en particular libstdc++) std::sort) son en realidad introclasificación, cuyo peor caso teórico es O(norteregistronorte), igual que ordenar por combinación.Lo logra limitando la profundidad de la recursividad y cambiando a un algoritmo diferente (ordenar en montón) una vez que excede lognorte.

Otros consejos

Como mucha gente ha notado, el rendimiento promedio de casos para la ordenación rápida es más rápido que el de ordenación por combinación. Pero Esto solo es cierto si asume 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 cierta 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 la ordenación rápida se vuelve delicado por el hecho de que su disco promedio realiza alrededor de 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 hace mergesort.

Por lo tanto, si los datos tienen que ordenarse en el disco, realmente querrás usar alguna variación en mergesort.(Por lo general, ordena rápidamente las sublistas y luego comienza a fusionarlas por encima de cierto umbral de tamaño).

Además si tienes que hacer cualquier cosa Con conjuntos de datos de ese tamaño, piense detenidamente en cómo evitar búsquedas en el disco.Por ejemplo, es por eso que es un consejo estándar eliminar los índices antes de realizar grandes cargas de datos en las bases de datos y luego reconstruir 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 que se va a tratar (¡usando un mergesort, por supuesto!) y luego cargándola en una estructura de datos BTREE para el índice.(Los BTREE se mantienen naturalmente en orden, por lo que puede cargar uno desde un conjunto de datos ordenados con pocas búsquedas en el disco).

Ha habido varias ocasiones en las que entender cómo evitar búsquedas en el disco me ha permitido hacer que los trabajos de procesamiento de datos lleven horas en lugar de días o semanas.

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

QuickSort es más popular porque:

Está en su lugar (MergeSort requiere memoria adicional lineal según el número de elementos que se van a ordenar).
Tiene una pequeña constante oculta.

"y aún así la mayoría de la gente usa Quicksort en lugar de Mergesort.¿Porqué es eso?"

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

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

Como han señalado otros, el peor caso de Quicksort es O(n^2), mientras que mergesort y heapsort permanecen en O(nlogn).Sin embargo, en el caso promedio, los tres son O(nlogn);por lo que en la gran mayoría de los casos son 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 realiza la mitad de lecturas que los otros dos algoritmos.En las CPU modernas, el rendimiento está fuertemente dominado por los tiempos de acceso, por lo que al final Quicksort termina siendo una excelente primera opción.

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

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

Todos los tipos de algoritmos tienen sus altibajos.Ver Artículo de Wikipedia para algoritmos de clasificación para una buena visión general.

De la entrada de Wikipedia sobre Quicksort:

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

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

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

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

Sin embargo, según mi experiencia, la propiedad más importante es la fácil implementación del acceso secuencial que puede utilizar al ordenar cuando utiliza 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 ejecutará en O(n*ln(n)) y solo requiere almacenamiento adicional finito.Pero hay muchas citas de pruebas del mundo real que muestran que la clasificación en montón es significativamente más lenta que la clasificación rápida en promedio.

La explicación de Wikipedia es:

Normalmente, la ordenación rápida es significativamente más rápida 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 minimicen la probabilidad de requerir tiempo cuadrático. .

Ordenación rápida

fusionar

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

Quicksort NO es mejor que mergesort.Con O(n^2) (el peor de los casos, que rara vez ocurre), la clasificación rápida es potencialmente mucho más lenta que la O(nlogn) de la clasificación por 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 en día que la sobrecarga adicional de una ordenación por fusión es insignificante, y el riesgo de una ordenación rápida muy lenta supera con creces la sobrecarga insignificante de una ordenación por fusión en la mayoría de los casos.

Además, una ordenación por combinación deja elementos con claves idénticas en su orden original, un atributo útil.

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

Aparte de los problemas de acceso aleatorio, hay dos factores principales que pueden afectar el rendimiento de QuickSort y ambos están relacionados con la comparación del pivote con los datos que se están clasificando.

1) Una pequeña cantidad de claves en los datos.Un conjunto de datos del mismo valor se ordenará en n^2 tiempos en un QuickSort básico de 2 particiones porque todos los valores, excepto la ubicación del 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 tiempo O(n).Entonces, usar una implementación de este tipo significa que una entrada con una pequeña cantidad de claves en realidad mejora el tiempo de rendimiento y ya no es una preocupación.

2) Una selección de pivote extremadamente mala puede provocar el peor rendimiento en los casos.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 dividirá a la mitad durante cada iteración.Esto nos da n comparaciones e intercambios de tiempos log-2(n) recursiones por tiempo O(n*logn).

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

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

¿Qué tan rápido empeora esto?

No muy rápido hasta que la elección del pivote se vuelve (consistentemente) muy mala:

50% por un lado:(caso ideal)
75% por un lado:2,4 veces más tiempo
90% por un lado:6,6 veces más tiempo
95% por un lado:13,5 veces más largo
99% por un lado:69 veces más tiempo

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

En una implementación ingenua de QuickSort, casos como una matriz ordenada (para el pivote del primer elemento) o una matriz ordenada de manera 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 de pivote predecible pueden estar sujetas a ataques DoS mediante 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 mezcla, tenemos 2 casos:

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

¿Qué posibilidades hay de que veamos un desempeño terrible?

Las probabilidades son evanescentemente pequeño.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 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:

Los buenos pivotes siempre están exactamente en una división del 25%/75% y operan en 2,4*caso ideal.Nunca obtenemos una división ideal ni una división mejor que 25/75.
Los malos pivotes siempre son el peor de los casos y esencialmente no aportan nada 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 necesitamos 22 particiones dinámicas de 25 %/75 % para dividir la entrada de 5000 valores hasta ese punto.(10*1.333333^22 > 5000) O requerimos 4990 pivotes en el peor de los casos.Hay que tener en cuenta que si acumulamos 22 buenos pivotes en Cualquier punto entonces la clasificación se completará, por lo que en el peor de los casos o algo parecido se requiere extremadamente mala suerte.Si nos tomó 88 recursiones para lograr los 22 buenos pivotes necesarios para ordenar hasta n=10, ese 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 ¿Lograr 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 alcanzado por un rayo en el segundo que lleva hacer clic en [CLASIFICAR] que de ver ejecutar la clasificación de 5000 elementos. algo peor de 10*caso ideal.Esta posibilidad disminuye a medida que el conjunto de datos aumenta.A continuación se muestran algunos tamaños de matriz y sus correspondientes posibilidades de ejecutarse por más de 10*ideal:

Conjunto de 640 artículos:10^-13 (requiere 15 buenos puntos de pivote en 60 intentos)
Conjunto de 5.000 artículos:10^-18 (requiere 22 buenos pivotes de 88 intentos)
Conjunto 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.Por lo tanto, el rendimiento real es aún mejor y el equilibrio de la probabilidad restante está más cerca del ideal que de lo contrario.

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

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

En ordenación por fusión, el algoritmo general es:

Ordenar la submatriz izquierda
Ordenar el subconjunto correcto
Fusionar los 2 subarreglos ordenados

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

Un nivel por debajo de ese, cada iteración del paso 3 implica tratar con N/2 elementos, pero debes repetir este proceso dos veces.Entonces 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 la misma cantidad de elementos en todas las llamadas para esa profundidad.

En su lugar, considere el algoritmo de clasificación rápida:

Elige un punto de pivote
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.
Ordenar el subarreglo izquierdo
Ordenar el subarreglo derecho

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

Un nivel por debajo de eso, se trata de 2 submatrices que tienen un tamaño combinado de N-1 (es decir, restan el punto de pivote anterior).Usted elige un punto de pivote para cada submatriz, lo que genera hasta 2 puntos de pivote adicionales.

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

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

La profundidad de su 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 la clasificació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 camino a través de la pila recursiva, la cantidad de elementos con los que está tratando es N - 2^((logN)/2)) == N - sqrt(N).

Descargo de responsabilidad:En la ordenación por combinación, debido a que divide la matriz en 2 partes exactamente iguales cada vez, la profundidad recursiva es exactamente logN.En la clasificación rápida, 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 los cálculos para ver qué papel tan importante juegan este factor y el factor descrito anteriormente en la complejidad del algoritmo.

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

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, simplemente porque es más fácil codificar una implementación estricta y las operaciones que realiza pueden ser más rápidas.Debido a que la ordenación rápida es generalmente más rápida, la gente la usa en lugar de la ordenación combinada.

¡Sin embargo!Personalmente, a menudo uso mergesort o una variante de clasificación rápida que se degrada a mergesort cuando la clasificación rápida no funciona bien.Recordar.Quicksort solo está activado O (n log n) 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 o la capacidad de respuesta en tiempo real son imprescindibles y los datos de entrada podrían provenir de una fuente maliciosa, no debes utilizar la clasificación rápida simple.

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 va a ordenar, puede construir fácilmente un conjunto que tome el peor de los casos con una complejidad temporal de o(n^2).

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

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

¿Por qué Quicksort es bueno?

QuickSort toma N^2 en el peor de los casos y NlogN en el caso promedio.El peor de los casos ocurre cuando los datos están ordenados.Esto se puede mitigar mediante una reproducción aleatoria antes de comenzar la clasificación.
QuickSort no requiere memoria adicional que se utiliza mediante ordenación por combinación.
Si el conjunto de datos es grande y hay elementos idénticos, la complejidad de Quicksort se reduce mediante el uso de una partición de 3 vías.Cuanto mayor sea el número de elementos idénticos, mejor será el tipo.Si todos los elementos son idénticos, se ordena en tiempo lineal.[Esta es la implementación predeterminada en la mayoría de las bibliotecas]

¿Quicksort siempre es mejor que Mergesort?

No precisamente.

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

Nota: En Java, la función Arrays.sort() utiliza Quicksort para tipos de datos primitivos y Mergesort para tipos de datos de objetos.Debido a que los objetos consumen una sobrecarga de memoria, agregar un poco de sobrecarga para Mergesort puede no ser un problema desde el punto de vista del rendimiento.

Referencia:Mira los vídeos de QuickSort de Semana 3, Curso de Algoritmos de Princeton en Coursera

La ordenación rápida es el peor de los casos O(n^2); sin embargo, el caso promedio supera consistentemente la ordenación por combinación.Cada algoritmo es O(nlogn), pero debes recordar que cuando hablamos de Big O dejamos de lado los factores de menor complejidad.La clasificación rápida tiene mejoras significativas con respecto a la clasificación por combinación cuando se trata de factores constantes.

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

Información extra:

El peor caso de clasificación rápida ocurre cuando el pivote se elige mal.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, la clasificació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 típico de elección de pivote (por ejemplo, elegir un elemento aleatorio), tenemos 0,5 posibilidades de elegir un buen pivote por cada elección de pivote.Para colecciones de gran tamaño, la probabilidad de elegir siempre un pivote deficiente es 0,5 * n.Según esta probabilidad, la clasificación rápida es eficaz para el caso promedio (y típico).

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

La ordenación por fusión necesita en promedio ~ N log N comparaciones.Para matrices ya (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 a la derecha 1/2 N elementos.Además, puedo especular que la entrada ya ordenada hace que el predictor de ramas del procesador brille pero adivina casi todas las ramas correctamente, evitando así paradas en la tubería.

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

Mis puntos de referencia en procesadores bastante modernos 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), la ordenación rápida es más lenta que la ordenación por combinación en un 15% en entradas aleatorias y 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 clasificación rápida supera a la clasificación combinada hasta en un 25%.

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

Entonces tal vez la conclusión sea:si la comparación es costosa (p. ej.función de devolución de llamada, comparar cadenas, comparar muchas partes de una estructura, en su mayoría llegar a un segundo, tercio y cuarto "si" para marcar la diferencia): lo más probable es que sea mejor con la ordenación por fusión.Para tareas más sencillas, la clasificación rápida será más rápida.

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

Cuando experimenté con ambos algoritmos de clasificación, contando el número de llamadas recursivas, Quicksort consistentemente tiene menos llamadas recursivas que Mergesort.Esto se debe a que la ordenación rápida tiene pivotes y los pivotes no se incluyen en las siguientes llamadas recursivas.De esa manera, la ordenación rápida puede alcanzar el caso base recursivo más rápido que la ordenación por fusión.

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

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

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

En otras noticias, los flotantes se pueden ordenar como números enteros, pero luego hay que invertir los números negativos.

Editar:En realidad, aquí hay una forma aún más cruel de ordenar flotantes como números 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...

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, 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. Entonces 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á implementado, requiere 2n espacio de memoria. Y MergeSort también necesita hacer muchas copias de matrices, lo cual no incluir en el análisis del algoritmo. En una palabra, MergeSort es realmente más rápido que la clasificación rápida en teoría, pero en realidad es necesario considerar el espacio de la memoria, el costo de la copia de la matriz, la fusión es más lenta que la clasificación rápida. Una vez hice un experimento en el que la clase aleatoria me dio 1000000 dígitos en Java, y me tomó 2610 ms para mergesort, 1370 ms para Quicksort.

Pequeñas adiciones a las clasificaciones rápidas y combinadas.

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

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

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

La clasificación rápida es un algoritmo de clasificación in situ, por lo que es más adecuado para matrices.Por otro lado, la clasificación por combinación requiere almacenamiento adicional de O(N) y es más adecuada para listas enlazadas.

A diferencia de las matrices, en la lista Me gusta podemos insertar elementos en el medio con espacio O(1) y tiempo O(1), por lo tanto, la operación de combinación en ordenación por combinación se puede implementar sin ningún espacio adicional.Sin embargo, asignar y desasignar espacio adicional para matrices tiene un efecto adverso en el tiempo de ejecución de la ordenación por combinación.La clasificación por combinación también favorece las listas vinculadas, 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 mucho acceso aleatorio a la memoria y con una matriz podemos acceder directamente a la memoria sin tener que atravesarla como lo requieren las listas vinculadas.Además, la clasificación rápida cuando se usa para matrices tiene una buena localidad de referencia, ya que las matrices se almacenan de forma contigua en la memoria.

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

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

Considere tanto la complejidad del tiempo como del espacio.Para ordenar por combinación:Complejidad del tiempo:O (nLogn), complejidad espacial:O (iniciar sesión)

Para clasificación rápida:Complejidad del tiempo:O (n^2), complejidad del espacio:En)

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

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

En la tierra C/C ++, cuando no uso contenedores STL, tiendo a usar Quicksort, porque está integrado en el tiempo de ejecución, mientras que Mergesort no lo está.

Por eso creo que, en muchos casos, es simplemente el camino de menor resistencia.

Además, el rendimiento puede ser mucho mayor con la clasificación rápida, en 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!posibilidades.Con 2 particiones de m & n-m que son mutuamente excluyentes, el número de posibilidades disminuye en varios órdenes de magnitud.¡metro!* (n-m)!es varios órdenes más pequeño que n!solo.imagina 5!¡contra 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 versus 900K!*100K!vs.Entonces, en lugar de preocuparse por establecer un orden dentro de un rango o una partición, simplemente establezca el orden a un nivel más amplio en las particiones y reduzca las posibilidades dentro de una partición.Cualquier orden establecido anteriormente dentro de un rango será perturbado más adelante si las particiones mismas no son mutuamente excluyentes.

Cualquier enfoque de orden ascendente, como la clasificación por fusión o la clasificación por montón, es como el enfoque de los trabajadores o empleados en el que uno comienza a comparar a un nivel microscópico desde el principio.Pero este orden está destinado a perderse tan pronto como más adelante se encuentre un elemento intermedio entre ellos.Estos enfoques son muy estables y extremadamente predecibles, pero requieren una cierta cantidad de trabajo adicional.

Quick Sort es como un enfoque gerencial en el que inicialmente no nos preocupamos por ningún pedido, solo por cumplir un criterio amplio sin tener en cuenta el orden.Luego las particiones se reducen hasta obtener un conjunto ordenado.El verdadero desafío en Quicksort es encontrar una partición o criterio en la oscuridad cuando no sabes nada sobre los elementos a ordenar.Es por eso que debemos esforzarnos en 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 nuevamente a un enfoque estúpido de abajo hacia arriba.Entonces, Quicksort dice que simplemente elija un pivote aleatorio y espere que esté en algún punto intermedio o trabaje un poco para encontrar una mediana de 3, 5 o algo más para encontrar una mediana mejor, pero no planee ser perfecto y no desperdicie en cualquier momento al realizar el pedido inicial.Eso parece funcionar bien si tienes suerte o, a veces, se degrada a n^2 cuando no obtienes una mediana, pero simplemente arriesga.De cualquier forma los datos son aleatorios.bien.Así que estoy más de acuerdo con el enfoque lógico arriba ->abajo de la clasificación rápida y resulta que el riesgo que implica la selección de pivotes y las comparaciones que guarda antes parece funcionar mejor más veces que cualquier enfoque ascendente estable meticuloso y completo como ordenar por fusión.Pero

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow