Quicksort, come funziona, esempio

Introduzione

Il quicksort è un algoritmo di ordinamento scoperto da Tony Hoare nel 1962. Tra gli algoritmi di ordinamento, è considerato in linea generale il più efficiente di tutti gli altri. Esso adotta la metodologia del divide et impera, ovvero che risolve un problema dividendolo in più sottoproblemi, quindi frutta il paradigma della ricorsione.

Qual è l’idea?

Supponiamo di avere un array A.
Il quicksort opera scegliendo un indice casuale, chiamato pivot (o perno, in italiano), così da dividire il vettore in due parti. Successivamente si occupa di portare alla sinistra del pivot gli elementi minori o uguali ad esso e a destra quelli maggiori. Infine chiama ricorsivamente i due sottoarray e vi esegue le medesime operazioni.
Il passaggio “combina” in questo algoritmo non è necessario, perché dopo tutte le chiamate ricorsive, l’array è ordinato.

Pseudocodice e descrizione

Il quicksort comprende una procedura chiamata partition, che si occupa di spostare gli elementi e di ritornare il valore dell’indice di mezzo, e poi due chiamate ricorsive sui due sottoarray.

Scriviamo adesso lo pseudocodice ispirato dal libro Introduzione agli Algoritmi.

QuickSort:

QuickSort(A, p, r)

    if (p < r)
        q = Partition(A, p, r)
        QuickSort(A, p, q-1)
        QuickSort(A, q+1, r)

La funzione principale del quicksort, se non consideriamo le operazioni fatte nella partition, è abbastanza semplice, purché si conosca bene la tecnica del divide et impera.
Dobbiamo capire che quello che succede, è che nella variabile q viene assegnato l’indice di mezzo e successivamente avvengono le chiamate ricorsive sui sottoarray alla destra e alla sinistra di q.
Al violarsi della condizione iniziale il processo si ferma e avremo l’array ordinato.
Quella che in realtà risulta più ostica da capire è la procedura partition, che è quella che fa il vero lavoro.
Andiamo quindi innanzitutto a scrivere pseudocodice:

Partition:

Partition(A, p, r)

    x = A[r]
    i = p-1
    
    for (j=p to r-1)
        if (A[j] ≤ x)
            i = i+1
            exchange A[i] with A[j]
    
    exchange A[i+1] with A[r]
    return i+1

Dallo pseudocodice vediamo che viene assegnata alla variabile x il valore del pivot scelto (solitamente si sceglie l’ultimo elemento), e ad i l’indice dell’elemento prima di p, che inizialmente non esiste.
Durante le operazioni possiamo distinguere 4 parti nell’array:
una parte dove si trovano gli elementi minori o uguali ad x, una dove si trovano quelli maggiori di x, una dove ci sono gli elementi ancora da guardare ed infine l’indice contente il pivot.
Nel ciclo for scorre l’array attraverso l’indice j che parte dal primo elemento e arriva fino all’elemento prima del pivot.
Se il valore in A[j] è minore o uguale al pivot, avviene l’incremento di i e lo scambio dei valori tra A[i] e A[j], così da tenere a sinistra i valori minori o uguali. Altrimenti non si fa niente.
Alla fine del ciclo viene eseguito lo scambio finale con il pivot e si ritorna il valore i+1 che corrisponderà al valore di mezzo (q).

Esempio di chiamata partition

Qua sotto abbiamo una rappresentazione dei vari passaggi, all’incrementare dell’indice j, della prima chiamata di partition su un array A = [8, 2, 7, 1, 3, 5, 6, 4].

Complessità

Quicksort lavora il loco, quindi non viene utilizzato spazio in memoria aggiuntivo, quindi la complessità in spazio equivale a Θ(n), ovvero la dimensione dell’array. Tuttavia bisogna considerare il fatto che essendo un algoritmo ricorsivo, si utilizza memoria in più per generare la stack.
La complessità di tempo vale Θ(n²) al caso pessimo e Θ(n logn) sia al caso ottimo che al caso medio.

Analizzando l’algoritmo notiamo che ci sono tre operazioni che influiscono sulla complessità di tempo: uno è la chiamata partition che ha complessità Θ(n) e poi le due chiamate ricorsive consecutive, che prendono una tempo T(q-1) e l’altra T(n-q). L’equazione di ricorrenza sarà quindi:

Caso pessimo

Dimostriamo che al caso pessimo, il quicksort ha complessità Θ(n²).

Intuitivamente, per capire in quale circorstanza in questo algoritmo si presenta il caso pessimo, dobbiamo pensare di avere un pivot “errato” che genera il massimo sbilanciamento nella divisione in parti dell’array, così da dover poi effettuare nella partition, n-1 confronti, poi n-2 confronti, n-3 e così via. Questo significa che ogni volta il numero di confronti diminuisce sempre e soltanto di 1 elemento, fino alla fine delle chiamate.
Vediamo l’albero di ricorsione

cn + c(n – 1) + c(n – 2) + c(n – 3) + … + 2c =
raccogliendo c
c( n + (n – 1) + (n – 2) + (n – 3) + … + 2) =
considerando la formula di Gauss per la somma dei primi n numeri
c( n(n+1) / 2 – 1) =
-1 perché la somma parte da 2, allora il tutto che equivale a circa
Θ(n²)

Quicksort randomizzato

Il quicksort è già di per sé un buon algoritmo, ma è possibile comunque migliorarlo evitando la probabilità di incontrare dei casi sfavorevoli che influiscono sui tempi di esecuzione, accade specialmente per grandi quantità di elementi da ordinare.

Il random quicksort o quicksort randomizzato è un normale quicksort dove però il pivot si sceglie in maniera randomica.
La scelta del pivot randomico si effettua da un’altra procedura partition, che chiameremo random partition ed è quella che viene chiamata dalla funzione principale di quicksort. Questa modifica porta la complessità dell’algoritmo al caso pessimo su O(n²).
Quindi il random quicksort va riscritto in questo modo:

Partition(A, p, r)
    x = A[r]
    i = p-1
    for (j=p to r-1)
        if (A[j] ≤ x)
            i = i+1
            exchange A[i] with A[j]  
    exchange A[i+1] with A[r]
    return i+1

//Nuova funzione
Random-Partition(A, p, r)
    i = random(p,r)
    exchange A[i] with A[r]
    return partition(A, p, r)

RandomQuickSort(A, p, r)
    if (p < r)
        q = Random-Partition(A, p, r)
        RandomQuickSort(A, p, q-1)
        RandomQuickSort(A, q+1, r)