Il QuickSort è uno degli algoritmi di ordinamento più utilizzati e studiati nell’ingegneria del software, inventato da Tony Hoare nel 1959. Si basa sul paradigma del divide et impera.
Il funzionamento prevede la scelta di un elemento dell’array chiamato pivot. L’algoritmo ripartisce quindi gli altri elementi in due sotto-array: quelli minori del pivot e quelli maggiori. Il processo viene ripetuto ricorsivamente per i due sotto-array finché l’intera sequenza non è ordinata.
Proprietà ingegneristiche:
- Complessità media: , il che lo rende estremamente veloce per grandi moli di dati.
- Ordinamento in-place: non richiede memoria aggiuntiva significativa per funzionare.
- Efficienza pratica: grazie all’uso ottimale della memoria cache, è spesso più veloce di altri algoritmi con la stessa complessità teorica (come il MergeSort).
È l’algoritmo di ordinamento predefinito in molte librerie standard di linguaggi di programmazione (come il qsort in C) grazie alle sue eccezionali prestazioni medie su dati reali.