algorithm - heapify - heapsort python

Superioridad de Quicksort sobre Heap Sort

Question

Heap Sort tiene una peor complejidad de caso de O(nlogn) mientras que Quicksort tiene O(n^2) . Pero las evidencias empericales dicen que el quicksort es superior. ¿Porqué es eso?

Answer 1

Aquí hay un par de explicaciones:

http://www.cs.auckland.ac.nz/software/AlgAnim/qsort3.html

http://users.aims.ac.za/~mackay/sorting/sorting.html

Básicamente, aunque el peor caso para el ordenamiento rápido es O (n ^ 2), en promedio tendrá un mejor rendimiento. :-)

Answer 2

Heapsort es O (N log N) garantizado, 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 lo necesita Mergesort. Entonces, ¿por qué las aplicaciones comerciales se quedan con Quicksort? ¿Qué Quicksort tiene que es tan especial sobre otras implementaciones?

He probado los algoritmos yo mismo y he visto que Quicksort tiene algo especial. Funciona rápido, mucho más rápido que los algoritmos Heap and Merge.

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

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

Con Mergesort, es incluso 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 intercambias lo que ya está ordenado. Si sus datos están completamente ordenados, ¡no intercambia casi nada! Aunque hay mucho alboroto sobre el peor de los casos, una pequeña mejora en la elección del pivote, cualquiera que no sea obtener el primer elemento o el último elemento del conjunto, puede evitarlo. Si obtienes un pivote del elemento intermedio entre el primer elemento, el último y el medio, 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! En el mejor de los casos, haga el mismo número de comparaciones, vale, pero no intercambia casi nada. En el caso promedio, intercambiamos 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 implementación a continuación en C # en mi computadora, ejecutándose en modo de lanzamiento, supera a Array.Sort por 3 segundos con pivote medio y por 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);
}

Answer 3

La complejidad del caso medio y el hecho de que puede tomar medidas simples para minimizar el riesgo de la complejidad del peor caso en Quicksort (por ejemplo, seleccione el pivote como una mediana de tres elementos en lugar de una sola posición seleccionada).

Answer 4

La notación de O grande significa que el tiempo requerido para ordenar n elementos está limitado anteriormente por la función c*n*log(n) , donde c es un factor constante no especificado. No hay ninguna razón por la cual la constante c sea ​​la misma para quicksort y heapsort . Entonces la verdadera pregunta es: ¿por qué esperas que sean igualmente rápidos?

Quicksort siempre ha sido algo más rápido que heapsort en la práctica, pero la diferencia se ha agrandado recientemente ya que, como se mencionó anteriormente, la ubicación del acceso a la memoria se ha vuelto tan importante para la velocidad de ejecución.

Answer 5

Uno de los principales factores es que quicksort tiene una mejor ubicación de referencia ; lo siguiente que se accede normalmente está cerca de lo que acaba de ver. Por el contrario, heapsort salta significativamente más. Dado que las cosas que están muy juntas probablemente se almacenarán en caché, la oferta rápida tiende a ser más rápida.

Sin embargo, el peor rendimiento del quicksort es significativamente peor que el del heapsort. Debido a que algunas aplicaciones críticas requerirán garantías de rendimiento de velocidad, heapsort es el camino correcto para estos casos.