Quicksort

Da Wikipedia, l'enciclopedia libera.

Quicksort

Un'altra appresentazione grafica dell'algoritmo Quicksort

Quicksort è un ottimo 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 più piccoli a sinistra rispetto a questo e gli elementi più grandi 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 1960. Il Quicksort è molto popolare dato che è facilmente implementabile ed è un buon algoritmo general purpose, che ha un buon comportamento in un ampia varietà di situazioni ed in molti casi richiede meno risorse di qualsiasi altro algoritmo. Offre inoltre il vantaggio di operare direttamente sul file da ordinare (utilizzando un piccolo stack ausiliario), e per effettuare l'ordinamento di N elementi richiede solo operazioni e ha un ciclo interno estremamente breve. Gli svantaggi sono dati dal fatto che non è stabile, nel caso peggiore ha un comportamento quadratico ed è particolarmente fragile: un semplice errore nella sua implementazone può passare inosservato ma causare in certe situazioni un drastico peggioramento nelle prestazioni dell'algoritmo.

Il Quicksort è stato sottoposto a un'analisi matematica approfondita ed estremamente precisa, tanto che le sue prestazioni sono state comprese a fondo e il suo comportamento è stato descritto in modo molto accurato. I risultati ottenuti in fase di analisi sono stati verificati sperimentalmente in modo esteso e l'algoritmo di base è stato migliorato al punto da diventare il metodo ideale per un gran numero di applicazioni pratiche.

Sono stati svolti inoltre numerosi studi per migliorare le prestazioni anche in considerazione del fatto che la ricerca di un algoritmo di ordinamento più veloce è una delle principali attrattive dell'informatica. Praticamente dal momento in cui Hoare pubblicò per la prima volta il suo lavoro, la letteratura specializzata iniziò a proporre versioni migliorate dell'algoritmo. Sono state provate e analizzate molte idee, ma l'algoritmo è così ben bilanciato da far si che il miglioramento apportato in una parte del programma quasi inevitabilmente dia luogo a un peggioramento delle prestazioni in qualche altro punto.

Per la sua estrema facilità è stato scelto in molte librerie di linguaggi come il C di implementare di base una funzione che effettui l'ordinamento del Quicksort. C'è da tenere presente che spesso ci si può sorprendere del comportamento indesiderato e inatteso in presenza di input particolari, specialmente se si tratta di versioni dell'algoritmo messe a punto accuratamente. Se un'applicazione non giustifica il lavoro necessario ad assicurare che l'implementazione del Quicksort sia esente da errori lo Shell sort rappresenta una scelta sicura in grado di garantire presetazioni sufficientemente buone a fronte di un minore sforzo implementativo.

[modifica] 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 più piccoli e a destra i più grandi, 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 è:

  begin
    if n  <  =  1 then return A
    else
      begin 
        scegli a caso un intero k tra 1 ed n 
        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

C'è da notare che la partition è la funzione più discussa dagli studiosi. In molte versioni inizia la scelta del pivot in modo casuale. Quindi effettua una scansione degli elementi dalla sinistra saltando quelli più piccoli e dalla destra saltando quelli più grandi, scambiando gli elementi che arrestano le scansioni e continuando fino a che i puntatori utilizzati per la scansione si incrociano. La scansione partita da sinistra si ferma una volta incontrato l'elemento pivot, mentre quella partita da destra in interrompe quando arriva al carattere precedente al pivot. Questo ciclo continua e l'ultima operazione da effettuare consiste nell'invertire le posizioni degli ultimi elementi che hanno interrotto la scansione.

[modifica] 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 interni p,q tali che denotiamo A_p,q = (A[p],A[p + 1],...A[q]) . Il cuore dell'algoritmo è costituto 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 α della prima componente A[p]; questa funzione modifica quindi il valore delle componenti di A_p,q e restituisce un indice che gode delle seguenti proprietà:

1. A[l] assume il valore α
2. A_{p,l − 1} contiene i valori minori o uguali ad α originariamente contenti in A_{p + 1,q}
3. A_l,q contiene i valori maggiori di α originariamente contenuti in A_{p + 1,q}

La funzione partition può essere calcolata dalla seguente procedura nella quale due puntatori scorrono il vettore da destra a sinistra e viceversa confrontando le componenti con l'elemento scelto casualmente. Per impedire ad uno dei due puntatori di uscire dall'insieme dei valori ammissibili aggiungiamo una sentinella al vettore A, cioè una componente A[n + 1] che assume un valore convenzionale superiore a quello di tutti gli elementi di A.

Supponiamo inoltre che il parametro A rappresenti una variabile globale; per questo motivo gli unici parametri formali della procedura sono p e q che rappresentano gli indici del sottovettore sul quale si opera la partizione (assumiamo sempre ). Le altre variabili che compaino nella procedura sono locali.

 i : =  p  +  1
 j : =  q
 while i  <  j do 
   begin
     while A[j]  >  A[p] do j : =  j - 1
     while A[i]  A[p] E 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

Rianalizzando l'algoritmo del quicksort prima esposto si comprende che la funzione partition è il fulcro delle operazioni

[modifica] Analisi delle prestazioni

[modifica] 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 . Questo implica che per ogni :

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 poiche 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 è Θ(n²).

[modifica] 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.

[modifica] 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.

[modifica] 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 utilizzano un 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'implmenetazione 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 logn 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 casuare 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 estramente 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.

[modifica] 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 migliorare 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)

 begin
 if l - q  <  q - l then 
   begin 
    if p  <  l - 1 then Quicksort (p,l-1) 
    if l + 1  <  q then Quicksort (l + 1, q)
   end 
 else
   begin
    if l+1  <  q then Quicksort (l+1,q) 
    if p  <  l-1 then Quicksort (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 mantenre 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 iterativo 
 Input: un vettore A con i dati da ordinare
   begin 
     p : =  1
     q : =  n 
     S : =  NULL
     repeat
       while q  -  p  1 do 
          begin
            scegli a caso un intero k tra p e q 
            Scambia (A[p],A[k])
            esegui la Partition(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 O 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.

[modifica] 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 almento della metà. Quindi durante la computazione la pila può contenere al più log₂N elementi dove n è la dimensione dell'input.

[modifica] 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 non la effettuiamo a caso, ma sulla parte di vettore da ordinare che risulta più corta (e quindi mai maggiore della metà del vettore di partenza), otteniamo contemporaneamente una strategia che: riduce il numero di chiamate ricorsive, utilizza lo stack di sistema senza doverne creare uno ad hoc, limita la profondità massima dello stack, anche nel caso peggiore, a log₂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;
        }
    }   
}

[modifica] File parziali di piccole dimensioni

[modifica] Partizionamento con il 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.

[modifica] Chiavi duplicate

[modifica] Stringhe e vettori

[modifica] Selezione

[modifica] Implementazioni

Seguono alcuni esempi di implementazione in vari linguaggi.

[modifica] C

 void sort(int array[], int begin, int end) {
    if (end > begin) {
       int pivot = array[begin];
       int l = begin + 1;
       int r = end+1;
       while(l < r) {
          if (array[l] < pivot) {
             l++;
          } else {
             r--;
             swap(array[l], array[r]); 
          }
       }
       l--;
       swap(array[begin], array[l]);
       sort(array, begin, l);
       sort(array, r, end);
    }
 }

[modifica] C++

#include <algorithm>
#include <iterator>
#include <functional>

template <typename T>
void sort(T begin, T end) {
    if (begin != end) {
        T middle = partition (begin, end, bind2nd(
                less<iterator_traits<T>::value_type>(), *begin));
        sort (begin, middle);
        sort (max(begin + 1, middle), end);
    }
}

[modifica] Haskell

  sort :: (Ord a)   => [a] -> [a]
  
  sort []           = []
  sort (pivot:rest) = sort [y | y <- rest, y < pivot]
                      ++ [pivot] ++ 
                      sort [y | y <- rest, y >=pivot]

[modifica] Java

Questo esempio mostra un quicksort generico, piuttosto che uno che funzioni con gli interi o con le stringhe.

import java.util.Comparator;
import java.util.Random;

public class Quicksort {
    public static final Random RND = new Random();      
    private void swap(Object[] array, int i, int j) {
        Object tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    private int partition(Object[] array, int begin, int end, Comparator cmp) {
        int index = begin + RND.nextInt(end - begin + 1);
        Object pivot = array[index];
        swap(array, index, end);        
        for (int i = index = begin; i < end; ++ i) {
            if (cmp.compare(array[i], pivot) <= 0) {
                swap(array, index++, i);
            }
        }
        swap(array, index, end);        
        return (index);
    }
    private void qsort(Object[] array, int begin, int end, Comparator cmp) {
        if (end > begin) {
            int index = partition(array, begin, end, cmp);
            qsort(array, begin, index - 1, cmp);
            qsort(array, index + 1,  end,  cmp);
        }
    }
    public void sort(Object[] array, Comparator cmp) {
        qsort(array, 0, array.length - 1, cmp);
    }
}

[modifica] Joy

 DEFINE sort == [small][]
                [uncons [>] split]
                [[swap] dip cons concat] binrec .

[modifica] Lisp

 (defun qsort (lst cmp / x y l e g)
   (if lst
     (progn
       (setq x (nth (/ (length lst) 2) lst))
       (foreach y lst
        (cond
          ((equal y x)
            (setq e (cons y e)))
          ((apply cmp (list y x))
            (setq l (cons y l)))
          (T (setq g (cons y g)))
        )
       )
       (append (qsort l cmp) e (qsort g cmp))
     )
   )
 )

[modifica] Pascal

 procedure sort( var r : ArrayToSort; lo, up : integer );
 var  
    i, j : integer;
    tempr : ArrayEntry;
 begin
    while up>lo do 
       begin
          i := lo;
          j := up;
          tempr := r[lo];
          {*** Split file in two ***}
          while i<j do 
             begin
                while r[j].k > tempr.k do j := j-1;
                r[i] := r[j];
                while (i<j) and (r[i].k<=tempr.k) do i := i+1;
                r[j] := r[i]
             end;
          r[i] := tempr;
          {*** Sort recursively ***}
          sort(r,lo,i-1);
          lo := i+1
       end
 end;

[modifica] Perl

sub qsort {
  @_ or return ();
  my $p = shift;
  (qsort(grep $_ < $p, @_), $p, qsort(grep $_ >= $p, @_));
}

[modifica] Perl 6

multi quicksort () { () }
multi quicksort (*$x, *@xs) {
   my @pre  = @xs.grep:{ $_ <  $x };
   my @post = @xs.grep:{ $_ >= $x };
   (@pre.quicksort, $x, @post.quicksort);
}

[modifica] Python

def partition(array, begin, end, cmp):
    while begin < end:
         while begin < end:
            if cmp(array[begin], array[end]):
                (array[begin], array[end]) = (array[end], array[begin])
                break
            end -= 1
         while begin < end:
            if cmp(array[begin], array[end]):
                (array[begin], array[end]) = (array[end], array[begin])
                break
            begin += 1
    return begin

def sort(array, cmp=lambda x, y: x > y, begin=None, end=None):
    if begin is None: begin = 0
    if end   is None: end   = len(array)
    if begin < end:
        i = partition(array, begin, end-1, cmp)
        sort(array, cmp, begin, i)
        sort(array, cmp, i+1, end)

[modifica] Prolog

append([], L, L).
append([H | L1], L2, [H | Result]) :- append(L1, L2, Result).

partition([], _, [], []).
partition([H | T], X, [H | Left], Right) :- H =< X, partition(T, X, Left, Right).
partition([H | T], X, Left, [H | Right]) :- H > X, partition(T, X, Left, Right).

qsort([],[]).
qsort([H | Tail], Sorted) :-
        partition(Tail, H, Left, Right),
        qsort(Left, SortedLeft),
        qsort(Right, SortedRight),
        append(SortedLeft, [X | SortedRight], Sorted).

[modifica] Ruby

 def qsort(list)
  return [] if list.size == 0
  x, *xs = *list
  less, more = xs.partition{|y| y < x}
  qsort(less) + [x] + qsort(more)
 end

[modifica] SML

 '''fun''' quicksort lt lst =
   '''let''' val rec sort =
     fn [] => []
      | (x::xs) =>
         '''let'''
           val (left,right) = List.partition (fn y => lt (y, x)) xs
         '''in''' sort left @ x :: sort right
         '''end'''
   '''in''' sort lst
 '''end'''

[modifica] Voci correlate

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

[modifica] Collegamenti esterni

• Interactive quicksort
• Multidimensional quicksort in Java
• Efficient quicksort implementation in C, available under a liberal license

[modifica] 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.