Quicksort vs heapsort

Question

Sia quicksort e heapsort fanno ordinamento sul posto. Che è migliore? Quali sono le applicazioni e casi in cui o è preferito?

Answer 1

Questo documento ha alcune analisi.

Inoltre, da Wikipedia:

  

Il più diretto concorrente di   quicksort è heapsort. heapsort è   tipicamente un po 'più lento di   Quicksort, ma il caso peggiore in esecuzione   il tempo è sempre Θ (nlogn). quicksort è   solitamente più veloce, anche se ci resti   la possibilità di performance peggiore caso   tranne nella variante introsort, che   interruttori per Heapsort quando un brutto caso   viene rilevato. Se è noto in anticipo   che heapsort sta per essere   necessario, usando direttamente sarà   più veloce di attesa per introsort a   passare ad esso.

Answer 2

Heapsort è O (N log N) guaranted, ciò che è molto meglio di caso peggiore in Quicksort. Heapsort non ha 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

Per la maggior parte delle situazioni, avendo rapido rispetto a un po 'più veloce è irrilevante ... semplicemente non lo vogliono ottenere di tanto in tanto waayyy lento. Anche se è possibile modificare QuickSort per evitare le situazioni di lenti modo, si perde l'eleganza del QuickSort base. Così, per la maggior parte delle cose, io in realtà preferisco heapsort ... è possibile implementare nella sua piena semplice eleganza, senza mai ottenere una sorta lento.

Per le situazioni in cui si vuole la velocità massima nella maggior parte dei casi, QuickSort può essere preferito su heapsort, ma nessuno dei due può essere la risposta giusta. Per le situazioni di velocità-critica, vale la pena di esaminare da vicino i dettagli della situazione. Ad esempio, in alcuni dei miei codice velocità critica, è molto comune che i dati sono già ordinati o quasi allineati (si indicizzando correlati più campi che spesso o si muovono su e giù insieme o si muovono su e giù di fronte all'altro, così una volta che si ordina per uno, gli altri sono o ordinati o indietro-ordinato o chiuso ... ciascuno dei quali può uccidere QuickSort). Per questo caso, ho implementato né ... invece, ho implementato di Dijkstra smoothsort ... una variante heapsort che è O (N), quando già allineati o quasi ordinato ... non è così elegante, non troppo facile da capire, ma veloce ... leggi http://www.cs.utexas.edu /users/EWD/ewd07xx/EWD796a.PDF se volete qualcosa di un po 'più impegnativo per il codice.

Answer 4

Quicksort-heapsort ibridi in-place sono davvero interessanti, troppo, dal momento che la maggior parte di loro ha bisogno solo n * log n confronti nel caso peggiore (sono ottimale rispetto al primo termine delle asintotica, in modo da evitare il peggio scenari CAUSA di Quicksort), O (log n) extra-spazio e conservano insieme almeno "metà" del buon comportamento di quicksort rispetto al già ordinato dei dati. Un algoritmo estremamente interessante è presentato da Dikert e Weiss in http://arxiv.org/pdf/1209.4214v1. pdf :

• Seleziona un perno p come la mediana di un campione casuale di sqrt (n) elementi (questo può essere fatto al massimo in 24 sqrt n confronti () attraverso l'algoritmo di Tarjan & co, o 5 sqrt (n) confronti attraverso la tanto algoritmo più contorto Spider-fabbrica di Schonhage);
• partizionare l'array in due parti come nel primo passo di Quicksort;
• heapify la più piccola parte e l'uso O (log n) bit extra per codificare un mucchio, in cui ogni bambino sinistra ha un valore maggiore rispetto al suo fratello;
• ricorsivamente estrarre la radice del mucchio, vagliare per lacune lasciato dalla radice fino a raggiungere una foglia del mucchio, quindi riempire la lacune con un elemento appropriato prese dall'altra parte della matrice;
• Ricorre sul resto non ordinato dell'array (se p è scelto come mediana esatta, non c'è ricorsione affatto).

Answer 5

Comp. tra quick sort e merge sort poiché entrambi sono tipo di posto smistamento v'è una differenza tra caso wrost tempo del caso wrost tempo di esecuzione per l'ordinamento pratica esecuzione è O(n^2) e mucchio ordinamento è ancora O(n*log(n)) e per una quantità media di dati veloce sorta sarà essere più utile. Dal momento che è un algoritmo randomizzato così la probabilità di ottenere ans corrette. in meno tempo dipende dalla posizione dell'elemento di rotazione che si sceglie.

a

Buono chiamata: le dimensioni di L e G sono ogni meno di 3s / 4

Bad chiamata: una delle L e G ha dimensione maggiore di 3s / 4

per la piccola quantità possiamo andare per insertion sort e per molto grandi quantità di dati vanno per heap sorta.

Answer 6

Beh, se si va a livello di architettura ... usiamo struttura dati della coda nella cache memory.so che cosa mai è disponibile in coda avranno sorted.As in quick sort non abbiamo alcun problema che divide l'array in qualsiasi lunghezza ... ma in una sorta mucchio (utilizzando array) può così accadere che il genitore non può essere presente nella matrice sub disponibile nella cache e poi deve portarlo nella memoria cache ... che richiede molto tempo. Ecco quicksort è meglio !!

Answer 7

Heapsort costruisce un mucchio e poi estrae più volte la voce di massima. Il suo caso peggiore è O (n log n).

Ma se si vedrebbe il peggior caso di rapido sorta , che è O (n2 ), si sarebbe reso conto che la rapida tipo sarebbe un non-così-buona scelta per i dati di grandi dimensioni.

Quindi questo rende ordinamento è una cosa interessante; Credo che la ragione per cui così tanti algoritmi di ordinamento vivono oggi è perché tutti sono 'migliori' ai loro posti migliori. Per esempio, bubble sort può eseguire fuori quick sort se i dati sono ordinati. Oppure, se sappiamo qualcosa circa gli elementi da ordinare allora probabilmente possiamo fare di meglio.

Questo non può rispondere alla tua domanda direttamente, ho pensato di aggiungere i miei due centesimi.

Answer 8

Heapsort ha il vantaggio di avere un peggiore funzionamento di O (n * log (n)) in modo nei casi in cui il Quicksort è probabile che sia uno scarso rendimento (i dati per lo più ordinato imposta in genere) heapsort è di gran lunga preferito.

Answer 9

Heap Sort è una scommessa sicura quando si tratta di grandi ingressi. analisi asintotica rivela ordine di crescita Heapsort nel caso peggiore è Big-O(n logn), che è meglio che Big-O(n^2) di Quicksort come caso peggiore. Tuttavia, Heapsort è più lenta in pratica sulla maggior parte delle macchine di una sorta pratica ben implementata. Heapsort inoltre, non è un algoritmo di ordinamento stabile.

Il motivo heapsort è più lento in pratica che quicksort è dovuto al meglio frazione di riferimento ( " https: / /en.wikipedia.org/wiki/Locality_of_reference ") in quicksort, dove elementi di dati distanza relativamente stretti posizioni di memoria. I sistemi che presentano forti località di riferimento sono ottimi candidati per l'ottimizzazione delle prestazioni. Mucchio sorta, tuttavia, si occupa di salti più grandi. Questo rende Quicksort più favorevole per gli ingressi più piccoli.

Answer 10

Per me c'è una differenza fondamentale tra molto Heapsort e il Quicksort: quest'ultimo utilizza una ricorsione. Negli algoritmi ricorsivi mucchio cresce con il numero di ricorsioni. Questo non importa se n è piccolo, ma in questo momento sto di ordinamento due matrici con n = 10 ^ 9 !!. Il programma prende quasi 10 GB di RAM e qualsiasi memoria aggiuntiva renderà il mio computer per avviare lo scambio di memoria del disco virtuale. Il mio disco è un disco RAM, ma ancora scambiando ad esso fare un grande differenza in termini di velocità . Quindi, in uno statpack scritto in C ++ che include matrici dimensione regolabili, con dimensioni sconosciute in anticipo al programmatore, e il tipo statistico non parametrico di smistamento preferisco il heapsort per evitare ritardi a usi con molto grandi matrici di dati.

Answer 11

Per rispondere alla domanda originale e affrontare alcune delle altre commenti qui:

Ho appena confrontato implementazioni di selezione, rapida, unire, e heap sorta per vedere come avevano stack contro l'altro. La risposta è che tutti hanno i loro lati negativi.

TL; DR: Breve è il miglior uso generale sort (ragionevolmente veloce, stabile, e per lo più in-place) Personalmente preferisco mucchio sorta anche se a meno che non ho bisogno di un ordinamento stabile.

Selection - N ^ 2 - E 'davvero buono solo per meno di 20 elementi, o giù di lì, allora è superato. A meno che i dati è già ordinato, o molto, molto quasi. N ^ 2 diventa veramente lento veramente veloce.

veloce, nella mia esperienza, non è in realtà che veloce per tutto il tempo. I bonus per l'utilizzo di quick sort come una sorta generale, comunque sono che è ragionevolmente veloce ed è stabile. E 'anche un algoritmo sul posto, ma, come è generalmente implementato in modo ricorsivo, ci vorranno spazio dello stack aggiuntivo. Essa rientra anche da qualche parte tra O (n log n) e O (n ^ 2). Timing su alcuni tipi sembrano confermare questo, soprattutto quando i valori rientrano in una gamma stretta. È il modo più veloce di selection sort su 10.000.000 di oggetti, ma più lento di unire o heap.

Unisci O sorta è garantita (n log n) sin dal suo ordinamento non è dipendente di dati. E 'solo fa quello che fa, indipendentemente da ciò che i valori che hai dato. E 'anche stabile, ma molto grandi tipi può spegnere il vostro stack, se non stai attento in merito all'esecuzione. Ci sono alcuni complessi sul posto merge implementazioni di ordinamento, ma in genere è necessario un altro array in ogni livello per unire i valori in. Se quei array vivono nello stack si può incorrere in problemi.

heap sort è massimo O (n log n), ma in molti casi è più veloce, a seconda di quanto è necessario spostare i valori del log n mucchio profondo. Il mucchio può essere facilmente implementato sul posto nell'array originale, quindi non ha bisogno di memoria aggiuntiva, ed è iterativo, quindi nessuna preoccupazione circa overflow di stack mentre recursing. Il enorme aspetto negativo di heap sort è che non è un ordinamento stabile, che significa che è a destra fuori se avete bisogno di questo.