Quicksort è un algoritmo di ordinamento ricorsivo in place non stabile. E come l'algoritmo di ordinamento Mergesort basa il suo funzionamento sul paradigma del "Divide et Impera"; ovvero sulla scomposizione del problema in più sottoproblemi di taglia minore.
In generale la logica dell'algoritmo può essere riassunta in questo modo:
Scelta del pivot: Seleziona un elemento dell'array chiamato pivot. Può essere scelto in vari modi (es: il primo elemento, l'ultimo, un elemento casuale, o la mediana). Partizionamento della lista: Si divide l'array in due parti: Elementi minori o uguali al pivot (solitamente a sinistra del pivot) Elementi maggiori del pivot (solitamente a destra del pivot) Alla fine di questa fase, il pivot sarà nella sua posizione corretta nella lista. Ricorsione sui sotto-array: Applicazione del Quicksort alla parte sinistra (elementi minori o uguali al pivot) e alla parte destra (elementi maggiori). Continua fino a che i sotto-array contengono un solo elemento o sono vuoti (caso base).
Il Quicksort, termine che tradotto letteralmente in italiano significa "ordinamento rapido", è l'algoritmo di ordinamento che ha, nel caso medio, prestazioni migliori tra quelli basati su confronto. È stato ideato da Charles Antony Richard Hoare nel 1961.
Storia L'algoritmo quicksort fu ideato nel 1959 da Tony Hoare durante un viaggio nell'URSS, durante una sua visita alla Moscow State University. In quel periodo, Hoare lavorava a un progetto di traduzione automatica per il National Physical Laboratory. Durante il processo di traduzione si rese necessario ordinare le parole russe prima di consultare il dizionario Russo-Inglese che era registrato su un nastro magnetico e ordinato alfabeticamente. Dopo aver capito che l'uso dell'insertion sort sarebbe stato troppo lento, concepì una nuova idea di algoritmo - il Quicksort. Scrisse il programma con Autocode relativa alla partizione ma non riuscì a gestire la parte relativa ai segmenti non ordinati. Tornato in Inghilterra, gli fu chiesto per lavoro di scrivere il codice di uno Shell sort - l'algoritmo di ordinamento più efficiente all'epoca. Hoare dichiarò al suo capo che conosceva un algoritmo più efficiente; il capo fece una scommessa, di sei pence, e perse. In seguito, Hoare venne a conoscenza del linguaggio ALGOL e della sua abilità di gestire la ricorsione; grazie ad esso, pubblicò il codice completo nella maggiore rivista scientifica di informatica del periodo, Communications of the Association for Computing Machinery.
Algoritmo di base L'idea base può esprimersi agevolmente in termini ricorsivi. Ad ogni stadio si effettua un ordinamento parziale di una sequenza di oggetti da ordinare. Assunto un elemento come perno dello stadio, si confrontano con esso gli altri elementi e si posizionano alla sua sinistra i minori e a destra i maggiori, senza tener conto del loro ordine. Dopo questo stadio si ha che il perno è nella sua posizione definitiva.
Successivamente si organizzano nuovi stadi simili nei quali si procede all'ordinamento parziale delle sottosequenze di elementi rimasti non ordinati, fino al loro esaurimento.
Lo pseudocodice per il Quicksort è:
Quicksort(array, primo, ultimo) k ← Pivot(array, primo, ultimo) Quicksort(array, primo, k-1) Quicksort(array, k+1, ultimo)
Pivot(array, primo, ultimo) x ← array[primo] k ← primo for i ← primo to ultimo do if array[i] < x then k ← k + 1 Scambia array[i] ↔ array[k] array[primo] ← array[k] array[k] ← x return k O, in alternativa: Procedure Quicksort(A) Input A, vettore a1, a2, a3 .. an begin if n ≤ 1 then return A else begin scegli un elemento pivot ak calcola il vettore A1 dagli elementi ai di A tali che i ≠ k e ai ≤ ak calcola il vettore A2 dagli elementi aj di A tali che j ≠ k e aj > ak A1 ← Quicksort(A1) A2 ← Quicksort(A2) return A1 · (ak) · A2; end
Specifica dell'algoritmo
Si vuole fornire una versione più dettagliata dell'algoritmo che specifichi la struttura dati utilizzata e il processo di partizione. L'obiettivo è quello di implementare la procedura mediante un procedimento che calcoli la sequenza ordinata attraverso scambi diretti tra i valori delle sue componenti, senza usare vettori aggiuntivi per mantenere risultati parziali della computazione. In questo modo lo spazio di memoria utilizzato è essenzialmente ridotto alle celle necessarie per mantenere il vettore di ingresso e per implementare la ricorsione.
Si rappresenta la sequenza di input mediante il vettore componenti. Per ogni coppia di interi p,q tali che denotiamo . Il cuore dell'algoritmo è costituito dalla funzione che partiziona l'insieme, per comodità chiamiamo Partition(p,q). Questa procedura ripartisce gli elementi del vettore rispetto al valore della prima componente ; questa funzione modifica quindi il valore delle componenti di e restituisce un indice che gode delle seguenti proprietà:
assume il valore contiene i valori minori o uguali ad originariamente contenuti in contiene i valori maggiori di originariamente contenuti in
Rianalizzando l'algoritmo del quicksort prima esposto si comprende che la funzione Partition(A, p, q) è il fulcro delle operazioni. Nella versione qui presentata l'elemento pivot è fissato a ; questo non è limitativo poiché il chiamante può scegliere un pivot diverso e posizionarlo in prima di chiamare la funzione. Partition quindi effettua una scansione degli elementi dalla sinistra saltando quelli più piccoli del pivot e dalla destra saltando quelli più grandi; quindi scambia gli elementi che arrestano le scansioni e ricomincia. La scansione partita da destra si ferma su elementi minori o uguali al pivot (e quindi è bloccata dall'elemento pivot stesso), mentre quella partita da sinistra si interrompe quando arriva a un elemento maggiore del pivot. I puntatori utilizzati per la scansione quindi si possono incrociare, e quando l'incrocio è avvenuto la funzione ha completato il suo lavoro.
Oltre al vettore , la funzione riceve i parametri e che rappresentano gli indici del sottovettore sul quale si opera la partizione (assumiamo sempre ). Le altre variabili che compaiono nella procedura sono locali.
Function Partition(A, p, q) begin i ← p j ← q while i ≤ j do begin while A[j] > A[p] do j ← j - 1 while i ≤ j and A[i] ≤ A[p] do i ← i + 1 if i < j then begin Scambia(A[i], A[j]) i ← i + 1 j ← j - 1 end end Scambia(A[p], A[j]) return j end
Analisi delle prestazioni Caso peggiore
Denotiamo con il massimo numero di confronti tra elementi del vettore di ingresso eseguiti dall'algoritmo su input di lunghezza . È evidente che i vettori e della partizione possono essere calcolati mediante confronti (dato che un elemento viene scelto come pivot). Inoltre la dimensione di e è data rispettivamente da e , per qualche . Questo implica che per ogni
mentre per :
Questa è l'equazione di ricorrenza per l'algoritmo in questione. Si vuole ora determinare il esatto. Nel caso pratico questo valore sarà utile per capire il comportamento dell'algoritmo nel caso in cui si sceglie l'elemento massimo o minimo per il partizionamento. Infatti poiché abbiamo che e quindi per ogni otteniamo:
In questo modo abbiamo ottenuto che l'algoritmo nel caso peggiore ha un costo quadratico. Il caso peggiore si verifica quando lo sbilanciamento è totale, cioè quando l'algoritmo di partizionamento restituisce una partizione di lunghezza n-1 e una di lunghezza 0; in questo caso il tempo di esecuzione è Θ().
Se vogliamo evitare che la scelta del partizionamento ci conduca ad un tempo quadratico, è sufficiente scegliere come pivot l'elemento mediano della sequenza, per esempio tramite l'algoritmo QuickSelect. Questo consente di trovarci sempre ad avere due sequenze di elementi, ottenendo quindi un tempo asintotico pari a nel caso peggiore. Ad un'analisi più accurata, tuttavia, si verifica che la costante moltiplicativa è circa 24 (e non 1.39, come nel caso migliore). Per accorgersene è sufficiente scegliere il pivot seguendo questi passi:
Costruire quintuple: l'ultimo sottoarray può non essere una quintupla, ma un insieme più piccolo; Per ogni quintupla calcolare il mediano, effettuando in totale, confronti, perché il mediano di 5 elementi può essere calcolato con al più 7 confronti; Ricavare un campione, ottenuto come mediano dei mediani delle quintuple; Calcolare il pivot come mediano dei mediani, impiegando un tempo pari a (chiamata ricorsiva); Partiziona intorno al pivot: confronti; Prosegui ricorsivamente: (perché la chiamata viene effettuata un insieme con cardinalità pari, al più ).
L'equazione di ricorrenza diventa:
che ha soluzione , in particolare . Esistono quindi soluzioni approssimate che in pratica evitano il caso pessimo pur non potendo garantire ciò.
Caso medio
Per lo studio nel caso medio si valuta il numero medio di confronti tra elementi del vettore di ingresso eseguiti dall'algoritmo, determinando di conseguenza l'ordine di grandezza del tempo medio di calcolo necessario per eseguire la procedura.
La complessità dell'algoritmo in questo caso è , precisamente .
Caso migliore
Il caso migliore si verifica quando l'algoritmo di partizionamento determina due sottoproblemi perfettamente bilanciati, entrambi di dimensione n/2; in questo caso il tempo di esecuzione è .
Tipi di partizionamento Esistono delle varianti del quicksort che si basano sulla differente scelta dell'elemento pivot all'interno della serie di dati da ordinare.
Non casuale (non random): in questa versione si sceglie come pivot l'elemento in ultima posizione evitando in questo modo il calcolo della scelta dei numeri casuali. Il caso pessimo è rappresentato da un vettore ordinato al contrario. Anche qualora venga scelto un altro elemento come pivot (ad es. il primo o quello di mezzo) si può trovare un caso pessimo. Metodo della mediana: Il metodo della mediana di 3 è un tipico approccio che consente di migliorare i partizionamenti dell'array, evitando partizioni troppo sbilanciate, e consiste nell'effettuare il partizionamento scegliendo opportunamente il pivot nel sottoarray: in particolare si sceglie come pivot la mediana di un insieme di tre elementi selezionati a caso dal sottoarray. Anche in questo caso tuttavia esiste un caso pessimo ed ha complessità quadratica. Casuale (random): Questa è la prima versione pubblicata del quicksort che si basa sulla scelta casuale dell'elemento pivot. Questo non permette di stabilire a tavolino quale sia il caso peggiore, che tuttavia si verificherà con probabilità .
Come già menzionato in precedenza, tutte queste versioni si ottengono aggiungendo uno scambio prima della chiamata a Partition, per esempio:
scegli a caso un intero k tra p e q Scambia (A[p], A[k]) Partition (A, p, q)
Chiavi duplicate
Se nello stesso vettore esistono degli elementi ripetuti, è possibile sistemarli nella prima scansione che viene effettuata tramite la versione di Bentley - Mc Illroy del 1993. Questa versione prevede che, durante il processo di scansione (fase di partizionamento dell'algoritmo), gli elementi uguali al pivot vengano spostati immediatamente a fianco del pivot (a sinistra se provengono dalla parte sinistra, a destra se provengono dalla parte destra). In questo modo si avranno tre partizioni, una con gli elementi minori del pivot, una con gli elementi uguali e una con gli elementi maggiori del pivot.
La complessità dell'algoritmo non viene modificata.
Dimensione dello stack