Quicksort superiorità rispetto Heap Sort

Question

Heap ha Ordina un caso peggiore complessità O(nlogn) mentre Quicksort ha O(n^2). Ma evidenze empirica dicono quicksort è superiore. Perché?

Answer 1

Uno dei principali fattori è che Quicksort ha una migliore località di riferimento - la prossima cosa da accedere è di solito vicino in memoria per la cosa che hai appena guardato. Al contrario, heapsort salta intorno significativamente più. Dal momento che le cose che sono vicine tra loro probabilmente saranno memorizzate nella cache insieme, quicksort tende ad essere più veloce.

Tuttavia, caso peggiore di quicksort performance è significativamente peggiore rispetto heapsort di è. Perché alcune applicazioni critiche richiedono garanzie di prestazioni di velocità, heapsort è la strada giusta da percorrere per questi casi.

Answer 2

Heapsort è O (N log N) guaranted, ciò che è molto meglio di caso peggiore in Quicksort. Heapsort non hanno bisogno di più memoria per un'altra matrice per mettere dati ordinati nella misura necessaria per Mergesort. Allora perché le applicazioni comercial bastone con Quicksort? Cosa Quicksort ha che è così speciale rispetto alle altre implementazioni?

Ho testato gli algoritmi me stesso e ho visto che Quicksort ha qualcosa di speciale. Corre algoritmi veloci, molto più veloce di Heap e unire.

Il segreto del Quicksort è: E 'quasi non fa inutili swap elemento. Swap è in termini di tempo.

Con Heapsort, anche se tutti i dati è già ordinato, che si sta per scambiare il 100% degli elementi per ordinare l'array.

Con Mergesort, è ancora peggio. Si sta per scrivere il 100% di elementi in un altro array e scrivere di nuovo in quella originale, anche se i dati sono già ordinati.

Con Quicksort non scambiare ciò che è già ordinato. Se i dati sono completamente ordinato, si scambia quasi nulla! Anche se c'è un sacco di irritabili caso circa peggiore, un piccolo miglioramento sulla scelta del perno, una diversa da ottenere il primo o l'ultimo elemento della matrice, può evitare. Se si ottiene un perno dall'elemento intermedio tra primo, ultimo e centrale elemento, è suficient evitare peggiore dei casi.

Ciò che è superiore a Quicksort non è il caso peggiore, ma il migliore dei casi! Nel migliore dei casi si fa lo stesso numero di confronti, ok, ma si scambia quasi nulla. Nel caso in cui media si scambia parte degli elementi, ma non tutti gli elementi, come in Heapsort e Mergesort. Questo è ciò che dà Quicksort il miglior tempo. Meno di swap, più velocità.

L'implementazione di seguito in C # sul mio computer, in esecuzione su modalità di rilascio, batte Array.Sort da 3 secondi con perno centrale e di 2 secondi con una migliore articolazione (sì, c'è un overhead per ottenere un buon pivot).

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

Ecco un paio spiegazioni:

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

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

Essenzialmente, anche se il caso peggiore per quick sort è O (n ^ 2) sul media eseguirà meglio. : -)

Answer 4

La notazione O-grande significa che il tempo necessario per ordinare n elementi è limitato superiormente dalla funzione c*n*log(n), dove c qualche fattore costante non specificato. Non v'è alcun motivo per cui il c costante dovrebbe essere lo stesso per quicksort e heapsort. Quindi la vera domanda è: perché ci si aspetta che siano altrettanto veloce

Quicksort è stato sempre più veloci di quelle heapsort in pratica, ma la differenza è diventata più grande dal recente, come accennato prima, frazione di accesso alla memoria è diventato così importante per la velocità di esecuzione.

Answer 5

media complessità nel caso, e il fatto che si possono adottare misure semplici per minimizzare il rischio di caso peggiore complessità Quicksort (es seleziona il perno come una mediana di tre elementi, piuttosto che una singola posizione selezionata).