Quicksort | |
---|---|
![]() | |
Classe | Algoritmo di ordinamento |
Struttura dati | Variabile |
Caso peggiore temporalmente | |
Caso ottimo temporalmente | |
Caso medio temporalmente | confronti |
Caso peggiore spazialmente | Dipende dalle implementazioni |
Ottimale | Spesso |
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ì:
Ho una lista di elementi da ordinare -> 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-> spezzo la lista nell'indice del valore che ho usato per i confronti -> 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.