Guida Quick sort

[ptm]

Algoritmi di ordinamento -> Quick sort

Come può suggerire la parola, il quick sort è un algoritmo di ordinamento efficiente. Fu sviluppato nel 1959 da Tony Hoare, presenta una complessità di O(n log n) ed è normalmente l'algoritmo scelto per l'implementazione del sorting nelle librerie di molti linguaggi. Quick sort, analogamente a merge sort, adotta un approccio Divide et Impera (anche se la parte Divide è più complessa, mentre quella Impera è più semplice). A differenza del merge sort, il quick sort opera in loco, ma non è stabile rispetto all'ordinamento (anche se nel nostro caso base di semplice ordinamento di un vettore di interi non ci importerà)

Concettualmente il abbiamo due operazioni:

1. Scelta di un elemento detto pivot dall'array
2. Partizione, cioè operazione con la quale gli elementi minori del pivot vengono spostati in posizione a sinistra e quelli maggiori alla sua destra (perciò il pivot si trova nella sua posizione finale)

I passi precedenti vengono ripetuti separatamente sui sotto-array dei numeri di valore inferiore e superiore.

Nella figura è possibile osservare in funzionamento dell'algoritmo

Codice

Una possibile implementazione del quick sort è quella che segue. Come al solito sono presenti alcuni commenti accanto alle parti più importanti

Perfavore, Entra oppure Registrati per vedere i codici!

Nota: quicksort in C è implementato nella libreria standard di C/C++ ->

Perfavore, Entra oppure Registrati per vedere i Link!

 

[Scanetatore]

presenta una complessità di O(n log n)

Attenzione che la complessità in rappresentazione di O del Quicksort è O(n^2). ;) Solo la complessità ammortizzata è O(n log n). Infatti se l'array è ragionevolmente piccolo o già ordinato meno gli ultimi elementi un algoritmo come Insertion Sort risulta più efficiente. ;)

Inoltre possiamo far notare che a differenza del Merge Sort opera in loco, il fattore moltiplicativo costante è minore ma non è un algoritmo che ha la stabilità (sempre relativa all'ordinamento).

 

[ptm]

Attenzione che la complessità in rappresentazione di O del Quicksort è O(n^2). ;) Solo la complessità ammortizzata è O(n log n). Infatti se l'array è ragionevolmente piccolo o già ordinato meno gli ultimi elementi un algoritmo come Insertion Sort risulta più efficiente. ;)

Inoltre possiamo far notare che a differenza del Merge Sort opera in loco, il fattore moltiplicativo costante è minore ma non è un algoritmo che ha la stabilità (sempre relativa all'ordinamento).

La tua prima osservazione è corretta, ma è stata una mia scelta scrivere solo la complessità del caso medio senza andarla a dimostrare (come avevo scritto qui: http://www.sciax2.it/forum/c-c/algoritmi-ordinamento-685368.html )
Per la seconda ti ringrazio e provvedo ad aggiungere ;)

 

[Dvdxseo]

Attenzione che la complessità in rappresentazione di O del Quicksort è O(n^2). ;) Solo la complessità ammortizzata è O(n log n). Infatti se l'array è ragionevolmente piccolo o già ordinato meno gli ultimi elementi un algoritmo come Insertion Sort risulta più efficiente. ;)

Vero, ma il caso pessimo per QuickSort si presenta solo in casi molto estremi. Se poi viene randomizzato allora è praticamente impossibile che si comporti in maniera quadratica, quindi è normale considerare più il costo al caso medio che a quello pessimo come invece spesso si fa. Per array piccoli tutto è possibile, e Insertion Sort è una valida scelta; solo che appunto, considerando il tempo asintotico noi ci riferiamo ad array lunghi lunghi lunghi.

 

[Scanetatore]

Vero, ma il caso pessimo per QuickSort si presenta solo in casi molto estremi. Se poi viene randomizzato allora è praticamente impossibile che si comporti in maniera quadratica, quindi è normale considerare più il costo al caso medio che a quello pessimo come invece spesso si fa. Per array piccoli tutto è possibile, e Insertion Sort è una valida scelta; solo che appunto, considerando il tempo asintotico noi ci riferiamo ad array lunghi lunghi lunghi.

Tutto verissimo, ci mancherebbe! ;) Però rimane il fatto che Insertion Sort è veloce quasi quanto questa implementazione se hai già un array parzialmente ordinato (diciamo con gli ultimi record e basta da ordinare). Ovviamente ci si basa sul tempo medio ma se io sono un tuo competitor e scopro che usi Quicksort ovviamente preparo input appositi al tuo programma per far vedere che non funziona così bene. :-P

Il mio era solo un appunto costruttivo ovviamente, giusto perché chi legga abbia un panorama completo. ;) Perché, come sappiamo, fin'ora non abbiamo un algoritmo di ordinamento generico (a meno di costanti altissime) che contemporaneamente:

• Ordini nel caso pessimo in O(nlogn)
• Sia stabile
• Sia in loco

 

[Dvdxseo]

Tutto verissimo, ci mancherebbe! ;) Però rimane il fatto che Insertion Sort è veloce quasi quanto questa implementazione se hai già un array parzialmente ordinato (diciamo con gli ultimi record e basta da ordinare). Ovviamente ci si basa sul tempo medio ma se io sono un tuo competitor e scopro che usi Quicksort ovviamente preparo input appositi al tuo programma per far vedere che non funziona così bene. :-P

Il mio era solo un appunto costruttivo ovviamente, giusto perché chi legga abbia un panorama completo. ;) Perché, come sappiamo, fin'ora non abbiamo un algoritmo di ordinamento generico (a meno di costanti altissime) che contemporaneamente:

• Ordini nel caso pessimo in O(nlogn)
• Sia stabile
• Sia in loco

Sì, vero; ma il mondo è bello perché è vario, avere quel tipo di algoritmo significherebbe spodestare tutti gli altri e un po' mi dispiacerebbe. :P