sort recursive codigo algoritmo java algorithm quicksort mergesort

java - recursive - mergesort c++ codigo



Quicksort más lento que Mergesort? (15)

Estaba trabajando en la implementación de un quicksort ayer, y luego lo ejecuté, esperando un tiempo de ejecución más rápido que el Mergesort (que también había implementado). Ejecuté los dos, y aunque el quicksort era más rápido para conjuntos de datos menores <100 elementos (y sí comprueve que funciona), el mergesort se convirtió rápidamente en el algoritmo más rápido. Me habían enseñado que el quicksort es casi siempre "más rápido" que mergesort, y entiendo que haya algún debate sobre este tema, pero al menos esperaba que fuera más cercano. Para conjuntos de datos> 10000 elementos, el mergesort fue más de 4 veces más rápido. ¿Es esto esperado, o hay un error en mi código quicksort?

mergesort:

public static void mergeSort(int[ ] e) { if (e.length <= 1) return; int[] first = new int[e.length/2]; int[] second = new int[e.length - first.length]; System.arraycopy(e, 0, first, 0, first.length); System.arraycopy(e, first.length, second, 0, second.length); mergeSort(first); mergeSort(second); System.arraycopy(merge(first, second), 0, e, 0, e.length); } private static int[] merge(int[] first, int[] second) { int iFirst = 0; int iSecond = 0; int iCombined = 0; int[] combined = new int[first.length + second.length]; while(iFirst < first.length && iSecond < second.length) { if (first[iFirst] > second[iSecond]) { combined[iCombined++] = second[iSecond++]; } else combined[iCombined++] = first[iFirst++]; } for(; iFirst < first.length; iFirst++) { combined[iCombined++] = first[iFirst]; } for(; iSecond < second.length; iSecond++) { combined[iCombined++] = second[iSecond]; } return combined; }

ordenación rápida:

public static void quicksort(int[] a, int first, int last) { if (first >= last) return; int partitionIndex = partition(a, first, last); quicksort(a, first, partitionIndex - 1); quicksort(a, partitionIndex + 1, last); } public static int partition(int[] x, int first, int last) { int left = first; int right = last; int pivot = x[first]; int pivotIdx = first; while(left <= right) { while(left < x.length && x[left] <= pivot) left++; while(right >= 0 && x[right] > pivot) right--; if (left <= right) { int temp = x[left]; x[left] = x[right]; x[right] = temp; } } pivotIdx = right; x[first] = x[right]; x[pivotIdx] = pivot; return pivotIdx; }

¿Fueron los conjuntos de datos lo suficientemente aleatorios? ¿Estaban parcialmente clasificados?

Eso podría afectar la velocidad del género ...

Al igual que para la partición QuickSort (), se saltearía si los números están ordenados, hasta que encuentre uno que no lo esté.

(1) Hay un qsort algo, utilizado por C qsort (), que no requiere memoria extra. Esto fue muy probablemente inventado por Hoare. Esto hace qsort () rápido en C.

(2) Aleatorizar los datos antes de ejecutar qsort casi siempre lo acelerará.

(3) seleccionar los datos de la mediana para pivote puede hacerlo más rápido,

Basado en este artículo de Wikipedia, se esperan sus resultados.

El peor caso de Merge sort es el caso promedio de quicksort, por lo que si no tiene una buena implementación, el tipo de fusión será más rápido en general. Hacer que quicksort trabaje rápido es evitar casos por debajo del promedio. Elige un pivote mejor (la mediana de 3 ayuda) y verás una diferencia.

Esto es consistente con el análisis de los algoritmos. Merge-sort está garantizado O (nlogn) para cualquier entrada y para cada tiempo de ejecución. Quicksort es el mejor de los casos O (nlogn) y el caso promedio O (nlogn), pero el caso más desfavorable O (n ^ 2), por lo que la ejecución promedio será entre O (nlogn) y O (n ^ 2).

Quicksort es el mejor algoritmo de caso general porque tiene una sobrecarga baja, por lo que tiene una buena velocidad para valores de n de hasta aproximadamente 10000 y sigue siendo un buen tiempo de ejecución para valores arbitrariamente astronómicos de n. Merge-sort tiene la desafortunada sobrecarga de escribir un marco de pila, requerido por cada llamada recursiva. Por lo tanto, para valores bajos de n tiene una c atrozmente alta en RT = cnlogn y no es el método de clasificación general preferido.

Editar: Software Monkey señaló una contradicción: Quicksort promedia O (nlogn) para la entrada aleatoria, pero O (n ^ 2) el peor de los casos. Por lo tanto, en realidad está un poco vinculado por la entropía de sus datos, o puede elegir el pivote de forma aleatoria. Sin embargo, aún podría estar fuera un poco.

Me podría imaginar que accediendo directamente a la memoria, usando C, por ejemplo, uno puede mejorar el rendimiento de Quicksort más de lo que es posible con Mergesort.

Otra razón es que Mergesort necesita más memoria porque es difícil implementarla como una ordenación in situ.

Y específicamente para su implementación, puede mejorar la elección del pivote, hay muchos algoritmos diferentes para encontrar un buen pivote.

Como se puede ver en wikipedia , uno puede implementar Quicksort de diferentes maneras.

Para un buen rendimiento de quicksort, es importante no volver a recurrir a listas de longitud 1

Debería considerar ordenar las listas de 2, 3 e incluso 4 como intercambios anidados si es necesario. Háganos saber cómo cambia el rendimiento.

Puede depender del tipo de datos que clasifique para la prueba (listas ya ordenadas, aleatorias, ordenadas de forma inversa). Además, es probable que el quicksort sea más rápido en general si elige un pivote aleatorio en lugar de usar el primer elemento.

Si implementa la clasificación de montón como el algoritmo de clasificación base en el peor de los casos, obtiene un algoritmo theta (n log n).

Si no necesita una clasificación estable, y no ordena una lista vinculada, creo que sería lo más rápido que podría ir.

Tipo de fusión

Una de las ventajas de quicksort para tamaños de matriz relativamente pequeños es solo un artefacto de implementación de hardware.

En las matrices, la ordenación rápida se puede realizar in situ, lo que significa que está leyendo y escribiendo en la misma área de la memoria. Mergesort, por otro lado, generalmente requiere asignar nuevos buffers, lo que significa que su acceso a la memoria está más extendido. Puede ver estos dos comportamientos en sus implementaciones de ejemplo.

Como resultado, para conjuntos de datos relativamente pequeños, es más probable que quicksort obtenga hits de caché y, por lo tanto, tiende a ejecutarse más rápido en la mayoría del hardware.

Mergesort sigue siendo una solución bastante buena para grandes conjuntos de datos u otras estructuras de datos, como listas vinculadas, como lo confirman sus experimentos.

Mergesort es mucho más lento para los datos basados ​​en arreglos aleatorios, siempre que se ajuste en RAM. Esta es la primera vez que lo veo debatido.

  • qsort el subarreglo más corto primero.
  • cambiar a ordenación de inserción por debajo de 5-25 elementos
  • hacer una selección de pivote normal

Su qsort es muy lento porque intenta dividir y ordenar matrices de longitud 2 y 3.

Creo que siempre que los datos quepan en la memoria, una buena implementación de tipo de combinación tiene mejor rendimiento que una buena implementación de ordenamiento rápido.

Una de las implementaciones más utilizadas de qsort (), glibc qsort (), internamente utiliza el tipo de fusión para la mayoría de los casos cuando los datos encajan en la memoria. Este tipo de combinación asigna un espacio de memoria temporal utilizado para la fusión, lo que agrega cierta sobrecarga de memoria, pero la mayoría de las veces supera a su propia implementación interna de quicksort con una buena selección de pivote y optimización. glibc solo usa quicksort cuando los datos y la memoria temporal para ordenar por fusión no caben en la memoria.

He medido el rendimiento de esas dos implementaciones en mi máquina con una CPU de 2.1 GHz con varios GB de RAM. Las entradas se generan con un generador pseudoaleatorio, y cada clave es un entero sin signo de 32 bits, lo que significa un poco más de ciclos de comparación que la comparación entera debido a la interfaz de la función de comparación.

Para el tipo de fusión:

2 MB, time_diff 165.156000 ms, 78.752518 ns per byte 4 MB, time_diff 344.298000 ms, 82.087040 ns per byte 8 MB, time_diff 730.926000 ms, 87.133169 ns per byte 16 MB, time_diff 1541.215000 ms, 91.863573 ns per byte 32 MB, time_diff 3088.924000 ms, 92.057109 ns per byte 64 MB, time_diff 6262.868000 ms, 93.324006 ns per byte 128 MB, time_diff 12887.018000 ms, 96.015766 ns per byte 256 MB, time_diff 26731.597000 ms, 99.582959 ns per byte

Para ordenar rápidamente:

2 MB, time_diff 243.519000 ms, 116.118908 ns per byte 4 MB, time_diff 504.975000 ms, 120.395422 ns per byte 8 MB, time_diff 1075.276000 ms, 128.182888 ns per byte 16 MB, time_diff 2183.865000 ms, 130.168498 ns per byte 32 MB, time_diff 4343.993000 ms, 129.461080 ns per byte 64 MB, time_diff 8714.166000 ms, 129.851192 ns per byte 128 MB, time_diff 17881.344000 ms, 133.226395 ns per byte 256 MB, time_diff 36751.029000 ms, 136.908252 ns per byte

Puede ver que hay claras diferencias en el rendimiento entre esas dos implementaciones y por qué se prefiere a mergesort sobre quicksort en esta implementación de qsort ampliamente utilizada. La razón principal detrás de esta diferencia parece ser que el género rápido tiene un 10-20% más de comparaciones que el tipo de combinación, debido a la división desigual en cada paso.

De hecho, escribí un "programa demo demográfico comparativo de listas enlazadas" en C y llegué a una conclusión similar (que mergesort superará a quicksort para la mayoría de los usos), aunque me han dicho que el quicksort generalmente no se usa para listas vinculadas. Me gustaría señalar que la elección de los valores de pivote es un factor monstruo: mi versión inicial usó un nodo aleatorio como pivote, y cuando la refiné un poco para tomar una media de dos nodos (aleatorios), el tiempo de ejecución para 1000000 registros pasó de más de 4 minutos a menos de 10 segundos, poniéndolo a la par con mergesort.

Mergesort y quicksort tienen el mismo gran O mejor caso (n * log (n)) y, a pesar de lo que la gente pueda tratar de decir, el gran O realmente se trata del recuento de iteraciones y no del recuento de comparación. La mayor diferencia que se puede producir entre los dos siempre será en detrimento del quicksort, e involucra listas que ya están ordenadas o contienen una gran cantidad de vínculos (cuando el quicksort es mejor que el mergesort, la diferencia no será tan grande estupendo). Esto se debe a que los vínculos o los segmentos ya ordenados optimizan directamente a través de mergesort; cuando vuelvan a fusionarse dos listas divididas, si una lista ya contiene todos los valores más pequeños, todos los valores de la izquierda se compararán uno a la vez con el primer elemento de la derecha y luego (dado que las listas devueltas tienen una orden interno) no es necesario hacer más comparaciones y el derecho simplemente se itera al final. Es decir, el número de iteraciones se mantendrá constante, pero el número de comparaciones se reducirá a la mitad. Si está hablando de tiempo real y está ordenando cadenas, son las comparaciones las que son caras.

Los vínculos y los segmentos ya clasificados en la orden rápida pueden conducir fácilmente a listas desequilibradas si el valor de pivote no se determina con cuidado, y las listas desequilibradas (por ejemplo, una a la derecha, diez a la izquierda) son las que causan la ralentización. Por lo tanto, si puede hacer que su quicksort funcione tan bien en una lista ya ordenada como en una lista ramificada, tiene un buen método para encontrar el pivote.

Si está interesado, el programa de demostración produce resultados como este:

[root~/C] ./a.out -1 3 Using "", 0 records Primary Criteria offset=128 Command (h for help, Q to quit): N How many records? 4000000 New list is 562500.00 kb Command (h for help, Q to quit): m Mergesorting..............3999999 function calls 123539969 Iterations Comparison calls: 82696100 Elapsed time: 0 min 9 sec Command (h for help, Q to quit): S Shuffled. Command (h for help, Q to quit): q Quicksorting..............4000000 function calls 190179315 Iterations Comparison calls: 100817020 Elapsed time: 0 min 23 sec

Aunque sin los kolors krazy. Hay más cosas sobre mí a mitad de esta página .

PD. ninguna clase requiere memoria adicional con la lista vinculada.

Ejecuté pruebas similares y la ordenación rápida pura (con selección aleatoria de pivote) resultó ser mucho más lenta que la ordenación por fusión para arreglos grandes.

Elegir el pivote como la mediana del primer, medio y último elemento mejoró el rendimiento de la ordenación rápida, pero el ordenamiento rápido fue definitivamente peor que el de fusión en matrices grandes (> 100000 elementos).

Observé una gran mejora cuando implementé intro-sort, es decir, ordenación rápida que vuelve a la ordenación de pila si la profundidad de recursión excede un cierto umbral. Mi implementación de tipo de introducción fue casi tan rápida como mi implementación de tipo de combinación. Por supuesto, intro-sort ya no es una clasificación pura y rápida, ya que utiliza la ordenación de montones para devolver la complejidad a n log (n) cuando la ordenación pura y rápida llega a algunos datos erróneos. Puedo publicar los resultados si estás interesado.