Quicksort è un algoritmo di ordinamento efficiente, sviluppato dallo scienziato informatico britannico Tony Hoare nel 1959 e pubblicato nel 1961. È un algoritmo basato sul confronto, il che significa che misura le differenze tra gli elementi che devono essere ordinati. Funziona utilizzando un approccio “dividi e conquista”, che divide gli elementi in due sottogruppi, che vengono poi ordinati in modo ricorsivo.
Quicksort utilizza una combinazione di ordinamento della selezione e partizionamento per ordinare un array. Nell'ordinamento per selezione, l'algoritmo cerca l'elemento più piccolo dell'array e lo scambia con il primo elemento dell'array. Questo scambio garantisce che l'elemento più piccolo sia sempre all'inizio dell'array. La fase di partizionamento sposta quindi il valore dell'elemento corrente in un posto tra gli elementi con valori minori e maggiori di esso. Questo viene fatto selezionando prima un elemento dell'array, noto come "pivot". Tutti gli elementi più piccoli del pivot vengono messi prima del pivot, mentre tutti gli elementi più grandi del pivot vengono messi dopo di esso. Questo processo viene ripetuto con i due sottogruppi appena creati finché l'array non viene ordinato.
La complessità temporale del Quicksort dipende dal pivot scelto, ma nella maggior parte dei casi la complessità temporale del Quicksort è O(n log n). Ciò rende Quicksort un algoritmo di ordinamento preferito, per la sua velocità relativamente elevata. È anche preferito a causa del suo basso fabbisogno di memoria.
Quicksort è ampiamente utilizzato in molte aree dell'informatica, come sistemi operativi, database e grafica. Viene spesso utilizzato anche come parte della libreria standard in molti linguaggi di programmazione come C, Java e Python.
