Perché quicksort è migliore di altri algoritmi di ordinamento in pratica?

Non sono d'accordo sul fatto che quicksort sia migliore di altri algoritmi di ordinamento in pratica.

Per la maggior parte degli scopi, Timsort - l'ibrido tra mergesort / insertion sort che sfrutta il fatto che i dati ordinati spesso inizia quasi in ordine o in ordine alfabetico.

Il quicksort più semplice (nessun pivot casuale) tratta questo caso potenzialmente comune come O (N ^ 2) (riducendo a O (N lg N) con pivot casuali), mentre TimSort può gestire questi casi in O (N).

Secondo questi benchmark in C # confrontando quicksort integrato a TimSort, Timsort è significativamente più veloce nei casi per lo più ordinati e leggermente più veloce nel caso di dati casuali e TimSort migliora se la funzione di confronto è particolarmente lenta. Non ho ripetuto questi benchmark e non sarei sorpreso se quicksort battesse leggermente TimSort per una combinazione di dati casuali o se ci fosse qualcosa di strano nell'ordinamento incorporato di C # (basato su quicksort) che lo sta rallentando. Tuttavia, TimSort ha vantaggi distinti quando i dati possono essere parzialmente ordinati, ed è approssimativamente uguale a quicksort in termini di velocità quando i dati non sono ordinati in modo parziale.

TimSort ha anche un ulteriore vantaggio di essere un ordinamento stabile, a differenza di quicksort. L'unico svantaggio di TimSort utilizza la memoria O (N) rispetto a O (lg N) nell'usuale (veloce) implementazione.

L'ordinamento rapido è considerato più veloce perché il coefficiente è inferiore a qualsiasi altro algoritmo noto. Non c'è alcuna ragione o prova per questo, solo nessun algoritmo con un coefficiente più piccolo è stato trovato. È vero che altri algoritmi hanno anche il tempo O ( n log n ), ma nel mondo reale anche il coefficiente è importante.

Si noti che per l'ordinamento di inserimento di piccoli dati (quello che è considerato O ( n ² )) è più veloce a causa della natura delle funzioni matematiche. Questo dipende dai coefficienti specifici che variano da macchina a macchina. (Alla fine, solo il montaggio è davvero in esecuzione.) Quindi a volte un ibrido di ordinamento rapido e ordinamento di inserimenti è il più veloce in pratica, credo.

Quicksort non sovraperforma su tutti gli altri algoritmi di ordinamento. Ad esempio, l'ordinamento heap bottom-up ( Wegener 2002 ) offre prestazioni migliori rispetto a quicksort per quantità ragionevoli di dati ed è anche un algoritmo sul posto. È anche facile da implementare (almeno, non più difficile di una variante quicksort ottimizzata).

Non è così noto e non lo trovi in molti libri di testo, questo potrebbe spiegare perché non è così popolare come quicksort.

Non dovresti centrare solo sul caso peggiore e solo sulla complessità temporale. È più circa la media del peggiore, e riguarda lo spazio e del tempo.

Quicksort:

• ha una media complessità temporale di Θ ( n log n );
• può essere implementato con la complessità dello spazio di Θ (log n );

Avere anche in considerazione che la grande notazione O non prende in considerazione alcuna costanza, ma in pratica fa la differenza se l'algoritmo è poche volte più veloce. Θ ( n log n ) significa che l'algoritmo viene eseguito in K n log ( n ), dove K è costante. Quicksort è l'algoritmo di confronto-ordinamento con il più basso K .

Quicksort è spesso una buona scelta in quanto è ragionevolmente veloce e ragionevolmente veloce e facile da implementare.

Se sei seriamente in grado di ordinare grandi quantità di dati molto rapidamente, probabilmente stai meglio con qualche variazione su MergeSort. Questo può essere fatto per sfruttare la memoria esterna, può fare uso di più thread o processi, ma non sono banali da codificare.

Le prestazioni effettive degli algoritmi dipendono dalla piattaforma, dal linguaggio, dal compilatore, dall'attenzione del programmatore per i dettagli di implementazione, dallo sforzo di ottimizzazione specifico eccetera. Quindi, il "vantaggio del fattore costante" di quicksort non è molto ben definito - è un giudizio soggettivo basato su strumenti attualmente disponibili e una stima approssimativa di "equivalenti sforzi di implementazione" da parte di chiunque faccia effettivamente lo studio comparativo delle prestazioni. .

Detto questo, ritengo che quicksort funzioni bene (per input casuali) perché è semplice e perché la sua struttura ricorsiva è relativamente cache-friendly. D'altra parte, poiché il suo caso peggiore è facile da attivare, qualsiasi utilizzo pratico di un quicksort dovrà essere più complesso di quanto la descrizione del suo libro di testo indichi: quindi, versioni modificate come l'introsort.

Nel tempo, mentre la piattaforma dominante cambia, diversi algoritmi possono guadagnare o perdere il vantaggio relativo (non ben definito). La saggezza convenzionale sulle prestazioni relative potrebbe essere in ritardo rispetto a questo cambiamento, quindi se non sei veramente sicuro di quale algoritmo sia il migliore per la tua applicazione, dovresti implementarle entrambe e testarle.