Sommario:
Definizione - Cosa significa Quicksort?
Quicksort è un popolare algoritmo di ordinamento che è spesso più veloce nella pratica rispetto ad altri algoritmi di ordinamento. Utilizza una strategia di divisione e conquista per ordinare rapidamente gli elementi di dati dividendo un array di grandi dimensioni in due array più piccoli. È stato sviluppato da Charles Antony Richard Hoare (comunemente noto come CAR Hoare o Tony Hoare) nel 1960 per un progetto di traduzione automatica per il National Physical Laboratory.Techopedia spiega Quicksort
Quicksort è un algoritmo utilizzato per ordinare rapidamente gli elementi all'interno di un array, indipendentemente dalla dimensione dell'array. È abbastanza scalabile e funziona relativamente bene per insiemi di dati piccoli e grandi ed è facile da implementare con poca complessità temporale. Lo fa attraverso un metodo di divisione e conquista che divide un singolo array grande in due più piccoli e quindi ripete questo processo per tutti gli array creati fino al completamento dell'ordinamento.
L'algoritmo quicksort viene eseguito come segue:
- Un punto pivot viene scelto dall'array.
- L'array viene riordinato in modo che tutti i valori più piccoli del pivot vengano spostati prima di esso e tutti i valori più grandi del pivot vengano spostati dopo di esso, con valori uguali al pivot che vanno in entrambi i modi. Al termine, il perno si trova nella sua posizione finale.
- Il passaggio precedente viene ripetuto per ciascun subarray con valori più piccoli, nonché eseguito separatamente per il subarray con valori maggiori.
Questo viene ripetuto fino a quando l'intero array non viene ordinato.
