¿Por qué es quicksort mejor que otros algoritmos de clasificación en la práctica?

308

En un curso de algoritmos estándar se nos enseña que quicksort es en promedio y en el peor de los casos. Al mismo tiempo, se estudian otros algoritmos de clasificación que son en el peor de los casos (como mergesort y heapsort ), e incluso tiempo lineal en el mejor de los casos (como bubbleort ) pero con algunas necesidades adicionales de memoria.O ( n 2 ) O ( n log n )O(nlognorte)O(norte2)O(norteIniciar sesiónnorte)

Después de un rápido vistazo a algunos tiempos de ejecución más , es natural decir que quicksort no debería ser tan eficiente como otros.

Además, tenga en cuenta que los estudiantes aprenden en los cursos de programación básica que la recursividad no es realmente buena en general porque podría usar demasiada memoria, etc. Por lo tanto (y aunque esto no es un argumento real), esto da la idea de que la clasificación rápida podría no ser realmente bueno porque es un algoritmo recursivo.

¿Por qué, entonces, la clasificación rápida supera a otros algoritmos de clasificación en la práctica? ¿Tiene que ver con la estructura de los datos del mundo real ? ¿Tiene que ver con la forma en que funciona la memoria en las computadoras? Sé que algunos recuerdos son mucho más rápidos que otros, pero no sé si esa es la verdadera razón de este rendimiento contraintuitivo (en comparación con las estimaciones teóricas).


Actualización 1: una respuesta canónica dice que las constantes involucradas en el del caso promedio son más pequeñas que las constantes involucradas en otros algoritmos . Sin embargo, todavía tengo que ver una justificación adecuada de esto, con cálculos precisos en lugar de solo ideas intuitivas.O ( n log n )O(norteIniciar sesiónnorte)O(norteIniciar sesiónnorte)

En cualquier caso, parece que la diferencia real ocurre, como sugieren algunas respuestas, a nivel de memoria, donde las implementaciones aprovechan la estructura interna de las computadoras, utilizando, por ejemplo, que la memoria caché es más rápida que la RAM. La discusión ya es interesante, pero aún me gustaría ver más detalles con respecto a la administración de memoria, ya que parece que la respuesta tiene que ver con eso.


Actualización 2: hay varias páginas web que ofrecen una comparación de algoritmos de clasificación, algunas más elegantes que otras (más notablemente sorting-algorithms.com ). Aparte de presentar una buena ayuda visual, este enfoque no responde a mi pregunta.

Janoma
fuente
2
La ordenación por fusión es en el peor de los casos, y la ordenación de una matriz de enteros donde hay un límite conocido en el tamaño de los enteros se puede hacer en tiempo O ( n ) con una ordenación de conteo. O(norteIniciar sesiónnorte)O(norte)
Carl Mummert
13
sorting-algorithms.com tiene una comparación bastante completa de algoritmos de clasificación.
Joe
2
Actualización de anuncio 1: supongo que puede tener un análisis riguroso o supuestos realistas. No he visto los dos. Por ejemplo, la mayoría de los análisis formales solo cuentan comparaciones.
Raphael
99
Esta pregunta ganó un concurso reciente sobre programadores .
Raphael
3
Interesante pregunta. Hice algunas pruebas hace algún tiempo con datos aleatorios y una implementación ingenua de ordenación rápida y ordenación por fusión. Ambos algoritmos funcionaron bastante bien para pequeños conjuntos de datos (hasta 100000 elementos), pero después de eso, la clasificación por fusión resultó ser mucho mejor. Esto parece contradecir la suposición general de que la ordenación rápida es tan buena y todavía no he encontrado una explicación. La única idea que se me ocurre es que normalmente el término ordenación rápida se usa para algoritmos más complejos como la ordenación de introducción, y que la implementación ingenua de la ordenación rápida con pivote aleatorio no es tan buena.
Giorgio

Respuestas:

215

Respuesta corta

El argumento de eficiencia de caché ya se ha explicado en detalle. Además, hay un argumento intrínseco, por qué Quicksort es rápido. Si se implementa como con dos "punteros de cruce", por ejemplo , aquí , los bucles internos tienen un cuerpo muy pequeño. Como este es el código ejecutado con mayor frecuencia, vale la pena.

Respuesta larga

Ante todo,

¡El caso promedio no existe!

Como el mejor y el peor de los casos a menudo son extremos que rara vez ocurren en la práctica, se realiza un análisis de caso promedio. ¡Pero cualquier análisis de caso promedio supone una distribución de entradas ! Para la clasificación, la opción típica es el modelo de permutación aleatoria (asumido tácitamente en Wikipedia).

¿Por qué -Notation?O

El descarte de constantes en el análisis de algoritmos se realiza por una razón principal: si estoy interesado en tiempos de ejecución exactos , necesito costos (relativos) de todas las operaciones básicas involucradas (incluso ignorando los problemas de almacenamiento en caché, canalización en procesadores modernos ...). El análisis matemático puede contar con qué frecuencia se ejecuta cada instrucción, pero los tiempos de ejecución de instrucciones individuales dependen de los detalles del procesador, por ejemplo, si una multiplicación entera de 32 bits requiere tanto tiempo como la suma.

Hay dos salidas:

  1. Arreglar algún modelo de máquina.

    Esto se hace en la serie de libros de Don Knuth "El arte de la programación de computadoras" para una computadora artificial "típica" inventada por el autor. En el volumen 3 encontrará resultados de casos promedio exactos para muchos algoritmos de clasificación, por ejemplo

    • Clasificación rápida : 11.667(n+1)ln(n)1.74n18.74
    • Mergesort: 12.5nln(n)
    • Heapsort: 16nln(n)+0.01n
    • Insertionsort: [ fuente ]2.25n2+7.75n3ln(n) Tiempos de ejecución de varios algoritmos de clasificación

    Estos resultados indican que Quicksort es el más rápido. Pero, solo se prueba en la máquina artificial de Knuth, no necesariamente implica nada, por ejemplo, su PC x86. Tenga en cuenta también que los algoritmos se relacionan de manera diferente para entradas pequeñas:
    Tiempos de ejecución de varios algoritmos de clasificación para entradas pequeñas
    [ fuente ]

  2. Analizar operaciones básicas abstractas .

    Para la ordenación basada en la comparación, generalmente se trata de intercambios y comparaciones clave . En los libros de Robert Sedgewick, por ejemplo, "Algoritmos" , se sigue este enfoque. Te encuentras ahi

    • Quicksort: comparaciones y 12nln(n)intercambios en promedio13nEn(norte)
    • Mergesort: comparaciones, pero hasta 8.66 n ln ( n ) accesos de matriz (mergesort no se basa en el intercambio, por lo que no podemos contar eso).1,44norteEn(norte)8.66norteEn(norte)
    • Insertionsort: comparaciones y114 4norte2swaps en promedio.14 4norte2

    Como puede ver, esto no permite fácilmente comparaciones de algoritmos como el análisis exacto del tiempo de ejecución, pero los resultados son independientes de los detalles de la máquina.

Otras distribuciones de entrada

Como se señaló anteriormente, los casos promedio son siempre con respecto a alguna distribución de entrada, por lo que uno podría considerar otros que no sean permutaciones aleatorias. Por ejemplo, se ha realizado una investigación para Quicksort con elementos iguales y hay un buen artículo sobre la función de clasificación estándar en Java

Sebastian
fuente
8
Los resultados del tipo 2. pueden transformarse en resultados del tipo 1. insertando constantes dependientes de la máquina. Por lo tanto, diría que 2. es un enfoque superior.
Raphael
2
@Raphael +1. Supongo que está asumiendo que depende de la máquina también depende de la implementación, ¿verdad? Quiero decir, la máquina rápida + implementación pobre probablemente no sea muy eficiente.
Janoma
2
@Janoma Supuse que el algoritmo analizado se daría en forma muy detallada (como se detalla el análisis) y que la implementación sea lo más detallada posible. Pero sí, la implementación también influiría.
Raphael
3
En realidad, el análisis tipo 2 es inferior en la práctica. Las máquinas del mundo real son tan complicadas que los resultados del tipo 2 no se pueden traducir de manera factible al tipo 1. Compare eso con el tipo 1: trazar tiempos de ejecución experimentales requiere 5 minutos de trabajo.
Jules
44
@Jules: "trazar el tiempo de ejecución experimental" no es de tipo 1; No es un tipo de análisis formal y no es transferible a otras máquinas. Es por eso que hacemos un análisis formal, después de todo.
Raphael
78

Hay varios puntos que se pueden hacer con respecto a esta pregunta.

Quicksort suele ser rápido

Aunque Quicksort tiene el comportamiento peor de los casos , generalmente es rápido: suponiendo una selección de pivote aleatorio, existe una gran posibilidad de que elijamos algún número que separe la entrada en dos subconjuntos de tamaño similar, que es exactamente lo que queremos tener .O(n2)

En particular, incluso si elegimos un pivote que crea una división del 10% -90% cada 10 divisiones (que es una división meh), y una división de 1 elemento - elemento de lo contrario (que es la peor división que puede obtener) , nuestro tiempo de ejecución sigue siendo O ( n log n ) (tenga en cuenta que esto haría explotar las constantes hasta un punto en el que Merge sort es probablemente más rápido).n1O(nlogn)

Quicksort suele ser más rápido que la mayoría de los tipos

El ordenamiento rápido suele ser más rápido que los tipos que son más lentos que (por ejemplo, ordenación por inserción con su tiempo de ejecución O ( n 2 ) ), simplemente porque durante grandes n explotan sus tiempos de ejecución.O(nlogn)O(n2)n

Una buena razón por la cual Quicksort es tan rápido en la práctica en comparación con la mayoría de los otros algoritmos como Heapsort, es porque es relativamente eficiente en caché. Su tiempo de ejecución es en realidad O ( nO(nlogn), dondeBes el tamaño del bloque. Heapsort, por otro lado, no tiene tal aceleración: no está accediendo de manera eficiente a la memoria caché.O(nBlog(nB))B

La razón de esta eficiencia de caché es que escanea linealmente la entrada y particiona linealmente la entrada. Esto significa que podemos aprovechar al máximo cada carga de caché que hacemos mientras leemos cada número que cargamos en el caché antes de cambiar ese caché por otro. En particular, el algoritmo es ajeno a la memoria caché, lo que proporciona un buen rendimiento de memoria caché para cada nivel de memoria caché, que es otra ganancia.

La eficiencia del caché podría mejorarse aún más a , dondeMes el tamaño de nuestra memoria principal, si usamosk-way Quicksort. Tenga en cuenta que Mergesort también tiene la misma eficiencia de caché que Quicksort, y su versión k-way de hecho tiene un mejor rendimiento (a través de factores constantes más bajos) si la memoria es una restricción severa. Esto da lugar al siguiente punto: tendremos que comparar Quicksort con Mergesort en otros factores.O(nBlogMB(nB))Mk

Quicksort suele ser más rápido que Mergesort

Esta comparación es completamente sobre factores constantes (si consideramos el caso típico). En particular, la elección es entre una elección subóptima del pivote para Quicksort versus la copia de toda la entrada para Mergesort (o la complejidad del algoritmo necesario para evitar esta copia). Resulta que el primero es más eficiente: no hay ninguna teoría detrás de esto, simplemente es más rápido.

Tenga en cuenta que Quicksort realizará más llamadas recursivas, pero asignar espacio en la pila es barato (de hecho, casi gratis, siempre y cuando no desperdicie la pila) y lo reutiliza. Asignar un bloque gigante en el montón (o su disco duro, si es realmente grande) es bastante más costoso, pero ambos son gastos generales O ( log n ) que palidecen en comparación con el trabajo O ( n ) mencionado anteriormente.nO(logn)O(n)

Por último, tenga en cuenta que Quicksort es ligeramente sensible a la entrada que está en el orden correcto, en cuyo caso puede omitir algunos intercambios. Mergesort no tiene tales optimizaciones, lo que también hace que Quicksort sea un poco más rápido en comparación con Mergesort.

Use el tipo que se adapte a sus necesidades.

En conclusión: ningún algoritmo de clasificación es siempre óptimo. Elija el que mejor se adapte a sus necesidades. Si necesita un algoritmo que sea el más rápido para la mayoría de los casos, y no le importa, podría terminar siendo un poco lento en casos excepcionales, y no necesita un tipo estable, use Quicksort. De lo contrario, utilice el algoritmo que mejor se adapte a sus necesidades.

Alex ten Brink
fuente
3
Su último comentario es especialmente valioso. Un colega mío actualmente analiza las implementaciones de Quicksort bajo diferentes distribuciones de entrada. Algunos de ellos se descomponen por muchos duplicados, por ejemplo.
Raphael
44
@Raphael, eche un vistazo al "Adversario asesino de Quicksort" de McIllroy, Software - Practice and Experience 29 (4), 341-344 (1999). Describe una técnica tortuosa para hacer que Quicksort tome siempre tiempo . "Ingeniería de una función de clasificación" de Bentley y McIllroy, Software - Practice and Experience 23 (11), 1249-1265 (1993) también podría ser relevante. O(n2)
vonbrand 01 de
8
"[T] aquí no hay ninguna teoría detrás de esto, simplemente es más rápido". Esa afirmación es altamente insatisfactoria desde un punto de vista científico. Imagine a Newton diciendo: "Las mariposas vuelan, las manzanas se caen: no hay ninguna teoría detrás de esto, las manzanas se caen".
David Richerby
2
@Alex ten Brink, ¿qué quieres decir con "En particular, el algoritmo es ajeno a la memoria caché "?
Hibou57
44
@David Richerby, "Esa afirmación es muy insatisfactoria desde un punto de vista científico": puede estar presenciando un hecho sin pretender que deberíamos estar contentos con él. Algunas familias de algoritmos adolecen de una falta de formalización completa; Las funciones de hash son un ejemplo
Hibou57
45

En uno de los tutoriales de programación de mi universidad, les pedimos a los estudiantes que compararan el rendimiento de QuickSort, Mergesort, Insertion Sort y Python en el list.sort incorporado (llamado Timsort ). Los resultados experimentales me sorprendieron profundamente ya que el list.sort incorporado funcionó mucho mejor que otros algoritmos de clasificación, incluso con instancias que fácilmente colapsaron rápidamente. Por lo tanto, es prematuro concluir que la implementación habitual de clasificación rápida es la mejor en la práctica. Pero estoy seguro de que hay una implementación mucho mejor de quicksort, o alguna versión híbrida del mismo.

Este es un buen artículo de blog de David R. MacIver que explica Timsort como una forma de combinación adaptativa.

Dai
fuente
17
@Raphael Para decirlo de manera sucinta, Timsort es un tipo de fusión para los asintóticos más el tipo de inserción para entradas cortas más algunas heurísticas para hacer frente de manera eficiente a los datos que ocasionalmente tienen una ráfaga ya clasificada (lo que sucede a menudo en la práctica). Dai: además del algoritmo, se list.sortbeneficia de ser una función integrada optimizada por profesionales. Una comparación más justa tendría todas las funciones escritas en el mismo idioma con el mismo nivel de esfuerzo.
Gilles
1
@Dai: Al menos podría describir con qué tipo de entradas (resp. Su distribución) bajo qué circunstancias (RAM baja, una implementación paralela, ...) obtuvo sus resultados.
Rafael
77
Probamos en la lista de números aleatorios, y los ordenamos parcialmente, los ordenamos por completo y los invertimos. Fue un curso introductorio de primer año, por lo que no fue un estudio empírico profundo. Pero el hecho de que ahora se use oficialmente para ordenar matrices en Java SE 7 y en la plataforma Android sí significa algo.
Dai
3
Esto también se discutió aquí: cstheory.stackexchange.com/a/927/74
Jukka Suomela
34

Creo que una de las principales razones por las que QuickSort es tan rápido en comparación con otros algoritmos de clasificación es porque es compatible con la caché. Cuando QS procesa un segmento de una matriz, accede a elementos al principio y al final del segmento, y se mueve hacia el centro del segmento.

Entonces, cuando comienzas, accedes al primer elemento de la matriz y una pieza de memoria ("ubicación") se carga en el caché. Y cuando intentas acceder al segundo elemento, (lo más probable) ya está en el caché, por lo que es muy rápido.

Otros algoritmos como heapsort no funcionan así, saltan mucho en la matriz, lo que los hace más lentos.

svick
fuente
55
Esa es una explicación discutible: mergesort también es compatible con caché.
Dmytro Korduban
2
Creo que esta respuesta es básicamente correcta, pero aquí hay algunos detalles youtube.com/watch?v=aMnn0Jq0J-E
rgrig
3
probablemente la constante multiplicativa para la complejidad de tiempo de caso promedio de clasificación rápida también es mejor (independientemente del factor de caché que ha mencionado).
Kaveh
1
El punto que mencionó no es tan importante, en comparación con otras buenas propiedades de clasificación rápida.
MMS
1
@Kaveh: "la constante multiplicativa para la complejidad de tiempo promedio de casos de clasificación rápida también es mejor" ¿Tiene algún dato al respecto?
Giorgio
29

Otros ya han dicho que el tiempo de ejecución promedio asintótico de Quicksort es mejor (en la constante) que el de otros algoritmos de clasificación (en ciertas configuraciones).

O(nlogn)

Tenga en cuenta que hay muchas variantes de Quicksort (véase, por ejemplo, la disertación de Sedgewick). Se desempeñan de manera diferente en diferentes distribuciones de entrada (uniforme, casi ordenada, casi inversamente ordenada, muchos duplicados, ...), y otros algoritmos podrían ser mejores para algunos.

k10

Rafael
fuente
20

En comparación con otros algoritmos de clasificación basados ​​en comparación con O(nlgn)

ps: para ser precisos, ser mejor que otros algoritmos depende de la tarea. Para algunas tareas, podría ser mejor usar otros algoritmos de clasificación.

Ver también:

Kaveh
fuente
3
@Janoma, se trata de qué idioma y compilador usas. Casi todos los lenguajes funcionales (ML, Lisp, Haskell) pueden hacer optimizaciones que evitan que la pila crezca, y los compiladores más inteligentes para lenguajes imperativos pueden hacer lo mismo (GCC, G ++, y creo que MSVC todos hacen esto). La notable excepción es Java, que nunca hará esta optimización, por lo que tiene sentido en Java reescribir su recursión como iteración.
Rafe Kettler
44
@JD, no puedes usar la optimización de llamadas de cola con quicksort (al menos no completamente), porque se llama a sí mismo dos veces. Puede optimizar la segunda llamada, pero no la primera.
svick
1
@ Janan, realmente no necesitas la implementación recursiva. Por ejemplo, si observa la implementación de la función qsort en C, no utiliza llamadas recursivas y, por lo tanto, la implementación se vuelve mucho más rápida.
Kaveh
1
Heapsort también está en su lugar, ¿por qué QS es a menudo más rápido?
Kevin
66
23240
16

Θ(n2)Θ(nlogn)

La segunda razón es que realiza la in-placeclasificación y funciona muy bien con entornos de memoria virtual.

ACTUALIZACIÓN:: (Después de los comentarios de Janoma y Svick)

Para ilustrar esto mejor, permítanme dar un ejemplo usando Merge Sort (porque Merge sort es el siguiente algoritmo de ordenación ampliamente adoptado después de la ordenación rápida, creo) y decirles de dónde provienen las constantes adicionales (según mi leal saber y entender por qué creo La ordenación rápida es mejor):

Considere la siguiente secuencia:

12,30,21,8,6,9,1,7. The merge sort algorithm works as follows:

(a) 12,30,21,8    6,9,1,7  //divide stage
(b) 12,30   21,8   6,9   1,7   //divide stage
(c) 12   30   21   8   6   9   1   7   //Final divide stage
(d) 12,30   8,21   6,9   1,7   //Merge Stage
(e) 8,12,21,30   .....     // Analyze this stage

Si te importa ver cómo está sucediendo la última etapa, el primer 12 se compara con el 8 y el 8 es más pequeño, por lo que va primero. Ahora 12 es OTRA VEZ en comparación con 21 y 12 sigue, y así sucesivamente. Si toma la fusión final, es decir, 4 elementos con otros 4 elementos, incurre en muchas comparaciones EXTRA como constantes que NO se incurre en la Clasificación rápida. Esta es la razón por la cual se prefiere la ordenación rápida.

0x0
fuente
1
Pero, ¿qué hace que las constantes sean tan pequeñas?
svick
1
@svick Debido a que están ordenados in-place, es decir, no se requiere memoria adicional.
0x0
Θ(nlgn)
15

Mi experiencia trabajando con datos del mundo real es que quicksort es una mala elección . Quicksort funciona bien con datos aleatorios, pero los datos del mundo real a menudo no son aleatorios.

En 2008, rastreé un error de software colgado hasta el uso de quicksort. Un tiempo después escribí implementaciones simples de clasificación de inserción, clasificación rápida, clasificación de montón y clasificación de combinación y las probé. Mi tipo de fusión superó a todos los demás mientras trabajaba en grandes conjuntos de datos.

Desde entonces, la opción de combinación es mi algoritmo de selección preferido. Es elegante Es simple de implementar. Es un tipo estable. No degenera en comportamiento cuadrático como lo hace quicksort. Me cambio a la inserción para ordenar pequeños arreglos.

En muchas ocasiones, me he dado cuenta de que una implementación determinada funciona sorprendentemente bien para la clasificación rápida solo para descubrir que en realidad no es una clasificación rápida. A veces, la implementación cambia entre quicksort y otro algoritmo y, a veces, no usa quicksort en absoluto. Como ejemplo, las funciones qsort () de GLibc en realidad usan la combinación de clasificación. Solo si falla la asignación del espacio de trabajo, vuelve al ordenamiento rápido in situ que un comentario de código llama "el algoritmo más lento" .

Editar: los lenguajes de programación como Java, Python y Perl también usan la combinación de clasificación, o más precisamente una derivada, como Timsort o clasificación de combinación para conjuntos grandes y clasificación de inserción para conjuntos pequeños. (Java también utiliza la clasificación rápida de doble pivote, que es más rápida que la clasificación rápida simple).

Erwan Legrand
fuente
Había visto algo similar a esto porque estábamos agregando / recurriendo constantemente para insertar en un lote de datos ya ordenados. Puede solucionar este problema en promedio utilizando un ordenamiento rápido aleatorio (y sorprenderse con un tipo raro y aleatorio terriblemente lento), o puede tolerar un tipo siempre más lento que nunca toma una cantidad sorprendente de tiempo para terminar. A veces también se requiere estabilidad de clasificación. Java ha pasado de usar el orden de fusión a una variante de clasificación rápida.
Rob
@Rob Esto no es exacto. Java todavía utiliza una variante de mergesort (Timsort) hasta el día de hoy. También utiliza una variante de clasificación rápida (clasificación rápida de doble pivote).
Erwan Legrand
14

1 - La ordenación rápida está en su lugar (no necesita memoria adicional, aparte de una cantidad constante).

2 - La clasificación rápida es más fácil de implementar que otros algoritmos de clasificación eficientes.

3 - La clasificación rápida tiene factores constantes más pequeños en su tiempo de ejecución que otros algoritmos de clasificación eficientes.

Actualización: para la ordenación por fusión, debe realizar algunas "fusiones", que necesitan una matriz adicional para almacenar los datos antes de fusionarse; pero en forma rápida, no lo haces. Es por eso que la clasificación rápida está en su lugar. También hay algunas comparaciones adicionales realizadas para la fusión que aumentan los factores constantes en el orden de fusión.

MMS
fuente
3
¿Has visto implementaciones avanzadas de Quicksort iterativas in situ? Son muchas cosas pero no "fáciles".
Raphael
2
El número 2 no responde a mi pregunta en absoluto, y los números 1 y 3 necesitan una justificación adecuada, en mi opinión.
Janoma
@Raphael: SON fáciles. Es mucho más fácil implementar una ordenación rápida en el lugar utilizando una matriz, en lugar de punteros. Y no necesita ser iterativo para estar en su lugar.
MMS
Las matrices para fusionar no son tan malas. Una vez que ha movido un elemento de una pila de origen a la pila de destino, ya no necesita estar allí. Si está utilizando matrices dinámicas, hay una sobrecarga de memoria constante al fusionar.
Oskar Skog
@ 1 Mergesort también puede estar instalado. @ 2 ¿Qué define eficiente? Me gusta el tipo de fusión porque, en mi opinión, es muy simple y eficiente. @ 3 Irrelevante cuando clasifica grandes cantidades de datos y requiere que el algoritmo se implemente de manera eficiente.
Oskar Skog
11

¿En qué condiciones es un algoritmo de clasificación específico el más rápido?

Θ(Iniciar sesión(norte)2)Θ(norteIniciar sesión(norte)2)

Θ(nortek)Θ(nortemetro)k=2# #nortetumetrosimir_ _oF_ _PAGSossyosilmi_ _vunaltumism=#maximum_length_of_keys

3) ¿La estructura de datos subyacente consiste en elementos vinculados? Sí -> siempre utiliza el orden de fusión en el lugar. Hay un tamaño fijo fácil de implementar o de abajo hacia arriba adaptativo (también conocido como natural) que combinan tipos de aridades diferentes para las estructuras de datos vinculadas, y dado que nunca requieren copiar todos los datos en cada paso y tampoco requieren recursiones, son más rápido que cualquier otro tipo de comparación general, incluso más rápido que el tipo rápido.

Θ(n) memoria adicional en el peor de los casos que consiste en índices originales, que también deben mantenerse sincronizados con cada intercambio que se realizará en los datos de entrada, de modo que cada ganancia de rendimiento que la clasificación rápida pueda tener sobre fusión el tipo probablemente se frustra.

5) ¿Se puede vincular el tamaño de los datos subyacentes a un tamaño pequeño a mediano? por ejemplo, ¿n <10,000 ... 100,000,000 (dependiendo de la arquitectura subyacente y la estructura de datos)? Sí -> utiliza el ordenamiento bitónico o el mezclador impar-par de Batcher. Ir a 1)

Θ(n)Θ(n2)Θ(nlog(n)2)se conocen los peores casos de tiempo de ejecución, o tal vez intente ordenar los peines. No estoy seguro de que la ordenación de concha o la de peine funcionen razonablemente bien en la práctica.

Θ(log(n))Θ(n)Θ(n)Θ(log(n))Θ(n2)Θ(n)Θ(n)Θ(log(n))Θ(nlog(n))

Θ(nlog(n))

Sugerencias de implementación para quicksort:

Θ(norte)Θ(Iniciar sesión(norte))Θ(norteIniciar sesiónk(k-1))

2) Existen variantes iterativas ascendentes de quicksort, pero AFAIK, tienen los mismos límites de espacio y tiempo asintóticos que los de arriba hacia abajo, con los lados inferiores adicionales de ser difíciles de implementar (por ejemplo, administrar explícitamente una cola). Mi experiencia es que, para fines prácticos, nunca vale la pena considerarlos.

Sugerencias de implementación para mergesort:

1) Mergesort Bottum-Up es siempre más rápido que Mergesort de arriba hacia abajo, ya que no requiere llamadas de recursión.

2) el mergesort muy ingenuo puede acelerarse utilizando un doble buffer y cambiar el buffer en lugar de copiar los datos de la matriz temporal después de cada paso.

3) Para muchos datos del mundo real, mergesort adaptativo es mucho más rápido que un mergesort de tamaño fijo.

Θ(k)Θ(Iniciar sesión(k))Θ(1)Θ(norte)

Por lo que he escrito, está claro que la clasificación rápida a menudo no es el algoritmo más rápido, excepto cuando se aplican las siguientes condiciones:

1) hay más de unos "pocos" valores posibles

2) la estructura de datos subyacente no está vinculada

3) no necesitamos un pedido estable

4) los datos son lo suficientemente grandes como para que el ligero tiempo de ejecución asintótico subóptimo de un clasificador bitónico o un mezclador impar-par de Batcher se active

5) los datos no están casi ordenados y no consisten en partes más grandes ya ordenadas

6) podemos acceder a la secuencia de datos simultáneamente desde múltiples lugares

Θ(Iniciar sesión(norte))Θ(norte)

PD: Alguien debe ayudarme con el formato del texto.

Franki
fuente
(5): la implementación de clasificación de Apple verifica primero una ejecución en orden ascendente o descendente, tanto al principio como al final de la matriz. Esto es muy rápido si no hay muchos de esos elementos, y puede manejar estos elementos de manera muy efectiva si hay más de n / ln n de ellos. Concatena dos matrices ordenadas y ordena el resultado, y obtienes una fusión
gnasher729
8

La mayoría de los métodos de ordenación tienen que mover datos en pasos cortos (por ejemplo, la ordenación por fusión realiza cambios localmente, luego fusiona este pequeño dato y luego fusiona uno más grande ...). En consecuencia, necesita muchos movimientos de datos si los datos están lejos de su destino.

unasi

fernand0
fuente
55
Su argumento sobre la ordenación rápida versus la fusión no se mantiene. Quicksort comienza con un movimiento grande, luego realiza movimientos cada vez más pequeños (aproximadamente la mitad del tamaño en cada paso). La ordenación por combinación comienza con un movimiento pequeño, luego realiza movimientos cada vez más grandes (aproximadamente el doble de grande en cada paso). Esto no apunta a que uno sea más eficiente que el otro.
Gilles