'''Quicksort''' è un ottimo [[algoritmo di ordinamento]] [[Algoritmo ricorsivo|ricorsivo]] [[Algoritmo in loco|in place]] che, come [[merge sort]], si basa sul paradigma [[Divide et impera (informatica)|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 [[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 mediamente solo <math> N \log N\!</math> 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 implementazione 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 [[Charles Antony Richard Hoare|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.
