Quicksort - Algoritmi e strutture dati

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ì,

cioè l’elemento che vado a mettere al posto giusto è

sempre il primo del sub-array su cui sto lavorando.

E’ matematicamente dimostrato che questo algoritmo

raggiunge lo scopo per cui è previsto, ci sono algoritmi

per cui il raggiungimento dello scopo è ipotizzato ma

non dimostrato

E’ 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 prativi, 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, quindi 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,

come quella di qualsiasi altra configurazione, però le

configurazioni che ci vanno bene sono molte di più di

quelle che non ci vanno bene.

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

a 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.

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 altro 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 e questo

punto ripeto l’operazione con quel che resta, dopodichè

alla fine scambio a con l’ultimo j.

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, si

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, cioè 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à.

Notiamo che con questo meccanismo a ogni passaggio

io ottengo un elemento che in questo caso è K a posto e

il sub-array inferiore è tutto minore di K, 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 succede 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, cioè 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. 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 succedere e

succede con probabilità sempre più bassa quanto più ci

sono degli elementi duplicati perché si ammucchiano

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

Vediamo la performance del quicksort

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^2 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^2, in realtà poi è (n^2)/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’inenr

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 ordin