Clasificación rápida vs clasificación heap

Tanto la clasificación rápida como la clasificación en pila realizan la clasificación en el lugar. ¿Cual es mejor? ¿Cuáles son las aplicaciones y los casos en los que se prefiere una u otra?

Este papel tiene algunos análisis.

Además, de Wikipedia:

El competidor más directo de quicksort es heapsort. Heapsort suele ser algo más lento que quicksort, pero el peor tiempo de ejecución es siempre Θ (nlogn). La ordenación rápida suele ser más rápida, aunque existe la posibilidad de un rendimiento en el peor de los casos, excepto en la variante introsort, que cambia a la ordenación en pila cuando se detecta un caso incorrecto. Si se sabe de antemano que será necesario ordenar heapsort, usarlo directamente será más rápido que esperar a que introsort cambie a él.

Heapsort está garantizado por O (N log N), lo que es mucho mejor que el peor de los casos en Quicksort. Heapsort no necesita más memoria para que otra matriz coloque datos ordenados como lo necesita Mergesort. Entonces, ¿por qué las aplicaciones comerciales se quedan con Quicksort? ¿Qué Quicksort tiene que sea tan especial sobre otras implementaciones?

Yo mismo he probado los algoritmos y he visto que Quicksort tiene algo especial. Se ejecuta rápido, mucho más rápido que los algoritmos Heap y Merge.

El secreto de Quicksort es: casi no realiza intercambios de elementos innecesarios. El intercambio lleva mucho tiempo.

Con Heapsort, incluso si todos sus datos ya están ordenados, intercambiará el 100% de los elementos para ordenar la matriz.

Con Mergesort, es aún peor. Va a escribir el 100% de los elementos en otra matriz y volver a escribirla en la original, incluso si los datos ya están ordenados.

Con Quicksort no intercambia lo que ya está ordenado. Si sus datos están completamente ordenados, ¡no intercambia casi nada! Aunque hay mucho alboroto por el peor de los casos, una pequeña mejora en la elección del pivote, que no sea obtener el primer o el último elemento de la matriz, puede evitarlo. Si obtiene un pivote del elemento intermedio entre el primer, último y medio elemento, es suficiente para evitar el peor de los casos.

Lo que es superior en Quicksort no es el peor de los casos, ¡sino el mejor de los casos! En el mejor de los casos, haces la misma cantidad de comparaciones, está bien, pero no cambias casi nada. En el caso medio, intercambia parte de los elementos, pero no todos, como en Heapsort y Mergesort. Eso es lo que le da a Quicksort el mejor momento. Menos intercambio, más velocidad.

La siguiente implementación en C # en mi computadora, que se ejecuta en modo de liberación, supera a Array. Ordena 3 segundos con pivote medio y 2 segundos con pivote mejorado (sí, hay una sobrecarga para obtener 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, tener rápido frente a un poco más rápido es irrelevante ... simplemente nunca querrás que ocasionalmente se vuelva demasiado lento. Aunque puede modificar QuickSort para evitar situaciones lentas, pierde la elegancia del QuickSort básico. Entonces, para la mayoría de las cosas, prefiero HeapSort ... puedes implementarlo con toda su elegancia simple y nunca obtener un tipo lento.

Para situaciones en las que SÍ desea la máxima velocidad en la mayoría de los casos, es posible que se prefiera QuickSort sobre HeapSort, pero ninguna de las dos 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 mis códigos de velocidad crítica, es muy común que los datos ya estén ordenados o casi ordenados (está indexando múltiples campos relacionados que a menudo se mueven hacia arriba y hacia abajo juntos O se mueven hacia arriba y hacia abajo uno frente al otro, así que una vez que ordena por uno, los otros se ordenan o se ordenan al revés o se cierran ... cualquiera de los cuales puede matar a QuickSort). Para ese caso, no implementé ninguno ... en su lugar, implementé SmoothSort de Dijkstra ... una variante de HeapSort que es O (N) cuando ya está ordenada o casi ordenada ... no es tan elegante, no es demasiado fácil de entender, pero rápido ... leerhttp://www.cs.utexas.edu/users/EWD/ewd07xx/EWD796a.PDF si quieres algo un poco más difícil de codificar.

Los híbridos en lugar Quicksort-Heapsort también son realmente interesantes, ya que la mayoría de ellos solo necesita comparaciones n * log n en el peor de los casos (son óptimos con respecto al primer término de los asintóticos, por lo que evitan los peores escenarios de Quicksort), O (log n) extra-espacio y conservan al menos "la mitad" del buen comportamiento de Quicksort con respecto al conjunto de datos ya ordenados. Dikert y Weiss presentan un algoritmo extremadamente interesante en http://arxiv.org/pdf/1209.4214v1.pdf :

• Seleccione un pivote p como la mediana de una muestra aleatoria de elementos sqrt (n) (esto se puede hacer en un máximo de 24 comparaciones sqrt (n) mediante el algoritmo de Tarjan & co, o 5 comparaciones sqrt (n) a través de la araña mucho más complicada -algoritmo de fábrica de Schonhage);
• Divida su matriz en dos partes como en el primer paso de Quicksort;
• Apila la parte más pequeña y usa O (log n) bits extra para codificar un montón en el que cada hijo izquierdo tiene un valor mayor que su hermano;
• Extraiga recursivamente la raíz del montón, tamice la laguna dejada por la raíz hasta que llegue a una hoja del montón, luego llene la laguna con un elemento apropiado tomado de la otra parte de la matriz;
• Se repite sobre la parte restante no ordenada de la matriz (si se elige p como la mediana exacta, no hay recursividad en absoluto).

Comp. entre quick sorty merge sortdado que ambos son un tipo de clasificación en el lugar, hay una diferencia entre el tiempo de ejecución del caso wrost del tiempo de ejecución del caso wrost para la clasificación rápida es O(n^2)y para la clasificación del montón sigue siendoO(n*log(n)) y para una cantidad promedio de datos la clasificación rápida será más útil. Dado que es un algoritmo aleatorio, la probabilidad de obtener respuestas correctas. en menos tiempo dependerá de la posición del elemento pivote que elija.

Entonces un

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

Una mala llamada: uno de L y G tiene un tamaño superior a 3s / 4

para una pequeña cantidad, podemos optar por la ordenación por inserción y para una gran cantidad de datos, por la ordenación por montón.

Heapsort tiene la ventaja de tener el peor caso de ejecución de O (n * log (n)), por lo que en los casos en los que es probable que quicksort tenga un rendimiento deficiente (en general, conjuntos de datos ordenados), se prefiere mucho el heapsort.

Bueno, si va al nivel de arquitectura ... usamos la estructura de datos de la cola en la memoria caché. De modo que lo que esté disponible en la cola se ordenará. Como en la clasificación rápida, no tenemos problemas para dividir la matriz en cualquier longitud ... pero en el montón ordenar (mediante el uso de una matriz) puede suceder que el padre no esté presente en la submatriz disponible en la caché y luego tenga que traerla a la memoria caché ... lo cual lleva mucho tiempo. ¡¡Esa clasificación rápida es la mejor !! 😀

Heapsort crea un montón y luego extrae repetidamente el elemento máximo. Su peor caso es O (n log n).

Pero si ve el peor caso de clasificación rápida , que es O (n2), se daría cuenta de que la clasificación rápida sería una opción no tan buena para datos grandes.

Así que esto hace que la clasificación sea algo interesante; Creo que la razón por la que existen tantos algoritmos de clasificación en la actualidad es porque todos ellos son 'mejores' en sus mejores lugares. Por ejemplo, la clasificación de burbujas puede superar la clasificación rápida si los datos están clasificados. O si sabemos algo sobre los elementos que se van a clasificar, probablemente podamos hacerlo mejor.

Es posible que esto no responda a su pregunta directamente, pensé en agregar mis dos centavos.

Heap Sort es una apuesta segura cuando se trata de entradas muy grandes. El análisis asintótico revela el orden de crecimiento de Heapsort en el peor de los casos Big-O(n logn), que es mejor que el de Quicksort en el Big-O(n^2)peor de los casos. Sin embargo, Heapsort es algo más lento en la práctica en la mayoría de las máquinas que una ordenación rápida bien implementada. Heapsort tampoco es un algoritmo de clasificación estable.

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

Para mí, hay una diferencia fundamental entre heapsort y quicksort: este último usa una recursividad. En los algoritmos recursivos, el montón crece con el número de recursiones. Esto no importa si n es pequeño, pero ahora mismo estoy ordenando dos matrices con n = 10 ^ 9 !!. El programa toma casi 10 GB de RAM y cualquier memoria adicional hará que mi computadora comience a cambiar a la memoria del disco virtual. Mi disco es un disco RAM, pero cambiarlo hace una gran diferencia en la velocidad . Entonces, en un paquete de estadísticas codificado en C ++ que incluye matrices de dimensiones ajustables, con un tamaño desconocido de antemano para el programador, y un tipo de ordenación estadística no paramétrica, prefiero el heapsort para evitar retrasos en los usos con matrices de datos muy grandes.

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

Acabo de comparar implementaciones de selección, rápida, fusión y ordenación por montones para ver cómo se comparan entre sí. La respuesta es que todos tienen sus desventajas.

TL; DR: Rápido es el mejor tipo de uso general (razonablemente rápido, estable y en su mayoría en el lugar). Personalmente, prefiero el tipo de pila a menos que necesite un tipo estable.

Selección - N ^ 2 - Realmente solo es bueno para menos de 20 elementos aproximadamente, entonces tiene un rendimiento superior. A menos que sus datos ya estén ordenados, o muy, muy cerca. N ^ 2 se vuelve muy lento muy rápido.

Rápido, en mi experiencia, no es realmente tan rápida todo el tiempo. Sin embargo, las ventajas de utilizar la clasificación rápida como clasificación general son que es razonablemente rápida y estable. También es un algoritmo in situ, pero como generalmente se implementa de forma recursiva, ocupará espacio adicional en la pila. También cae en algún lugar entre O (n log n) y O (n ^ 2). El tiempo en algunos tipos parece confirmar esto, especialmente cuando los valores caen dentro de un rango estrecho. Es mucho más rápido que el ordenamiento por selección en 10,000,000 elementos, pero más lento que fusionar o agrupar.

La ordenación por fusión está garantizada O (n log n) ya que su ordenación no depende de los datos. Simplemente hace lo que hace, independientemente de los valores que le haya dado. También es estable, pero los tipos muy grandes pueden arruinar tu pila si no tienes cuidado con la implementación. Hay algunas implementaciones complejas de ordenación por combinación en el lugar, pero generalmente necesita otra matriz en cada nivel para combinar sus valores. Si esas matrices viven en la pila, puede tener problemas.

La clasificación de montón es máxima O (n log n), pero en muchos casos es más rápida, dependiendo de qué tan lejos tenga que mover sus valores hacia arriba en el montón de log n deep. El montón se puede implementar fácilmente en el lugar en la matriz original, por lo que no necesita memoria adicional y es iterativo, por lo que no se preocupe por el desbordamiento de la pila mientras se recupera. La gran desventaja de la clasificación en montón es que no es una clasificación estable, lo que significa que está bien si la necesita.