Ordenación rápida vs heapsort

https://stackoverflow.com/questions/2467751

20-09-2019
|

Pregunta

Tanto la clasificación rápida y heapsort hacer la clasificación en el lugar. ¿Cual es mejor? ¿Cuáles son las aplicaciones y casos en los que, o bien se prefiere?

Solución

Este documento tiene algunos análisis.

Además, de Wikipedia:

El competidor más directo de quicksort es heapsort. heapsort es típicamente algo más lento de lo la clasificación rápida, pero el peor de los casos corriendo el tiempo es siempre Θ (nlogn). quicksort es por lo general más rápido, aunque sigue existiendo la posibilidad de peor desempeño caso excepto en la variante introsort, que interruptores para HeapSort cuando un caso grave se detecta. Si se sabe de antemano heapsort que va a ser es necesario, usando directamente será más rápido que esperar a introsort cambiar a él.

Otros consejos

heapsort es O (N log N) guaranted, lo que es mucho mejor que el peor caso en Quicksort. Heapsort no necesita más memoria para otra matriz para poner datos ordenados como sea necesario mediante la ordenación por fusión. Entonces, por qué las aplicaciones comerciales se pega con la ordenación rápida? Lo que tiene la ordenación rápida que es tan especial sobre los demás implementaciones?

He probado los algoritmos de mí mismo y he visto que la ordenación rápida tiene algo especial. Se ejecuta algoritmos rápidos, mucho más rápido que Heap y Combinar.

El secreto de ordenación rápida es: Casi no hace permutas de elementos innecesarios. Swap es mucho tiempo.

Con heapsort, incluso si todos los datos ya están ordenados, que se van a intercambiar el 100% de los elementos para ordenar la matriz.

Con la ordenación por fusión, es aún peor. Usted va a escribir el 100% de los elementos de otra matriz y escribir de nuevo en el original, incluso si los datos ya están ordenados.

Con la ordenación rápida que no intercambia lo que ya se ordenó. Si los datos se ordenó por completo, se intercambian casi nada! Aunque hay una gran cantidad de quejarse sobre el peor de los casos, una pequeña mejora en la elección del pivote, cualquier otro que conseguir el primer o el último elemento de la matriz, puede evitarlo. Si obtiene un pivote del elemento intermedio entre el primero, último y media del elemento, es suficiente parar para evitar la peor de los casos.

Lo que es superior en la ordenación rápida no es el peor de los casos, pero el mejor de los casos! En mejor de los casos lo hace el mismo número de comparaciones, ok, pero se intercambian casi nada. En caso promedio se intercambia parte de los elementos, pero no todos los elementos, como en heapsort y ordenación por fusión. Eso es lo que da la ordenación rápida el mejor momento. Menos de intercambio, más velocidad.

La aplicación a continuación en C # en mi equipo, que se ejecuta en modo de lanzamiento, latidos Array.Sort por 3 segundos con pivote central y de 2 segundos con una mejor pivote (sí, hay una sobrecarga de conseguir un buen pivote).

static void Main(string[] args)
{
    int[] arrToSort = new int[100000000];
    var r = new Random();
    for (int i = 0; i < arrToSort.Length; i++) arrToSort[i] = r.Next(1, arrToSort.Length);

    Console.WriteLine("Press q to quick sort, s to Array.Sort");
    while (true)
    {
        var k = Console.ReadKey(true);
        if (k.KeyChar == 'q')
        {
            // quick sort
            Console.WriteLine("Beg quick sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff"));
            QuickSort(arrToSort, 0, arrToSort.Length - 1);
            Console.WriteLine("End quick sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff"));
            for (int i = 0; i < arrToSort.Length; i++) arrToSort[i] = r.Next(1, arrToSort.Length);
        }
        else if (k.KeyChar == 's')
        {
            Console.WriteLine("Beg Array.Sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff"));
            Array.Sort(arrToSort);
            Console.WriteLine("End Array.Sort at " + DateTime.Now.ToString("HH:mm:ss.ffffff"));
            for (int i = 0; i < arrToSort.Length; i++) arrToSort[i] = r.Next(1, arrToSort.Length);
        }
    }
}

static public void QuickSort(int[] arr, int left, int right)
{
    int begin = left
        , end = right
        , pivot
        // get middle element pivot
        //= arr[(left + right) / 2]
        ;

    //improved pivot
    int middle = (left + right) / 2;
    int
        LM = arr[left].CompareTo(arr[middle])
        , MR = arr[middle].CompareTo(arr[right])
        , LR = arr[left].CompareTo(arr[right])
        ;
    if (-1 * LM == LR)
        pivot = arr[left];
    else
        if (MR == -1 * LR)
            pivot = arr[right];
        else
            pivot = arr[middle];
    do
    {
        while (arr[left] < pivot) left++;
        while (arr[right] > pivot) right--;

        if(left <= right)
        {
            int temp = arr[right];
            arr[right] = arr[left];
            arr[left] = temp;

            left++;
            right--;
        }
    } while (left <= right);

    if (left < end) QuickSort(arr, left, end);
    if (begin < right) QuickSort(arr, begin, right);
}

Para la mayoría de las situaciones, teniendo rápida frente a un poco más rápido es irrelevante ... simplemente no quiero que esté en ocasiones waayyy lento. Aunque se puede ajustar QuickSort para evitar las situaciones de forma lenta, se pierde la elegancia de la QuickSort básica. Por lo tanto, para la mayoría de las cosas, en realidad prefieren HeapSort ... se puede poner en práctica en su elegancia sencilla completa, y nunca obtener una especie lenta.

En situaciones en las que desee velocidad máxima en la mayoría de los casos, QuickSort puede ser preferible a HeapSort, pero tampoco puede ser la respuesta correcta. Para situaciones de velocidad crítica, vale la pena examinar de cerca los detalles de la situación. Por ejemplo, en algunos de mi código de velocidad crítica, es muy común que los datos ya está ordenada o casi ordenadas (que está indexando relacionada múltiples campos que a menudo tampoco se mueven arriba y abajo juntos o se mueven arriba y abajo frente a la otra, así que una vez ordenar por uno, los otros están bien ordenados o revertir-ordenados o cerca ... cualquiera de los cuales puede matar QuickSort). Para ese caso, he implementado ni ... en cambio, he implementado SmoothSort de Dijkstra ... HeapSort una variante que es O (N) si ya ordenadas o casi ordenados ... no es tan elegante, no muy fácil de entender, pero rápido ... leer http://www.cs.utexas.edu /users/EWD/ewd07xx/EWD796a.PDF si quieres algo un poco más difícil de codificar.

Quicksort-HeapSort híbridos en el lugar son realmente interesante, también, ya que la mayoría de ellos sólo se necesita n * log n comparaciones en el peor de los casos (que son óptimas con respecto al primer término de los asintótica, lo que evitan el peor escenarios ASUNTO de Quicksort), O (log n)-espacio adicional y que preservan conjunto al menos "un medio" de la buena conducta de Quicksort con respecto a ordenó ya de datos. Un algoritmo muy interesante es presentado por Dikert y Weiss en http://arxiv.org/pdf/1209.4214v1. pdf :

Seleccione un pivote p como la mediana de una muestra aleatoria de sqrt (n) elementos (esto se puede hacer en las comparaciones a lo sumo 24 sqrt (n) a través del algoritmo de comparaciones Tarjan & co, o 5 sqrt (n) a través de la mucho algoritmo de araña en fábrica más enrevesado de Schonhage);
Partición su matriz en dos partes como en la primera etapa de Quicksort;
Heapify la más pequeña parte y el uso O (log n) bits adicionales para codificar un montón en el que cada hijo izquierdo tiene un valor mayor que su hermano;
recursivamente extracto de la raíz del montón, tamizar abajo de la lacune dada por la raíz hasta que llega a una hoja de la pila, a continuación, llenar el lacune con un elemento apropiado tomó de la otra parte de la matriz;
repetirse durante la parte restante no ordenada de la matriz (si p se elige como la mediana exacta, no hay recursión en absoluto).

Comp. entre quick sort y merge sort ya que ambos son el tipo de en su lugar clasificando hay una diferencia entre el caso wrost tiempo del caso wrost tiempo de ejecución para la ordenación rápida ejecución se O(n^2) y de pila de clasificación se sigue O(n*log(n)) y por un importe medio de los datos de tipo Quick ser más útil. Puesto que es el algoritmo aleatorio por lo que la probabilidad de obtener ans correctas. en menos tiempo dependerá de la posición del elemento de pivote que elija.

Así que un

Buena llamada: los tamaños de L y G son cada uno menos de 3s / 4

llamada malo: uno de L y G tiene un tamaño mayor que 3S / 4

para la pequeña cantidad que podemos ir para la ordenación por inserción y por muy gran cantidad de datos van de pila de clasificación.

Bueno, si vas a nivel de arquitectura ... utilizamos cola de estructura de datos en la memoria caché memory.so lo que cada vez está disponible en la cola recibirá sorted.As de tipo rápida tenemos ningún problema dividiendo la matriz en cualquier longitud ... pero en la pila de clasificación (mediante el uso de matriz), puede ocurrir que los padres pueden no estar presentes en la matriz sub disponible en caché y luego tiene que llevarlo en la memoria caché ... lo cual es mucho tiempo. Esa es la clasificación rápida es mejor !!

heapsort construye un montón y luego extrae varias veces el elemento de máxima. Su peor caso es O (n log n).

Pero si quieren ver el peor caso de href="http://en.wikipedia.org/wiki/Quicksort" rápida tipo , que es O (n2 ), se dio cuenta de que lo haría ese tipo rápida sería una no tan buena opción para grandes volúmenes de datos.

Así que esto hace que la clasificación es una cosa interesante; Creo que la razón por la que muchos algoritmos de ordenación viven en la actualidad se debe a que todos ellos son 'mejor' en sus mejores lugares. Por ejemplo, la ordenación de burbuja puede realizar a cabo ordenación rápida si se ordena los datos. O si sabemos algo acerca de los artículos que ser resuelto entonces probablemente podemos hacerlo mejor.

Esto puede no responder a su pregunta directamente, que me gustaría añadir mi granito de arena.

heapsort tiene la ventaja de tener un peor de los casos funcionamiento de O (n * log (n)) por lo que en los casos en que es probable que sea un mal desempeño ordenación rápida (principalmente datos ordenada establece en general) heapsort es mucho preferido.

Heap Sort es una apuesta segura cuando se trata de grandes entradas. El análisis revela asintótica orden de crecimiento de heapsort en el peor de los casos es Big-O(n logn), que es mejor que Big-O(n^2) de ordenación rápida como peor de los casos. Sin embargo, heapsort es algo más lento en la práctica en la mayoría de máquinas que una especie rápida bien implementado. También heapsort no es un algoritmo de ordenación estable.

La razón heapsort es más lento en la práctica que la clasificación rápida se debe a la mejor localidad de referencia ( " https: / /en.wikipedia.org/wiki/Locality_of_reference ") en quicksort, donde los elementos de datos se encuentran dentro de los lugares de almacenamiento relativamente cercanos. Los sistemas que tienen una fuerte localidad de referencia son grandes candidatos para la optimización del rendimiento. Pila de clasificación, sin embargo, se ocupa de los saltos más grandes. Esto hace que la clasificación rápida más favorable para las entradas más pequeñas.

Para mí hay una diferencia muy fundamental entre heapsort y clasificación rápida: este último utiliza un recursividad. En los algoritmos recursivos el montón crece con el número de recurrencias. Esto no importa si n es pequeño, pero en este momento estoy clasificando dos matrices con n = 10 ^ 9 !!. El programa lleva casi 10 GB de RAM y cualquier memoria adicional hará que el ordenador para iniciar el intercambio de memoria de disco virtual. Mi disco es un disco RAM, pero aún así el intercambio en que hacer un gran diferencia en la velocidad . Así que en un statpack codificado en C ++ que incluye matrices de dimensiones ajustables, con tamaño desconocido de antemano para el programador, y el tipo de estadística no paramétrica de clasificar prefiero el heapsort para evitar retrasos a usos de muy grandes matrices de datos.

Para responder a la pregunta original y abordar algunos de los otros comentarios aquí:

Yo sólo comparado implementaciones de selección, rápida, combinar, y pila de clasificación para ver cómo habían apilan uno contra el otro. La respuesta es que todos ellos tienen sus desventajas.

TL; DR: Rápida es el mejor tipo de propósito general (razonablemente rápido, estable, y sobre todo en el lugar) Personalmente prefiero pila de clasificación, aunque a menos que necesito una especie estable.

Selección - N ^ 2 - Es realmente sólo es bueno para menos de 20 elementos o menos, entonces se superó. A menos que los datos ya están ordenados, o muy, muy casi. N ^ 2 se pone muy lento muy rápido.

rápida, en mi experiencia, no es en realidad que rápido todo el tiempo. Bonificaciones para el uso de ordenación rápida como una especie general, sin embargo son que es bastante rápido y es estable. Es también un algoritmo en el lugar, pero como es generalmente implementado de forma recursiva, que ocupará espacio de pila adicional. También cae en algún lugar entre O (n log n) y O (n ^ 2). El tiempo en algunos tipos parecen confirmar esto, especialmente cuando los valores caen dentro de un rango estrecho. Es mucho más rápido que la selección especie de 10.000.000 de artículos, pero más lento que fusionar o montón.

Combinar O especie está garantizada (n log n) desde su especie no depende de los datos. Simplemente hace lo que hace, independientemente de los valores que se ha incorporado. También es estable, pero muy grandes tipo puede dañar tu pila si no tiene cuidado acerca de la implementación. Hay algún complejo en el lugar de combinación de implementaciones de ordenación, pero por lo general se necesitan otra matriz en cada nivel para fusionar sus valores en. Si esas matrices viven en la pila puede que tenga problemas.

pila de clasificación es Max O (n log n), pero en muchos casos es más rápido, dependiendo de lo lejos que tiene que mover los valores de seguridad del registro de n montón de profundidad. El montón se puede implementar fácilmente en el lugar de la matriz original, por lo que no necesita memoria adicional, y es iterativo, por lo que no se preocupa por desbordamiento de pila, mientras que de manera recursiva. El enorme desventaja de pila de clasificación es que no es una especie estable, lo que significa que está bien si necesitas que.

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

No afiliado a StackOverflow