Quicksort - Algoritmi e strutture dati

Il meccanismo del processo di partizionamento

Tutto il meccanismo sta nella magia del processo di partizionamento, cioè scoprire qual è il posto giusto di un elemento partendo dal primo. Prendo il primo e lo metto al posto giusto, poi prendo i primi dei sub-array e li metto al posto giusto, poi prendo i primi dei sub-array di questi sub-array e li metto al posto giusto e via così. L'elemento che vado a mettere al posto giusto è sempre il primo del sub-array su cui sto lavorando.

Algoritmi e caratteristiche

È matematicamente dimostrato che questo algoritmo raggiunge lo scopo per cui è previsto, ci sono algoritmi per cui il raggiungimento dello scopo è ipotizzato ma non dimostrato. È un algoritmo divide-and-conquer ma ha un’altra caratteristica: è un esempio di un algoritmo randomizzato perché ha il primo passo iniziale di permutazione casuale degli elementi che permette di creare artificialmente degli input che non hanno strutture particolari che purtroppo sono frequenti nei casi pratici.

Ad esempio, se usiamo questo algoritmo per ordinare array parzialmente ordinati, il quicksort lavora particolarmente bene su un array completamente casuale. Se l’array è parzialmente ordinato, cioè ha una sua struttura interna, allora il quicksort potrebbe lavorare peggio, quindi la situazione migliore per il quicksort è avere un array casuale. La randomizzazione che vogliamo fare è un algoritmo che scombina le cose. Dopo aver scombinato tutto, la probabilità di ottenere anche una sola configurazione ordinata è molto bassa, ma le configurazioni che ci vanno bene sono molte di più di quelle che non ci vanno bene.

I due pezzi del quicksort

Vediamo i due pezzi del quicksort: questo codice è in Java eliminando alcune parti che servono solo al compilatore. La prima è la parte “non magica”: mediante shuffle scombiniamo il vettore, dopo di che ordiniamo il vettore da 0 ad a.length-1 chiamando la funzione sort definita sotto. Essa lavora su sub-array e contiene una serie di condizioni che ci dicono se, stringendo l’array, sono arrivato a sovrapporre hi e lo allora ho finito (hi<=lo, non dovrebbe mai succedere che hi<lo ma per sicurezza è bene metterlo), ho cioè un array di dimensione 0 e quindi si conclude.

Naturalmente, per trovare la j, chiama la funzione partition chiedendo quindi la dimensione in cui deve mettere il primo elemento nel sub-array che va da lo a hi. Quindi partition trova il punto in cui mettere questo elemento, una volta trovato il punto metto lì l’elemento e vado avanti a partizionare ricorsivamente il sub-array più basso e il sub-array più alto.

La funzione partition

Vediamo ora la funzione partition: scelgo un elemento da collocare, chiamo con v il primo elemento del sub-array da ordinare, nonché pivot. Comincio poi a leggere il sub-array in salita e andiamo a verificare se quel sub-array per caso è già fatto di elementi tutti inferiori, questo mediante la prima while dentro il while(true). Infatti, mediante la less mi chiedo se a[++i] è meno del pivot, con ++i intendiamo che incremento i -quindi parto dal secondo elemento del sub-array- poi prendo a[i] e vado a vedere se è minore di v. Il ciclo si ferma in due casi: quando incontra un elemento che non è minore, quindi un elemento che dovrebbe stare nel vettore alto ma sta nel vettore basso, oppure si ferma anche quando trovo i==hi, cioè ho finito.

Il while successivo fa il giro complementare, nell’altro sub-array, quindi parte da hi e andando in giù, si ferma quando incontra qualcosa che sta in alto ma dovrebbe stare in basso oppure quando j==lo perché è arrivato in fondo. Siccome queste due cose si muoveranno, cioè avrò i in salita e j in discesa, se per caso si scambiano mi fermo, quindi la salita che sto facendo e la discesa che sto facendo non possono scambiarsi e andare avanti. Mediante exch scambio gli elementi i e j ma a questo punto ripeto l’operazione con quel che resta, dopodiché alla fine scambio a con l’ultimo j.

La traccia dell'algoritmo

Vediamo la traccia: la prima riga è l’array scombinato, quindi dopo lo shuffle, poi segue lo scan left cioè quella che nel codice era la prima while dopo il while(true). Poi faccio lo scan right, nella seconda riga parto da R e mi chiedo se minore di K, quindi mi fermo subito perché in questo caso al primo tentativo fallisce la condizione less(a[++i],v), quindi siccome sono uscito dal ciclo vado a fare il secondo ciclo while. Quindi sempre nella seconda riga parto da S in fondo e mi chiedo se S è maggiore di K, sì allora continuo con il while, O è maggiore di K? Si quindi procedo. X è più grande di K? Si allora ancora altro giro. C è più grande di K? No allora mi fermo, esco da questo while.

Ora ho trovato in due punti dell’array, su a[i] un elemento che è più grande del pivot e dovrebbe essere più piccolo, e dall’altra parte un elemento più piccolo del pivot e dovrebbe essere più grande, quindi li scambio, scambio cioè R e C, ciò che succede alla terza riga, questo mediante la funzione exch nel codice. Arrivati in fondo al codice ricominciamo da capo grazie al while(true) ma senza scambiare i e j, quindi ricominciamo da dove siamo arrivati. Infatti, alla quarta riga abbiamo: A<K? Si, T<K? No quindi ci fermiamo. Poi dall’altra parte? Q>K? Si, M>K? Si, I>K? No abbiamo così trovato un’altra coppia di elementi che deve essere scambiata, abbiamo infatti quello grande che dovrebbe essere piccolo e viceversa, quindi mediante la riga 5 li scambiamo.

Si va poi avanti in questo modo finché non arriviamo nella riga 8 dove E<K ma L>K quindi K viene prima di L, scambio la E con K e ho trovato il posto con K, questo è quello che succede quando if(i>=j) ritorna true quindi faccio quello che nel codice viene chiamato final exchange. Questo meccanismo sfrutta bene la località.

Conclusione sul processo di partizionamento

Notiamo che con questo meccanismo a ogni passaggio ottengo un elemento che in questo caso è K a posto e il sub-array inferiore è tutto minore di K, mentre il sub-array superiore è tutto fatto da elementi maggiori di K, nessuno dei due è ordinato. A questo punto viene rifatta l’operazione sul primo sub-array e sul secondo sub-array.

Notiamo che mentre mergesort, soprattutto nella versione top-down, prende elementi spaccando a metà il vettore originale, questo potrebbe spaccare gli elementi a caso, potrebbe anche succedere che il posto giusto del pivot è esattamente dov’è, cioè in prima posizione. Le prestazioni di questo algoritmo, quindi il numero di giri che devo fare qui dentro, cambia significativamente in funzione dell’input. Mentre mergesort impiega sempre lo stesso numero di confronti qualunque sia l’input, questo invece no perché non sappiamo dove sarà la posizione del pivot.

Performance del quicksort

L’aver fatto la fase di shuffle rende un po' più probabile ma non certo che a ogni giro l’elemento pivot stia approssimativamente a metà tra tutti gli altri, cosa che non è garantita e succede con probabilità sempre più bassa quanto più ci sono degli elementi duplicati perché si ammassano tutti da una parte del vettore.

Vediamo la traccia completa dell’algoritmo applicata alla stringa quicksortexample: ogni singolo passaggio di questa traccia richiede un partizionamento, quindi quello che è interessante è il partizionamento e non la sequenza.

All’inizio si pensava non funzionasse pubblicando l’algoritmo ha pubblicato anche la dimostrazione proprio perché Hoare era un matematico dimostrò che quell’algoritmo a ogni passo andava a creare condizioni che convergevano verso un array ordinato, perché a ogni passo il nostro array è un po' più ordinato del passo precedente perché ha almeno un elemento al suo posto.

Ne esiste anche una versione iterativa e non ricorsiva che è preferibile perché non lavora sullo stack ma solo muovendo gli indici, però quella ricorsiva si capisce cosa sta facendo leggendo il codice. La complessità nel caso peggiore è n² perché nel caso peggiore non devo mettere a posto due array più piccoli ma un elemento è al suo posto quindi devo fare n passaggi per confrontare gli elementi e cercare il loro posto e poi n passaggi per trovare un posto a tutti gli elementi, quindi n², in realtà poi è (n²)/2 perché devo trovare posto a sempre meno elementi.

Inoltre, i dati che dobbiamo ordinare dopo la randomizzazione riescono ad andare in convergenza molto velocemente, cioè il mio pivot finisce quasi sempre più o meno in mezzo all’array. Ci sono anche altri vantaggi, ad esempio che l’inner loop, quello del metodo partition, è talmente sintetico che è difficile pensare a qualcosa di più veloce.

Notiamo inoltre che nel metodo partition, a differenza del mergesort, viene utilizzato un valore fisso, infatti v viene preso una volta per tutte come elemento di confronto, mergesort invece deve fare sempre due accessi in memoria per prendere i due elementi da confrontare, in questo caso invece il pivot è in memoria, nell’implementazione sarà sul registro della macchina quindi il confronto sarà più veloce perché verrà fatto solo 1 accesso per ogni confronto, invece mergesort ne fa 2.

Notiamo che inoltre gli scambi li fa solo se incontra degli elementi che non sono a posto, questo vale anche per mergesort. Il problema però di mergesort è che deve comunque fare le copie per poter poi fare il merge. Inoltre, in totale il numero di confronti che quicksort fa è abbastanza piccolo. La performance di quicksort dipende da quanto è fortunato nel partizionare l’array, se il pivot cade sempre più o meno a metà è praticamente equivalente a mergesort perché sta facendo partizionamento in parti uguali, se invece il pivot tende a cadere all’inizio o alla fine dell’array si crea uno squilibrio nelle dimensioni dei due array e, nel caso peggiore che si verifica quando il pivot è sempre all’inizio o sempre alla fine, l’altro array da ordinare è massimale quindi devo fare N operazioni per riordinarli tutti. Quicksort usa confronti (e scambi) in media per ordinare.