Quicksort

Nel seguente testo sull'argomento informatica è presente una sospetta violazione di copyright.

Motivo: Parti della voce (almeno l'inizio) sembrano copiate pari pari dal testo di Sedgewick

---

È sconsigliato wikificare o ampliare il testo attuale, che potrebbe essere cancellato. Puoi invece riformulare il testo con parole tue o partecipare alla discussione. Segui i suggerimenti del progetto di riferimento.
Avvisa l'autore: {{Avvisocontrolcopy|voce=Quicksort}}--~~~~

Quicksort
Quicksort in esecuzione su una lista di numeri. La linea blu è il valore del pivot.
Classe	Algoritmo di ordinamento
Struttura dati	Variabile
Caso peggiore temporalmente	${\displaystyle \Theta (n^{2})}$
Caso ottimo temporalmente	${\displaystyle \Theta (n\log _{2}n)}$
Caso medio temporalmente	${\displaystyle \Theta (n\log _{2}n)}$ confronti
Caso peggiore spazialmente	Dipende dalle implementazioni
Ottimale	Spesso
Manuale

Quicksort è un algoritmo di ordinamento ricorsivo in place non stabile. Si basa anch'esso, come il Merge Sort sul paradigma di Divide et Impera. L'idea dell'algoritmo può essere riassunta così:

1. Ho una lista di elementi da ordinare.
2. Faccio in modo di avere tutti gli elementi più piccoli di un certo elemento presente nella lista da un lato della lista e quelli più grandi dall'altro lato.
3. Spezzo la lista nell'indice del valore che ho usato per i confronti.
4. Itero per i due sottoinsiemi che ho trovato.

Il Quicksort, termine che tradotto letteralmente in italiano indica ordinamento rapido, è l'algoritmo di ordinamento che ha, nel caso medio, prestazioni migliori tra quelli basati su confronto. È stato ideato da Charles Antony Richard Hoare nel 1961.