Un fatto importante che dovresti sapere è che in una serie di elementi distinti, quicksort con una scelta casuale di partizione verrà eseguito in O (n lg n). Ci sono molte buone prove di questo, e the one on Wikipedia ha in realtà una discussione abbastanza buona di questo. Se sei disposto a cercare una prova leggermente meno formale che sia per lo più matematicamente valida, l'intuizione è la seguente. Ogni volta che selezioniamo un pivot, diciamo che un "buon" pivot è un pivot che ci dà almeno una divisione del 75%/25%; cioè, è maggiore di almeno il 25% degli elementi e al massimo il 75% degli elementi. Vogliamo limitare il numero di volte in cui possiamo ottenere un pivot di questo tipo prima che l'algoritmo termini. Supponiamo di ottenere k split di questo tipo e di considerare la dimensione del sottoproblema più grande generato in questo modo. Ha dimensioni al massimo (3/4) k n, poiché su ogni iterazione ci stiamo liberando di almeno un quarto degli elementi. Se consideriamo il caso specifico in cui k = log 3/4 (1/n) = registro 4/3 n, allora la dimensione del sottoproblema più grande dopo che sono stati scelti k pivots saranno 1 e la ricorsione sarà Stop. Ciò significa che se scegliamo i pivots di O (lg n), la ricorsione terminerà. Ma su ogni iterazione, qual è la possibilità di ottenere un tale perno? Bene, se prendiamo il perno casualmente, allora c'è il 50% di probabilità che sia al centro del 50% degli elementi, e così in previsione sceglieremo due pivot casuali prima di ottenere un buon pivot. Ogni passo della scelta di un pivot richiede O (n) tempo, e quindi dovremmo impiegare circa O (n) tempo prima di ottenere ogni pivot. Poiché otteniamo al massimo O (lg n) buoni pivot, il tempo di esecuzione complessivo è O (n lg n) in attesa.
Un dettaglio importante nella discussione di cui sopra è che se si sostituisce il/25% diviso 75% con qualsiasi costante della divisione - per esempio, una (100 - k%)/k% split - l'analisi sopra asintotica è lo stesso. Otterrai che il quicksort richiede, in media, il tempo O (n lg n).
Il motivo per cui ho menzionato questa dimostrazione è che ti offre una buona struttura per pensare a come scegliere un pivot in quicksort. Se puoi scegliere un pivot che è abbastanza vicino al centro su ogni iteartion, puoi garantire il runtime O (n lg n).Se non si può garantire che si otterrà un buon pivot su qualsiasi iterazione, ma si può dire che in previsione ci vuole solo un numero costante di iterazioni prima di ottenere un buon pivot, allora si può anche garantire O (n lg n) runtime previsto.
Detto questo, diamo un'occhiata ai tuoi schemi di pivot proposti. Per (a), se l'array è casuale, selezionare il primo elemento come pivot equivale essenzialmente a selezionare un pivot casuale ad ogni passaggio, quindi dall'analisi sopra riportata si otterrà il runtime O (n lg n) in base alle aspettative . Per (b), se si sa che l'array è in gran parte ordinato, quindi scegliere la mediana è una buona strategia. Il motivo è che se possiamo dire che ogni elemento è "abbastanza vicino" al punto in cui dovrebbe essere nella sequenza ordinata, allora puoi fare una discussione che ogni pivot che scegli sia un buon pivot, dandoti la O (n lg n) tempo di esecuzione desiderato. (Il termine "abbastanza vicino" non è matematicamente preciso, ma penso che potresti formalizzare questo senza troppe difficoltà se lo volessi).
Per quanto riguarda (c) e (d), dei due, (d) è l'unico garantito per ottenere O (n lg n) in attesa. Se deterministicamente si selezionano determinati elementi da utilizzare come pivot, l'algoritmo sarà vulnerabile a sequenze deterministiche che possono degenerare in O (n) comportamento. C'è in realtà un articolo davvero interessante su questo chiamato "A Killer Adversary for Quicksort" di McIlroy che descrive come puoi prendere qualsiasi quicksort deterministico e costruire un input patologicamente peggiore usando una funzione di confronto malevolo. Quasi sicuramente vorrai evitarlo in qualsiasi implementazione di Quicksort, poiché altrimenti gli utenti malintenzionati potrebbero lanciare attacchi DoS sul tuo codice alimentando queste sequenze killer per forzare il tuo programma a ordinare in tempo quadratico e quindi bloccarsi. D'altra parte, poiché (d) sta selezionando i suoi punti campione casualmente, non è vulnerabile a questo attacco, perché in qualsiasi sequenza la scelta dei pivot è casuale.
È interessante notare che per (d), mentre non fa male scegliere tre elementi casuali e prendere la mediana, non è necessario farlo. La prova precedente è sufficiente per dimostrare che otterrai O (n lg n) in attesa con una singola scelta di pivot casuale. In realtà non so se scegliere la mediana di tre valori casuali migliorerà le prestazioni dell'algoritmo quicksort, sebbene dal quicksort sia sempre Ω (n lg n) non sarà certamente asintoticamente meglio che semplicemente selezionare elementi casuali come perni.
Spero che questo aiuti un po '. Adoro l'algoritmo di quicksort e tutte le decisioni di progettazione necessarie per realizzare una buona implementazione rapida. :-)
Non capisco la domanda. –
D: Per le possibili strategie ho scelto (a-d) come influenzeranno il comportamento generale dell'algoritmo quicksort? –