Quicksort

Quicksort
Classe	{{{classe}}}
Struttura dati	{{{struttura dati}}}

Quicksort è un algoritmo di ordinamento ricorsivo in place che, come merge sort, si basa sul paradigma divide et impera. La base del suo funzionamento è l'utilizzo ricorsivo della procedura partition: preso un elemento da una struttura dati (es. array) si pongono gli elementi minori a sinistra rispetto a questo e gli elementi maggiori a destra.

Il Quicksort, termine che tradotto letteralmente in italiano indica ordinamento rapido, è l'algoritmo di ordinamento che ha, in generale, prestazioni migliori tra quelli basati su confronto. È stato ideato da Charles Antony Richard Hoare nel 1961.

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 è:

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

Un'altra rappresentazione grafica dell'algoritmo Quicksort

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 $A=(A[1],A[2],...A[n])\,\,n\geq 1$ componenti. Per ogni coppia di interi p,q tali che $1\leq p\leq q\leq n$ denotiamo $A_{p,q}=(A[p],A[p+1],...A[q])$ . Il cuore dell'algoritmo è costituito dalla funzione che partiziona l'insieme, per comodità chiamiamo Partition(p,q). Questa procedura ripartisce gli elementi del vettore $A_{p,q}$ rispetto al valore $\alpha$ della prima componente $A[p]$; questa funzione modifica quindi il valore delle componenti di $A_{p,q}$ e restituisce un indice $l\in [p,p+1,...q]$ che gode delle seguenti proprietà:

1. $A[l]$ assume il valore $\alpha$
2. $A_{p,l-1}$ contiene i valori minori o uguali ad $\alpha$ originariamente contenuti in $A_{p+1,q}$
3. $A_{l,q}$ contiene i valori maggiori di $\alpha$ originariamente contenuti in $A_{p+1,q}$

Rianalizzando l'algoritmo del quicksort prima esposto si comprende che la funzione partition è il fulcro delle operazioni. Nella versione qui presentata l'elemento pivot è fissato a A[p]; questo non è limitativo poiché il chiamante può scegliere un pivot diverso e posizionarlo in A[p] 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 sinistra si ferma su elementi maggiori o uguali al pivot (e quindi è bloccata dall'elemento pivot stesso), mentre quella partita da destra si interrompe quando arriva a un elemento minore del pivot (e quindi è bloccata dall'elemento precedente al 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 A, la funzione riceve i parametri p e q che rappresentano gli indici del sottovettore sul quale si opera la partizione (assumiamo sempre $1\leq p\leq q\leq n$). 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 A[i] ≤ A[p] and i ≤ j 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 $T_{w}(n)$ il massimo numero di confronti tra elementi del vettore di ingresso eseguiti dall'algoritmo su input A di lunghezza n. È evidente che i vettori A1 e A2 della partizione possono essere calcolati mediante n-1 confronti (dato che un elemento viene scelto come pivot). Inoltre la dimensione di A1 e A2 è data rispettivamente da k e n-k-1, per qualche $k\in [0,1,...,n-1]$. Questo implica che per ogni

$n\geq 1$:

$T_{w}(n)=n-1+max_{0\leq k\leq n-1}{T_{w}(k)+T_{w}(n-k-1)}$

mentre per $n=0$:

$T_{w}(0)=0$. Questa è l'equazione di ricorrenza per l'algoritmo in questione. Si vuole ora determinare il $T_{w}(0)$ 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 (il caso peggiore!!). Infatti poiché $max_{0\leq k\leq n-1}[T_{w}(k)+T_{w}(n-k-1)]\geq T_{w}(n-1)$ abbiamo che $T_{w}(n)\geq n-1+T_{w}(n-1)$ e quindi per ogni $n\in N$ otteniamo:

$T_{w}(n)=\sum _{0}^{n-1}k={\frac {n(n-1)}{2}}$.

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 è Θ($n^{2}$).

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 $\lfloor n/2\rfloor$ elementi, ottenendo quindi un tempo asintotico pari a O(nlogn) nel caso peggiore. Ad una 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 n/5 quintuple: l'ultimo sottoarray può non essere una quintupla (ma un insieme più piccolo)
• Per ogni quintupla calcolare il mediano, effettuando in totale, 7n/5 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 T(n/5) (chiamata ricorsiva)

5. Partiziona intorno al pivot: (n-1) confronti (ovvio) 6. Prosegui ricorsivamente: T( (7/10) n ) (perché la chiamata viene effettuata un insieme con cardinalità pari, al più 7n/10 +3).

L'equazione di ricorrenza diventa:

T(n) ≤ (12/5) n + T( n/5 ) + T( (7/10) n )

che ha soluzione O(n), in particolare T(n)<=cn <-> c>24. 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 è $O(n\log(n))$.

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 è Θ(nlogn), precisamente 1.39NlogN.

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à O((1/n)^log n).

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 avrò 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

L'algoritmo utilizza la ricorsione, che in casi di anomalie potrebbe portare a problemi di stack overflow. È possibile operare un processo di rimozione della ricorsione senza alterare le prestazioni utilizzando uno stack esterno che memorizza il "lavoro da fare" in forma di file parziali da ordinare. Ogni qualvolta si richiede un sottofile da ordinare è sufficiente estrarlo dalla stack mentre in seguito a un partizionamento i due file parziali generati possono essere inseritivi. Nell'implementazione ricorsiva (quelle viste sopra), lo stack viene gestito dal sistema contiene le stesse informazioni che si salveranno in questo stack esterno. Per un fle casuale la massima dimensione dello stack è proporzionale a $\log n$ anche se in casi degeneri lo stack può crescere proporzinalmente a N. Il caso peggiore è quello in cui il file risulta già ordinato. Questo problema è tanto sottile quanto reale: anche un programma ricorsivo utilizza (implicitamente ) uno stack, per cui la degenerazione del quicksort per file di grandi dimensioni potrebbe causare una terminazione anomala del programma per mancanza di memoria disponibile. Ovviamente un comportamento del genere deve essere evitato soprattutto se si vuole inserire la routine in una libreria di programma. Non è facile dare garanzie che ciò non avvenga anche se non è difficile fare in modo che questi casi degeneri siano estremamente improbabili.

Per effettuare lo studio della dimensione dello stack si effettua la valutazione dello spazio di memoria necessario alla procedura del quicksort. Oltre alle n celle necessarie per contenere il vettore dei valori di ingresso, occorre utilizzare una certa quantità di spazio per mantenere la pila che implementa la ricorsione. Nel caso peggiore Quicksort(1,n) utilizza uno spazio $O(n)$ per mantenere la pila. Se infatti viene estratto l'elemento maggiore del campione, la pila deve conservare i parametri relativi a un massimo di n - 1 chiamate ricorsive.

Quicksort iterativo

Il primo passaggio da fare per passare dalla strategia ricorsiva a quella iterativa è quello di inserire il più grande dei due sottofile da ordinare nello stack assicurando che ogni sottofile presente nello stack non sia più grande della metà di quello che gli sta sotto, quindi lo stack non dovrà contenere più di un numero logaritmico di oggetti. Questa dimensione massima dello stack si verifica quando il partizionamento è effettuato sempre al centro del file. Per file casuali l'occupazione di stack è verosimilmente piccola.

La versione di base del quicksort potrà essere migliorata modificando appositamente le chiamate ricorsive. Più precisamente si può forzare la procedura ad eseguire sempre la prima chiamata relativa al sottovettore di lunghezza minore. Si ottiene un nuovo algoritmo con le seguenti istruzioni (la procedura viene scritta in pseudocodice):

 Procedure Quicksort(A, p, q)
 Input A vettore di elementi
   begin
     l ← Partition (A, p, q)
     if (l - p) < (q - l) then 
       begin 
         if p < (l - 1) then Quicksort(A,p, l - 1) 
         if (l + 1) < q then Quicksort(A, l + 1, q)
       end 
     else
       begin
         if (l + 1) < q then Quicksort(A, l + 1,q) 
         if p < (l - 1) then Quicksort(A,p, l - 1)
       end
   end

A questo punto è possibile operare la trasformazione e passare nella versione iterativa. Si osserva innanzitutto che in questo caso il criterio di gestione della pila può essere semplificato sfruttando il fatto che le due chiamate ricorsive sono le ultime istruzioni della procedura. Si può quindi definire una versione iterativa nella quale la pila serve per mantenere l'elenco delle chiamate che devono ancora essere eseguite e non sono state neppure iniziate. In altre parole nell'esecuzione della procedura la prima chiamata ricorsiva viene attivata dopo aver accantonato in testa alla pila i parametri necessari per eseguire la seconda. Quest'ultima sarà attivata una volta completata la precedente, quando i suoi parametri si trovano di nuovo in testa alla pila. In particolare non si ha bisogno di mantenere nella pila il record di attivazione della procedura (che qualsiasi linguaggio di programmazione fa ogni qual volta viene chiamata una procedura).

L'algoritmo così ottenuto è descritto dalla seguente procedura:

 Procedure Quicksort(A)
 Input: un vettore A con i dati da ordinare
   begin 
     p ← 1
     q ← n 
     S ← NULL
     repeat
       while (q - p) ≤ 1 do 
          begin
            Partition(A, p, q)
            sia Ap1,q1 il vettore max(Ap,q)
            sia Ap2,q2 il vettore min(Ap,q)
            S ← Push(S, (p1,q1))
            p ← p2
            q ← q2
          end 
     until (S = NULL) or (q - p) < 1
   end

Si può dimostrare che la procedura è corretta. Infatti al termine dell'esecuzione di ogni ciclo repeat-until le parti del vettore di ingresso non ancora ordinate sono contenute nella pila S oppure in A_p,q. La verifica di questa proprietà è facile. Di conseguenza quando si esce dal ciclo la condizione (S ≠ NULL) e (q - p) < 1 garantisce che il vettore di ingresso sia ordinato.

Valutazione altezza massima dello stack

Si osserva innanzitutto che il vettore A_p,q sul quale la macchina sta lavorando non è mai maggiore del vettore che si trova in testa alla pila S. Inoltre, ad ogni incremento di S la dimensione A_p,q, viene ridotta almeno della metà. Quindi durante la computazione la pila può contenere al più $log_{2}N$ elementi dove n è la dimensione dell'input.

Quicksort misto ricorsivo-iterativo

Come descritto per il Quicksort iterativo, anche per questa strategia il primo passo è quello di modificare la procedura ricorsiva considerando il fatto che la seconda chiamata alla funzione Quicksot avviene alla fine della procedura, quando non c'è più quindi la necessità di mantenere nello stack le informazioni e lo stato della funzione chiamante. Si può allora trasformare la seconda chiamata ricorsiva in un loop interno alla funzione chiamante stessa, dopo averne opportunamente aggiornato i parametri d'ingresso. Se a questo primo passo aggiungiamo che la prima chiamata ricorsiva è sempre effettuata sulla parte di vettore da ordinare che risulta più corta (e quindi mai maggiore della metà del vettore di partenza), questa strategia contemporaneamente riduce il numero di chiamate ricorsive e può utilizzare lo stack di sistema (senza doverne creare uno ad hoc) dato che limita la profondità massima dello stack, anche nel caso pessimo, a $log_{2}N$ elementi.

Si riporta una efficiente implementazione in C della strategia descritta. Il codice può essere compilato per ordinare stringhe, numeri interi, etc.

/********** QuickSort(): sorts the vector 'list[]' **********/

/**** Compile QuickSort for strings ****/
#define QS_TYPE char*
#define QS_COMPARE(a,b) (strcmp((a),(b)))

/**** Compile QuickSort for integers ****/
//#define QS_TYPE int
//#define QS_COMPARE(a,b) ((a)-(b))

/**** Compile QuickSort for doubles, sort list in inverted order ****/
//#define QS_TYPE double
//#define QS_COMPARE(a,b) ((b)-(a))

void QuickSort(QS_TYPE list[], int beg, int end)
{
    QS_TYPE piv; QS_TYPE tmp;
    
    int  l,r,p;

    while (beg<end)    // This while loop will substitude the second recursive call
    {
        l = beg; p = (beg+end)/2; r = end;

        piv = list[p];

        while (1)
        {
            while ( (l<=r) && ( QS_COMPARE(list[l],piv) <= 0 ) ) l++;
            while ( (l<=r) && ( QS_COMPARE(list[r],piv)  > 0 ) ) r--;

            if (l>r) break;

            tmp=list[l]; list[l]=list[r]; list[r]=tmp;

            if (p==r) p=l;
            
            l++; r--;
        }

        list[p]=list[r]; list[r]=piv;
        r--;

        // Select the shorter side & call recursion. Modify input param. for loop
        if ((r-beg)<(end-l))   
        {
            QuickSort(list, beg, r);
            beg=l;
        }
        else
        {
            QuickSort(list, l, end);
            end=r;
        }
    }   
}

Implementazione

Una semplice e pratica implementazione in C++ è la seguente (utilizza le STL):

// Input argument: an unordered vector
// Output: a ordered vector
std::vector<int> quicksort(std::vector<int> arr)
{
	// 1) A 1-element or 0-element array is already ordered
	if(arr.size() <= 1)
		return arr;

	// 2) Choose pivotal element
	int pivot_index = arr.size() / 2;
	int pivot_value = arr[pivot_index];
	
	// 3) Get sublists
	std::vector<int> less;
	std::vector<int> greater;

	for(int i=0; i<arr.size(); i++)
	{
		if(i == pivot_index)
			continue;
		if(arr[i] <= pivot_value)
			less.push_back(arr[i]);
		else
			greater.push_back(arr[i]);
	}

	std::vector<int> result;
	std::vector<int> lessOrdered = quicksort(less);
	std::vector<int> greaterOrdered = quicksort(greater);
	result.insert(result.end(), lessOrdered.begin(), lessOrdered.end());
	result.push_back(pivot_value);
	result.insert(result.end(), greaterOrdered.begin(), greaterOrdered.end());

	return result;
}

Bibliografia

• Hoare, C. A. R. (1961): Partition: Algorithm 63, Quicksort: Algorithm 64, and Find: Algorithm 65., Comm. ACM 4, pp. 321–322
• Sedgewick, Robert (1978): Implementing quicksort programs, Communications of the ACM, 21(10) pp. 847–857.
• Musser, David (1997): Introspective Sorting and Selection Algorithms, Software Practice and Experience vol 27, number 8, pp. 983–993
• LaMarca, A.; Ladner, R. E. (1997): The Influence of Caches on the Performance of Sorting, Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 370–379.

Voci correlate

• qsort - Funzione di ordinamento presente nella libreria standard del C, che tipicamente implementa l'algoritmo di ordinamento quicksort.

Altri progetti

Altri progetti

• Wikibooks
• Wikimedia Commons

• Wikibooks contiene implementazioni di quicksort
• Wikimedia Commons contiene immagini o altri file su quicksort

Collegamenti esterni

• Interactive quicksort, su pages.stern.nyu.edu.
• Multidimensional quicksort in Java, su fiehnlab.ucdavis.edu.