algorithm - complexity - Quick Sort Vs Merge Sort
sorting algorithms complexity (11)
Además de los demás: Merge sort es muy eficiente para estructuras de datos inmutables como listas enlazadas y, por lo tanto, es una buena opción para lenguajes de programación (puramente) funcionales.
Un quicksort mal implementado puede ser un riesgo de seguridad .
Esta pregunta ya tiene una respuesta aquí:
- ¿Por qué Quicksort es mejor que mergesort? 29 respuestas
¿Por qué podría ser mejor ordenar rápidamente que fusionar?
La ordenación rápida suele ser más rápida que la ordenación por fusión cuando los datos se almacenan en la memoria. Sin embargo, cuando el conjunto de datos es enorme y se almacena en dispositivos externos, como un disco duro, el tipo de combinación es el claro ganador en términos de velocidad. Minimiza las costosas lecturas de la unidad externa y también se presta bien a la informática paralela.
La respuesta se inclinaría ligeramente hacia quicksort wrt a los cambios traídos con DualPivotQuickSort para valores primitivos. Se usa en JAVA 7 para 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
Lectura adicional impresionante en DualPivotQuickSort - http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628
No es cierto que el quicksort sea mejor. Además, depende de qué signifique mejor, consumo de memoria o velocidad.
En términos de consumo de memoria, en el peor de los casos, pero quicksort puede usar memoria n ^ 2 (es decir, cada partición es 1 a n-1), mientras que merge sort usa nlogn.
Lo anterior sigue en términos de velocidad.
Para Merge sort, el peor caso es O(n*log(n)) , para la ordenación rápida: O(n 2 ) . Para otros casos (promedio, mejor) ambos tienen O(n*log(n)) . Sin embargo, Quick sort es una constante de espacio donde Merge sort depende de la estructura que está ordenando.
Ver esta comparación
También puedes verlo visually .
Personalmente, quise probar la diferencia entre Quick sort y merge sort y vi los tiempos de ejecución para una muestra de 1,000,000 de elementos.
La ordenación rápida fue capaz de hacerlo en 156 milisegundos, mientras que el tipo de fusión hizo lo mismo en 247 milisegundos
Sin embargo, los datos de ordenación rápida fueron aleatorios y la clasificación rápida funciona bien si los datos son aleatorios, ya que no es el caso con el tipo de combinación, es decir, el tipo de fusión realiza de manera idéntica cuando los datos están ordenados o no. Pero el tipo de fusión requiere un espacio extra completo y el ordenamiento rápido no es un tipo de lugar en el lugar
He escrito un programa de trabajo integral para ellos con imágenes ilustrativas también.
Quicksort está en su lugar. Necesitas muy poca memoria extra. Lo cual es extremadamente importante.
Una buena elección de la mediana lo hace aún más eficiente, pero incluso una mala elección de la mediana de las garantías Theta (nlogn).
Quicksort está en su lugar. Solo necesita intercambiar posiciones de datos durante la función de Partición. Mergesort requiere mucha más copia de datos. Necesita otro almacenamiento temporal (generalmente el mismo tamaño que su matriz de datos original) para la función Fusionar.
Si bien el quicksort es a menudo una mejor opción que el tipo de combinación, definitivamente hay momentos en los que el tipo de fusión es una mejor opción. El momento más obvio es cuando es extremadamente importante que su algoritmo corra más rápido que O (n ^ 2). Quicksort suele ser más rápido que esto, pero dada la peor entrada teórica posible, podría ejecutarse en O (n ^ 2), que es peor que el peor tipo de combinación posible.
Quicksort también es más complicado que mergesort, especialmente si desea escribir una implementación realmente sólida, por lo que si busca simplicidad y capacidad de mantenimiento, el tipo de fusión se convierte en una alternativa prometedora con muy poca pérdida de rendimiento.
Ver Quicksort en wikipedia :
Típicamente, quicksort es significativamente más rápido 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 cuadráticos hora.
Tenga en cuenta que el requisito de memoria muy baja es una gran ventaja también.
quicksort se llama así por una razón,
Lo más destacado: ambos son géneros estables (simplemente una molestia en la implementación), así que pasemos a las complejidades
es muy confuso, con solo las anotaciones de big-oh derramadas y "abusadas", ambas tienen una complejidad promedio de casos de 0 (nlogn),
pero el tipo de fusión siempre es 0 (nlogn), mientras que el quicksort para particiones defectuosas, es decir, particiones sesgadas como 1 elemento-10 (que puede suceder debido a una lista clasificada o inversamente ordenada) puede llevar a 0 (n ^ 2) ..
.. y entonces hemos escogido aleatoriamente quicksort, donde seleccionamos el pivote aleatoriamente y evitamos esa partición sesgada, anulando así el escenario entero n ^ 2 de todos modos incluso para particiones moderadamente sesgadas como 3-4, tenemos un nlog (7/4) n , idealmente queremos 1-1 partición, por lo tanto los 2 enteros de O (nlog (2) n).
así que es O (nlogn), casi siempre y, a diferencia de merge sort, las constantes ocultas bajo la notación "big-oh" son mejores para quicksort que para mergesort ... y no usa espacio extra como merge sort.
pero hacer que quicksort funcione a la perfección requiere retoques, reformulaciones, quicksort le brinda la oportunidad de retocar ...