Superiorità di Quicksort rispetto a Heap Sort

Heap Sort ha una complessità nel caso peggiore di O(nlogn) mentre Quicksort ha O(n^2) . Ma le prove empiriche dicono che quicksort è superiore. Perché?

Uno dei fattori principali è che quicksort ha una migliore localizzazione di riferimento : la prossima cosa a cui si accede è solitamente vicina alla memoria alla cosa che hai appena guardato. Al contrario, heapsort salta significativamente di più. Poiché le cose che sono vicine tra loro saranno probabilmente memorizzate insieme, quicksort tende ad essere più veloce.

Tuttavia, le prestazioni nel caso peggiore di quicksort sono significativamente peggiori di quelle di heapsort. Poiché alcune applicazioni critiche richiedono garanzie di prestazioni di velocità, heapsort è la giusta soluzione per questi casi.

Heapsort è O (N log N) garantito, ciò che è molto meglio del caso peggiore in Quicksort. Heapsort non ha bisogno di più memoria per un altro array per mettere i dati ordinati come necessario da Mergesort. Quindi, perché le applicazioni commerciali si attaccano a Quicksort? Che cosa Quicksort ha è così speciale rispetto ad altre implementazioni?

Ho provato io stesso gli algoritmi e ho visto che Quicksort ha davvero qualcosa di speciale. Funziona velocemente, molto più velocemente degli algoritmi Heap e Merge.

Il segreto di Quicksort è: quasi non fa scambi di elementi non necessari. Lo swap richiede molto tempo.

Con Heapsort, anche se tutti i tuoi dati sono già ordinati, devi scambiare il 100% di elementi per ordinare l’array.

Con Mergesort, è anche peggio. Scriverete il 100% degli elementi in un altro array e lo riscrivete in quello originale, anche se i dati sono già ordinati.

Con Quicksort non si scambia ciò che è già stato ordinato. Se i tuoi dati sono completamente ordinati, non cambierai quasi nulla! Sebbene ci sia molta agitazione nel caso peggiore, un piccolo miglioramento nella scelta del pivot, a parte il fatto di ottenere il primo o l’ultimo elemento della matrice, può evitarlo. Se ottieni un pivot dall’elemento intermedio tra il primo, l’ultimo e il medio, è sufficiente per evitare il caso peggiore.

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

L’implementazione di seguito in C # sul mio computer, in esecuzione in modalità di rilascio, batte Array.Sort di 3 secondi con pivot centrale e di 2 secondi con pivot migliorato (sì, c’è un sovraccarico 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); } 

Ecco alcune spiegazioni:

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

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

In sostanza, anche se il caso peggiore per l’ordinamento rapido è O (n ^ 2), in media si comporterà meglio. 🙂

La notazione O grande indica che il tempo necessario per ordinare n elementi è delimitato in alto dalla funzione c*n*log(n) , dove c è un fattore costante non specificato. Non vi è alcun motivo per cui la costante c dovrebbe essere la stessa per quicksort e heapsort . Quindi la vera domanda è: perché ti aspetteresti che siano ugualmente veloci?

Quicksort è sempre stato un po ‘più veloce di heapsort nella pratica, ma la differenza è aumentata di recente poiché, come accennato prima, la localizzazione dell’accesso alla memoria è diventata così importante per la velocità di esecuzione.

Complessità del caso medio e il fatto che è ansible adottare semplici passaggi per minimizzare il rischio di complessità del caso peggiore in Quicksort (ad esempio, selezionare il pivot come una mediana di tre elementi anziché una singola posizione selezionata).