algorithm - recursive - mergesort geek

¿Cuando se prefiere la ordenación por combinación a la ordenación rápida?

Question

La ordenación rápida es mucho mejor que la ordenación por fusión en muchos casos. Sin embargo, ¿cuándo son los casos en que la clasificación por fusión puede ser una solución mejor que la clasificación rápida?

Por ejemplo, la clasificación de combinación funciona mejor que la clasificación rápida cuando los datos no se pueden cargar en la memoria de una vez. ¿Hay otros casos?

EDITAR: Las respuestas de la pregunta duplicada sugerida enumera todas las ventajas de la ordenación rápida sobre la ordenación de mezcla. Aquí estoy preguntando sobre los posibles casos y aplicaciones que usar la ordenación de fusión sería ventajoso que usar la ordenación rápida.

Answer 1

1. Merge Sort La complejidad del peor caso es O (nlogn) mientras que el peor caso de Quick Sort es O (n ^ 2).
2. La clasificación de mezcla es una clasificación estable, lo que significa que el mismo elemento en una matriz mantiene sus posiciones originales entre sí.

Answer 2

1. MergeSort es estable por diseño, elementos iguales mantienen su orden original.
2. MergeSort está bien adaptado para ser implementado en paralelo (multihilo).
3. MergeSort utiliza (alrededor del 30%) menos comparaciones que QuickSort. Esta es una ventaja que a menudo se pasa por alto, porque una comparación puede ser bastante costosa (por ejemplo, al comparar varios campos de filas de la base de datos).

Answer 3

La clasificación de fusión tiene un límite superior garantizado de O (N log ₂ N). La ordenación rápida también tiene ese límite, pero es mucho más alta: es O (N ² ). Cuando necesite un límite superior garantizado en el tiempo de su código, use la ordenación por fusión en lugar de la ordenación rápida.

Por ejemplo, si escribe código para un sistema en tiempo real que se basa en la clasificación, la clasificación por fusión sería una mejor opción.

Answer 4

Probablemente debería comenzar mencionando que tanto Quicksort como Mergesort pueden funcionar bien si no puedes guardar todo en la memoria al mismo tiempo. Puede implementar la ordenación rápida al elegir un pivote, luego transmitir los elementos desde el disco a la memoria y escribir los elementos en uno de dos archivos diferentes según la forma en que ese elemento se compara con el pivote. Si usa una cola de prioridad de doble extremo, puede hacer esto de manera aún más eficiente si ajusta el número máximo de elementos posibles en la memoria de una vez.

Otros han mencionado el beneficio de que Mergesort es el caso más desfavorable O (n log n), lo que es definitivamente cierto. Dicho esto, puede modificar fácilmente la introsort rápida para producir el algoritmo introsort , un híbrido entre la ordenación rápida, la ordenación por inserción y la introsort ; ese es el caso más desfavorable O (n log n) pero conserva la velocidad de la ordenación rápida en la mayoría de los casos.

Podría ser útil ver por qué quicksort suele ser más rápido que mergesort, ya que si comprende las razones, puede encontrar rápidamente algunos casos en los que mergesort es un claro ganador. Quicksort generalmente es mejor que mergesort por dos razones:

1. Quicksort tiene una mejor localidad de referencia que mergesort, lo que significa que los accesos realizados en quicksort son generalmente más rápidos que los accesos correspondientes en mergesort.

2. Quicksort utiliza la memoria O (log n) en el peor de los casos (si se implementa correctamente), mientras que mergesort requiere memoria O (n) debido a la sobrecarga de la fusión.

Hay un escenario, sin embargo, donde desaparecen estas ventajas. Supongamos que desea ordenar una lista de elementos vinculados. Los elementos de la lista enlazada están dispersos en toda la memoria, por lo que la ventaja (1) desaparece (no hay una localidad de referencia). En segundo lugar, las listas vinculadas se pueden combinar solo con una sobrecarga de espacio O (1) en lugar de una sobrecarga de espacio O (n), por lo que la ventaja (2) desaparece. Por consiguiente, generalmente encontrará que mergesort es un algoritmo superior para ordenar las listas vinculadas, ya que hace menos comparaciones totales y no es susceptible a una mala elección de pivote.

¡Espero que esto ayude!

Answer 5

Quicksort es el caso promedio O (n log n), pero tiene el peor de los casos O (n ^ 2). Mergesort siempre es O (n log n). Además del peor caso asintótico y la carga de memoria de mergesort, no puedo pensar en otra razón.

Escenarios cuando quicksort es peor que mergesort:

1. La matriz ya está ordenada.
2. Todos los elementos de la matriz son iguales.
3. La matriz está ordenada en orden inverso.

Tome mergesort en quicksort si no sabe nada acerca de los datos.

Answer 6

Una de las ventajas más importantes de la clasificación por fusión sobre la clasificación rápida es su estabilidad: los elementos comparados conservan su orden original.