Quick Sort

L’algoritmo Quick Sort, ideato da Charles Antony Richard Hoare nel 1960, è forse il più famoso algoritmo di ordinamento, ed ha, nel caso medio, le migliori prestazioni tra gli algoritmi basati su confronto. 

Adotta una strategia di tipo divide et impera, ossia divide il problema in tanti sotto problemi, fino a raggiungere dei sotto problemi facilmente risolvibili.

Questo approccio è conveniente solo se lo sforzo per ricomporre le soluzioni dei sotto problemi ed ottenere la soluzione del problema iniziale, è inferiore allo sforzo per risolvere il problema nella sua interezza.

In termini più tecnici abbiamo:

1. Scelta di un elemento dell’array, detto “pivot”
2. Suddivisione del vettore in due “sub-array”
3. Nel primo array tutti gli elementi minori o uguali al pivot, nel secondo quelli maggiori
4. Ordinare i due sub-array separatamente, ossia applicare ricorsivamente per ognuno i passi dal 1 al 4
5. Fondere i due sub-array ordinati insieme.

Riassumendo, abbiamo che l’ordinamento avviene mediante un algoritmo ricorsivo, che viene applicato a sotto-array sempre più piccoli, fino ad arrivare a sotto-array di pochi elementi, che possono essere risolte direttamente, senza altre chiamate ricorsive.

Codificando il tutto si ha:

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

Esempio

Per semplicità di esposizione, è stato scelto come pivot sempre l’elemento centrale.

Rimane da specificare come scegliere il pivot.

E’ stato dimostrato che scegliendo in modo random il pivot, il Quick Sort ha una complessità media di O(n*log n) ma nel caso peggiore di O(n²).

L’ideale sarebbe però che tale risultato fosse raggiunto sempre: a ciò provvede il Merge Sort.