|
|
Quicksort è l’algoritmo di ordinamento proposto da Hoare nel 1962. Come mergesort, anche quicksort è basato sulla tecnica di “Divide et Impera”, ma differisce da come vengono combinati i risultati. La strategia consiste nel selezionare un elemento del vettore, detto perno, attorno al quale riarrangiare gli altri elementi. Gli elementi più piccoli [grandi] del perno sono spostati in posizioni precedenti [successive] a quella del perno. Vediamo una possibile implementazione in linguaggio C.
La procedura perno deve scegliere un elemento x in posizione j per poi permutare gli elementi affinché risulti che:
A[ i ] <= x per i<j
A[ i ] >= x per i>j
Supponendo che il perno scelga sempre l’elemento in prima posizione avremo:
Vediamo come realizzare questa funzione:
L’ esecuzione della funzione “perno” può essere schematizzata nella seguente tabella:
Per esempio analizziamo la prima riga, il perno x è assegnato a 9 ed il primo valore minore di 9 è 8 in posizione i=3 ( j =1). Viene assegnato temp = 12, mentre A[2] = 8 e poi infine A[3] = 12. Dopodiché viene incrementato i e viene cercato un nuovo valore minore di 9, quando viene trovato viene ripetuto lo stesso meccanismo. Usciti dal ciclo for viene spostato il perno in posizione j. Proseguendo viene richiamata ricorsivamente la funzione “Quicksort” sulle due porzioni ottenute, ordinando cosi una chiamata dopo l’altra l’ intero vettore A. Per valutare la complessità della funzione “Quicksort”, considerando che T(n) della funzione “perno” è uguale a n-1 (viene confrontato un elemento con tutti gli altri) e che le due porzioni di A sulle quali avviene la chiamata ricorsiva hanno j-1 e n-j elementi, si ottiene:
Nel caso pessimo A[first] è sempre elemento più piccolo, e quindi la porzione A con elementi minori di x è vuota, mentre quella con elementi maggiori o uguali ne contiene n-1. Pertanto T(n) = T(n-1) + n-1= T(n-1) + cn. Applicando il teorema di ricorrenze lineare di ordine costante otteniamo:
Il nome dell’algoritmo non è però immeritato, poiché la sua velocità è elevata non nel caso pessimo, ma in quello medio O( n log n ).
Tutto quanto riportato in questa pagina è a puro scopo informativo personale. Se non ti trovi in accordo con quanto riportato nella pagina, vuoi fare delle precisazioni, vuoi fare delle aggiunte o hai delle proposte e dei consigli da dare, puoi farlo mandando un email. Ogni indicazione è fondamentale per la continua crescita del sito.