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

https://cs.stackexchange.com/questions/3

15-10-2019
|

Pregunta

En unos algoritmos estándar supuesto se nos enseña que clasificación rápida es $ O (n \ log n) en promedio $ y $ O (n ^ 2) $ en el peor de los casos. Al mismo tiempo, otros algoritmos de clasificación se estudian cuales son $ O (n \ log n) $ en el peor de los casos (como mergesort y heapsort ), e incluso el tiempo lineal en el mejor de los casos (como BubbleSort ), pero con algunas necesidades adicionales de memoria.

Después de un rápido vistazo a algunas veces más que ejecutan es natural decir que la clasificación rápida no debería ser tan eficiente como otros.

Además, consideran que los estudiantes aprenden en los cursos básicos de programación que la recursividad no es muy buena en general, ya que podría utilizar 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 tal vez no sea muy bueno, ya que es un algoritmo recursivo.

¿Por qué, entonces, la clasificación rápida superan a otros algoritmos de clasificación en la práctica? ¿Tiene que ver con la estructura de datos del mundo real ? ¿Tiene que ver con las obras de memoria manera el ordenador? Sé que algunos recuerdos son mucho más rápido que otros, pero no sé si esa es la verdadera razón de esta actuación contraria a la intuición (en comparación con las estimaciones teóricas).

Actualización 1: una respuesta canónica está diciendo que las constantes que intervienen en el $ O (n \ log n) $ del caso medio son más pequeñas que las constantes involucradas en otra $ O (n \ log n) $ algoritmos. Sin embargo, todavía tengo que ver una justificación adecuada de este, con cálculos precisos en lugar de las ideas intuitivas solamente.

En cualquier caso, parece que se produce la verdadera diferencia, ya que algunas respuestas sugieren, a nivel de la memoria, donde las implementaciones se aprovechan de la estructura interna de los ordenadores, utilizando, por ejemplo, que la memoria caché es más rápida que la RAM. La discusión es ya interesante, pero todavía me gustaría ver con más detalle con respecto a la gestión de memoria, ya que parece que la respuesta tiene que ver con ello.

Actualización 2: Hay varias páginas web que ofrecen una comparación de algoritmos de clasificación, algunos más elegante que otros (sobre todo sorting-algorithms.com ). Aparte de presentar una buena ayuda visual, este enfoque no responde a mi pregunta.

Solución

Respuesta corta
El argumento de la eficiencia de caché ya ha sido explicada con detalle. Además, hay un argumento intrínseco, ¿por qué la ordenación rápida es rápida. 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 que se ejecuta con mayor frecuencia, esto vale la pena.

Respuesta larga

En primer lugar,

La Media de la caja no existe!

Como mejor y peor de los casos son a menudo extremos rara vez ocurre en la práctica, se realiza el análisis del caso promedio. Pero cualquier análisis del caso promedio asumen algunos distribución de insumos ! Para la clasificación, la elección típica es la modelo de permutación al azar (tácitamente en la Wikipedia).

¿Por qué $ O $ -Notation?

El descarte constantes en el análisis de algoritmos se hace por una razón principal: si estoy interesado en exacta tiempos de funcionamiento, Necesito (relativas) los costos de todas las operaciones básicas involucradas (aunque todavía haciendo caso omiso de los problemas de almacenamiento en caché, la canalización de los procesadores modernos ...). El análisis matemático puede recuento 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 entero de 32 bits lleva tanto tiempo como adición.

Hay dos maneras de salir:

solucionar algunos modelo de máquina.

Esto se hace en Don Knuth 's serie de libros “El arte de Programación de Computadoras” para un artificial‘típico equipo’inventado por el autor. En el volumen 3 a encontrar exactamente caso promedio resultados para muchos algoritmos de clasificación, por ejemplo,

ordenación rápida: $ 11.667 (n + 1) \ ln (n) -1.74n-18.74 $

por fusión: $ de los 12,5 N \ ln (n) $

heapsort: $ 16 n \ ln (n) + 0,01 $

InsertionSort: $ 2.25n ^ 2 + 7.75n-3LN (n) $
^{[ ]}

Estos resultados indican que la ordenación rápida es más rápida. Sin embargo, sólo se probó en la máquina artificial de Knuth, no implica necesariamente nada por decir su PC x86. Tenga en cuenta también que los algoritmos se relacionan de forma diferente para entradas pequeñas:

^{[ ]}

Analizar abstractos operaciones básicas .

Para la comparación basada en la clasificación, esto normalmente es permutas y comparaciones clave . En los libros de Robert Sedgewick, por ejemplo “Algoritmos” , se persigue este enfoque. Usted encontrará que hay

ordenación rápida: $ 2n \ ln (n) $ comparaciones y $ \ frac13n \ ln (n) $ permutas en promedio

por fusión: $ 1.44n \ ln (n) $ comparaciones, pero hasta $ 8.66n \ ln (n) $ accesos array (mergesort no se basa SWAP, por lo que no podemos contar con que)
.
InsertionSort:. $ \ Frac14n ^ 2 $ y $ \ comparaciones frac14n ^ 2 $ permutas en promedio

Como se puede ver, esto no permite fácilmente la comparación de algoritmos como el análisis exacto de 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 se podría considerar los distintos permutaciones aleatorias. P.ej. investigación se ha hecho para ordenación rápida con elementos iguales y hay buen artículo sobre la función de clasificación estándar en Java

Otros consejos

Hay varios puntos que se pueden hacer con respecto a esta cuestión.

ordenación rápida es generalmente rápido

A pesar de la ordenación rápida tiene peor de los casos $ O (n ^ 2) $ comportamiento, por lo general es rápido: suponiendo que la selección de pivote al azar, hay una gran posibilidad de que escogemos un número que separa la entrada en dos subconjuntos de tamaño similar, lo cual es exactamente lo que queremos tener.

En particular, incluso si tomamos un pivote que crea un 10% -90% divide cada 10 divisiones (que es una fracción de MEH), y un elemento de 1 - $ $ n-1 elemento de división de otra manera (que es el peor la división se pueden conseguir), el tiempo de ejecución es todavía $ O (n \ log n) $ (nota que esto sería hacer estallar las constantes a un punto que Fusionar especie es probablemente más rápido sin embargo).

ordenación rápida es generalmente más rápido que la mayoría de las clases

ordenación rápida es generalmente más rápido que las clases que son más lentos que $ O (n \ log n) $ (por ejemplo, ordenación por inserción con su $ O (n ^ 2) $ tiempo de ejecución), simplemente porque para grandes $ n $ de su ejecución veces explotan.

Una de las razones por qué buena ordenación rápida es tan rápido en la práctica en comparación con la mayoría de otros $ O (n \ log n) $ algoritmos como heapsort, es porque es relativamente caché eficiente. Su tiempo de ejecución es en realidad $ O (\ frac {n} {B} \ log (\ frac {n} {B})) $, donde $ B $ es el tamaño de bloque. Heapsort, por el contrario, no tiene tal aumento de velocidad:. No es en absoluto acceso a memoria caché de manera eficiente

La razón de esta eficiencia caché es que explora linealmente la entrada y particiones linealmente la entrada. Esto significa que podemos aprovechar al máximo cada carga caché que hacemos como leemos todos cargamos número en la memoria caché antes de intercambiar esa caché para otro. En particular, el algoritmo es ajeno caché, lo que da un buen rendimiento de la caché para cada nivel de caché, que es otra victoria.

eficiencia de la caché podría mejorarse aún más a $ O (\ frac {n} {B} \ log _ {\ frac {M} {B}} (\ frac {n} {B})) $, donde $ M $ es el tamaño de la memoria principal, si usamos $ k $-way ordenación rápida. Tenga en cuenta que la ordenación por fusión también tiene el mismo caché eficiencia como la ordenación rápida, y su versión K-way, de hecho, tiene un mejor rendimiento (a través de factores constantes bajas) si la memoria no es una restricción severa. Esto da lugar al siguiente punto:. Tendremos que comparar a la ordenación rápida por fusión de otros factores

ordenación rápida es generalmente más rápido que la ordenación por fusión

Esta comparación es completamente acerca de los factores constantes (si consideramos el caso típico). En particular, la elección es entre una opción subóptima del pivote para Quicksort frente a la copia de toda la entrada para la ordenación por fusión (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, que sólo pasa a ser más rápido

Tenga en cuenta que la ordenación rápida hará más llamadas recursivas, pero la asignación de espacio de pila es barato (casi libre, de hecho, siempre y cuando no sopla la pila) y volver a usarlo. La asignación de un bloque gigante en el montón (o el disco duro, si $ n $ es realmente grande) es un poco más caro, pero ambos son $ O (\ log n) $ gastos generales que palidecen en comparación con los $ O (n) $ trabajo mencionado anteriormente.

Por último, cabe destacar que la ordenación rápida es poco sensible a la entrada que pasa a ser en el orden correcto, en cuyo caso se puede omitir algunos intercambios. Mergesort no tiene ningún tipo de optimizaciones, que también hace ordenación rápida un poco más rápido en comparación con la ordenación por fusión.

Uso de la clase que se adapte a sus necesidades

En conclusión: no hay algoritmo de ordenación es siempre óptima. Seleccionar el método que se adapte a sus necesidades. Si necesita un algoritmo que es el más rápido para la mayoría de los casos, y no le importa que podría llegar a ser un poco lento en casos raros, y que no es necesario un establo tipo, utilice la ordenación rápida. De lo contrario, utilice el algoritmo que se adapte a sus necesidades mejor.

En uno de los tutoriales de programación en mi universidad, que pidió a los estudiantes a comparar el rendimiento de la clasificación rápida, mergesort, ordenación por inserción vs incorporada list.sort (llamado Timsort ). Los resultados experimentales me sorprendió profundamente desde el incorporado en list.sort realizado mucho mejor que otros algoritmos de clasificación, incluso con instancias que hacen fácil la clasificación rápida, accidente mergesort. Por lo que es prematuro concluir que la aplicación ordenación rápida habitual es el mejor en la práctica. Pero estoy seguro de que hay mucho mejor implementación de la clasificación rápida, o alguna versión híbrida de ella por ahí.

Este es un buen artículo de blog por David R. MacIver explicar como Timsort una forma de mergesort adaptativo.

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

Por lo tanto, cuando se inicia, se accede al primer elemento de la matriz y un trozo de memoria ( “localización”) se carga en la memoria caché. Y cuando intenta acceder al segundo elemento, es (lo más probable) que ya están en la memoria caché, por lo que es muy rápido.

Otros algoritmos como heapsort no trabajo como éste, saltan en la matriz de una gran cantidad, lo que les hace más lento.

Otros ya han dicho que el asintótica medio tiempo de ejecución de la ordenación rápida es mejor (en el constante) que el de los otros algoritmos de clasificación (en ciertos ambientes).

¿Qué significa eso? Asumir cualquier permutación se elige al azar (suponiendo una distribución uniforme). En este caso, los métodos de selección típico de pivote proporcionan pivotes que en la expectativa dividir la lista / matriz más o menos por la mitad; eso es lo que nos lleva a $ \ {cal} O (n \ log n) $. Pero, adicionalmente, fusión soluciones parciales obtenidos por recursividad sólo toma constante de tiempo (en contraposición a tiempo lineal en caso de la ordenación por fusión). Por supuesto, la separación de la entrada en dos listas de acuerdo con el pivote es en el tiempo lineal, pero a menudo requiere pocos swaps reales.

Tenga en cuenta que hay muchas variantes de ordenación rápida (véase, por ejemplo, la disertación de Sedgewick). Ellos actúan de forma diferente en diferentes distribuciones de entrada (uniforme, casi ordenadas, casi inversamente ordenados, muchos duplicados, ...), y otros algoritmos podría ser mejor para algunos.

Otro hecho digno destacar es que la ordenación rápida es lenta en las entradas cortas en comparación con los algoritmos Simper con menos sobrecarga. Por lo tanto, buenas bibliotecas no son recursivos a listas de longitud uno, pero se usan (por ejemplo) la ordenación por inserción si la longitud de entrada es más pequeño que algunos $ k \ aprox $ 10.

En comparación con otros algoritmos de clasificación basados ??en comparación con $ O (n \ lg n) $ complejidad del tiempo, rápido especie se considera a menudo mejor que otros algoritmos como fusión-tipo, ya que es un algoritmo en el lugar de clasificación. En otras palabras, no necesitamos la memoria (mucho más) para almacenar los miembros de la matriz.

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

Ver también:

Comparación de rápido-especie con otra algoritmos de ordenación

de heap-tipo con otros algoritmos de ordenación

A pesar de que tiene una clasificación rápida peor caso el tiempo de ejecución de $ \ theta (n ^ 2) $, quicksort es considerado el mejor clasificando porque es muy eficiente en el medio: su tiempo de ejecución esperado es $ \ theta (n \ log n) $ en donde las constantes son muy pequeñas en comparación con otros algoritmos de ordenación. Esta es la principal razón para usar rápida tipo sobre otros algoritmos de ordenación.

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

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

Para ilustrar esto mejor Déjenme darles un ejemplo usando Merge Sort (porque Combinar tipo es el algoritmo de clasificación junto ampliamente adoptada después de ordenación rápida, creo) y le dirá donde las constantes adicionales provienen de (a lo mejor de mi conocimiento y Por eso creo que es mejor rápida especie):

Considere el siguiente seqence:

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 usted se preocupa totalmente mira cómo la última etapa está sucediendo, primero 12 se compara con 8 y 8 es menor por lo que va en primer lugar. Ahora 12 es de nuevo en comparación con 21 y 12 va siguiente y así sucesivamente y así sucesivamente. Si se toma la fusión definitiva es decir, 4 elementos con otros 4 elementos, se incurre en una gran cantidad de comparaciones adicionales en forma de constantes que no se incurre en rápido Ordenado. Esta es la razón por la cual se prefiere ordenación rápida.

Mi experiencia de trabajo con los datos del mundo real es que quicksort es una mala elección . Ordenación rápida funciona bien con datos aleatorios, pero los datos del mundo real es lo más a menudo no es al azar.

Ya en 2008 me rastreó un error de software que cuelga hacia abajo para el uso de la clasificación rápida. Un rato después me escribió implentations simples de ordenación por inserción, clasificación rápida, pila de clasificación y ordenamiento por mezcla y se prueban estos. Mi ordenamiento por mezcla superó a todos los demás mientras se trabaja en grandes conjuntos de datos.

Desde entonces, la fusión es mi tipo algoritmo de ordenación de elección. Es elegante. Es fácil de implementar. Es una especie estable. No hace degenerado a un comportamiento cuadrática como quicksort hace. Me cambio a la inserción Ordenar para ordenar arreglos pequeños.

En muchas ocasiones he encontrado mi auto pensar que una implementación dada funciona sorprendentemente bien para la clasificación rápida, sólo para descubrir que en realidad no es la clasificación rápida. A veces, la aplicación cambia entre la clasificación rápida y otro algoritmo ya veces no utiliza la clasificación rápida en absoluto. A modo de ejemplo, qsort de glibc () funciona en realidad usos fusionan tipo. Sólo si la asignación del espacio de trabajo no lo hace caer de nuevo en el lugar ordenación rápida la que un comentario de código llamadas "el algoritmo más lento"
.
Editar: Los lenguajes de programación como Java, Python y Perl también utilizar la combinación de tipo, o más precisamente un derivado, tal como Timsort o de combinación de tipo de grandes conjuntos y ordenación por inserción para conjuntos pequeños. (Java también utiliza quicksort de doble pivote que es más rápido que quicksort llanura.)

1 - es rápida tipo in-situ (. No necesita memmory adicional, aparte de una cantidad constante)

2 -. rápido especie es más fácil de implementar que otros algoritmos de ordenación eficiente

3 -. rápida tiene una especie más pequeños factores constantes que es hora de que otros algoritmos de ordenación eficiente funcionamiento

Actualización: Por tipo de combinación, es necesario hacer un poco de "fusión", que necesita matriz extra (s) para almacenar los datos antes de la fusión; pero en la ordenación rápida, no lo hace. Es por eso que es una especie rápida en el lugar. También hay algunas comparaciones adicionales hechas para fusionar que aumentan los factores constantes en combinación tipo.

¿En qué condiciones es un algoritmo de ordenación específica en realidad el más rápido?

1) Cuando se implementa en forma paralela en hardware, ¿Es necesario tener una latencia razonablemente baja mientras que requiere el menor número posible de puertas? Sí -> usar un clasificador bitónica o Dosificadores par-impar mergesort, la latencia es $ \ theta (\ log (n) ^ 2) $ y el número de comparadores y multiplexores es de $ \ theta (n \ cdot \ log (n) ^ 2) $.

2) ¿Cuántos valores diferentes puede tener cada elemento? Latas cada posible valor han asignado un lugar único en la memoria o caché Sí -> Uso de recuento tipo u Radix sort, los que habitualmente tiene un tiempo de ejecución lineal de $ \ theta (n \ cdot k) $ (recuento especie) o $ \ theta (n \ cdot m) $ (cubo especie), pero más lento para obtener un gran número de diferentes valores, como $ k = 2 ^ {\ # número \ _of \ _Possible \ _values} $ y $ m = \ #maximum \ _length \ _of \ _keys $.

3) ¿La estructura de datos subyacente constan de elementos vinculados? Sí -> Allways uso en lugar de mezcla tipo. Hay tanto fácil de implementar tamaño fijo o adaptativo (también conocido como natural) de abajo hacia arriba en lugar tipo de combinación de diferentes arities para estructuras de datos enlazadas, y puesto que nunca requieren la copia de todos los datos en cada paso y que nunca requieren recurrencias o bien, son más rápido que cualquier otro tipo a base de COMPARACIÓN generales, incluso más rápido que el tipo rápido.

4) ¿Es necesario que la clasificación sea estable? Sí -> utilizar la combinación de especie, ya sea en el lugar o no, de tamaño fijo o adaptable, dependiendo de la estructura de datos subyacente y el tipo de datos que se espera, incluso en los casos en que de otro modo sería preferible ordenación rápida, como la estabilización de una clasificación arbitraria algoritmo requiere $ \ theta (n) $ memoria adicional en el peor de los casos consiste en índices originales, que también necesita que se le mantenga en sincronía con cada intercambio que se va a realizar en los datos de entrada, de modo que cada aumento de rendimiento que pueden ordenación rápida tiene más de una especie de combinación es probablemente frustrado.

5) ¿Puede el tamaño de los datos subyacentes estar unido a un tamaño pequeño a mediano? p.ej. Es N <10000 ... 100 000 000 (dependiendo de la arquitectura subyacente y estructura de datos)? Sí -> usar una especie bitónica o Dosificadores par-impar mergesort. Goto 1)

6) ¿Puede usted ahorrar otros $ \ theta (n) $ memoria? Sí -> a) ¿Los datos de entrada consisten en piezas de gran tamaño de los datos ya ordenados en secuencia? -> uso adaptativo (también conocido como natural) de combinación de tipo o de tipo tim Sí -> b) ¿Los datos de entrada consisten en su mayoría de elementos que son casi en el lugar correcto? -> burbuja del uso especie o tipo de inserción. Si tiene miedo de sus $ \ theta (n ^ 2) $ complejidad del tiempo (que es patológico para los datos de casi ordenada), tal vez considerar el cambio a la ordenación Shell con una (casi) la secuencia asintóticamente óptimo de lagunas, algunas secuencias que el rendimiento de $ \ theta ( n \ cdot \ log (n) ^ 2) peor caso el tiempo de ejecución $ son conocidos, o tal vez intente peine tipo. No estoy seguro de cualquiera de ordenación Shell o peine tipo llevaría a cabo razonablemente bien en la práctica.

No -> 7) ¿Puede usted ahorrar otros $ \ theta (\ log (n)) $ memoria? Sí -> a) ¿La estructura de datos de undelying permitir el acceso secuencial dirigida o mejor? Sí -> ¿Le permite sólo una única secuencia de accesos de lectura / escritura a la vez hasta el final de los datos se ha alcanzado (por ejemplo, acceso a la cinta dirigida)? Sí -> i) el uso de combinación de tipo, pero no hay manera obvia para hacer este caso en su lugar, por lo que puede requerir $ adicional \ theta (n) $ memoria. Pero si usted tiene el tiempo y las bolas para hacerlo, hay una manera de combinar 2 arrays en $ \ theta (n) $ vez usando sólo $ \ theta (\ log (n)) $ espacio de una manera estable, de acuerdo con Donald E. Knuth "The Art of Computer Programming, Volumen 3: Clasificación y búsqueda", el ejercicio 5.5.3. afirma que hay un algoritmo de L. Trabb-Pardo, que lo haga. Sin embargo, no creo que esto sería más rápido que la versión mergesort ingenuo o la ordenación rápida del caso anterior. No, que permite múltiples accesos simultáneos a una secuencia de datos (por ejemplo, no es una unidad de cinta) -> ii) uso quicksort, a efectos prácticos recomendaría ya sea un randomizeta o un uno mediana aproximada. Si se resisten a $ patológica \ theta (n ^ 2) $ casos, considere el uso de introducción especie. Si usted está empeñado en el comportamiento determinista, considere el uso de la mediana de la mediana algoritmo para seleccionar el elemento de pivote, se requiere $ \ theta (n) $ el tiempo y su aplicación ingenua requiere $ \ theta (n) $ Espacio (paralelizable ), mientras que puede ser implementado a sólo requieren $ \ theta (\ log (n)) $ espacio (no paralelizable). Sin embargo, el algoritmo de la mediana de la mediana le da una clasificación rápida determinista que tiene peor de los casos $ \ theta (n \ cdot \ log (n)) $ en tiempo de ejecución. No -> estás jodido (lo siento, necesitamos al menos 1 manera de acceder a cada elemento de los datos una vez)

No -> 8) ¿Puede usted ahorrar una pequeña cantidad constante de la memoria? Sí -> ¿La estructura de datos subyacente permite acceso aleatorio? Sí -> heapsort uso, tiene un óptimo tiempo de ejecución asintótica de $ \ theta (n \ cdot \ log (n)) $, pero la coherencia de caché pésimo y no paralelizar también. No -> que se atornillan No -> que se atornillan

consejos de implementación para la clasificación rápida:

1) Naive clasificación rápida binario requiere $ \ theta (n) $ memoria adicional, sin embargo, es relativamente fácil de reducir que reduce a $ \ theta (\ log (n)) $ reescribiendo la última llamada recursividad en un bucle . Hacer lo mismo para quicksorts k-ary para k> 2 requiere $ \ Theta (n ^ {\ log_k (k-1)}) $ espacio (de acuerdo con el teorema de maestro), por lo quicksort binario requiere la menor cantidad de memoria, pero me encantaría saber si alguien sabe si la clasificación rápida k-aria para k> 2 podría ser más rápido que la clasificación rápida binario en alguna configuración del mundo real.

2) No existe abajo hacia arriba, iterativo variantes de clasificación rápida, pero que yo sepa, no tienen el mismo espacio y tiempo límites asintóticos como el arriba hacia abajo queridos, con los lados hacia abajo adicionales de ser difícil de implementar (por ejemplo, la gestión de forma explícita cola). Mi experiencia es que para fines prácticos, los que no son dignos de considerarse.

consejos de implementación para mergesort:

1) Bottum arriba mergesort es siempre más rápido que mergesort de arriba hacia abajo, ya que no requiere llamadas de recursividad.

2) la mergesort muy ingenuo puede ser acelerado mediante el uso de un tampón doble y interruptor de la memoria intermedia en lugar de copiar la parte posterior de 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.

4) el algoritmo de combinación puede ser fácilmente parallelized por división de los datos de entrada en k partes aproximadamente del mismo tamaño. Esto requerirá k referencias en los datos, y es una cosa buena para elegir k tal que todas las k (o c * k para una pequeña constante c> = 1) encajan en la jerarquía de memoria más cercana (por lo general L1 caché de datos). La elección de la salida más pequeña de k elementos de la manera ingenua (búsqueda lineal) realiza $ \ theta (k) $ tiempo, mientras que la construcción de un min-montón dentro de esos k elementos y elegir el más pequeño sólo requiere amortizado $ \ theta (\ log ( k)) $ time (recogiendo el mínimo es de $ \ Theta (1) $ por supuesto, pero tenemos que hacer un poco de mantenimiento como un elemento es eliminado y reemplazado por otro en cada paso). La fusión parallelized siempre requiere de $ \ theta (n) $ memoria independientemente de k.

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

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

2) la estructura de datos subyacente no está vinculada

3) que no necesitamos un orden estable

4) de datos es lo suficientemente grande que el ligero sub-óptima asintótica tiempo de ejecución de un clasificador de bitónico o Dosificadores par-impar mergesort patadas en

5) los datos no clasificados y casi no consiste en grandes piezas ya ordenados

6) podemos acceder a la secuencia de datos simultáneamente desde varios lugares

7) { escrituras de memoria son especialmente caros (debido a que desventaja principal de de mergesort), la medida en que se ralentiza el algoritmo más allá de división sub-óptima probable de un quicksort. {O} nosotrossólo puede tener $ \ theta (\ log (n)) $ memoria adicional, $ \ theta (n) $ es demasiado (por ejemplo, el almacenamiento externo) }

necesidad p.s .: Alguien que me ayudara con el formato del texto.

La mayoría de las granulometrías métodos tienen que mover los datos en intervalos cortos (por ejemplo, ordenamiento por mezcla hace que los cambios a nivel local, a continuación, combina esta pequeña pieza de información, a continuación, combina una más grande. ..). En consecuencia, es necesario muchos movimientos de datos si los datos está lejos de su destino.

ordenación rápida, en el otro trata laterales para intercambiar números que están en la primera parte de la memoria y son grandes, con los números que se encuentran en la segunda parte de la matriz y son pequeños (si está ordenando $ a \ le b $, el argumento es el mismo en el otro sentido), por lo que obtener rápidamente asignan cerca de su destino final.

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

No afiliado a cs.stackexchange