APPROFONDIMENTI

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. E' 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 [N log N] 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 sì che il miglioramento apportato in una parte del programma quasi inevitabilmente dia luogo a un peggioramento delle prestazioni in qualche altro punto.