Quicksort
Sceglie un valore, il perno (pivot), e mette i valori più piccoli alla sua sinistra e quelli più grandi alla sua destra. Poi fa lo stesso su ogni lato.
- Ω(n log n)
- Θ(n log n)
- O(n²)
- O(log n)
- no
- sì
Caso migliore: come cresce il tempo con la dimensione n della lista quando l'input è il più facile per questo algoritmo.
Caso medio: crescita tipica del tempo con n. Con n², raddoppiare il numero di valori quadruplica circa il tempo; n log n cresce molto meno.
Caso peggiore: la crescita sull'input più difficile. Utile quando la velocità non deve mai calare.
Spazio: quanta memoria extra serve oltre alla lista. 1 vuol dire poche variabili, n una copia della lista.
Stabile: due valori uguali mantengono il loro ordine originale. Conta quando si ordinano record in base a un solo campo.
Sul posto: ordina dentro la lista stessa, senza una seconda lista.
- confronto
- spostamento
- perno
- al suo posto finale
Profondità di ricorsione: 0 · minima possibile: 4 · caso peggiore: 23 in attesa del suo perno
Premi Riproduci: le linee mostrano come cresce il costo
Premi Riproduci o avanza passo passo.
Spazio: riproduci o metti in pausa. Frecce sinistra e destra: passo passo. Home e Fine: salta.
Prova così: Scegli una lista invertita. Il perno è sempre il minimo o il massimo rimasto, quindi un lato resta vuoto e il costo sale verso n².
Come funziona
Qui il perno è l'ultimo valore dell'intervallo. Da sinistra a destra, ogni valore non più grande del perno passa sul lato sinistro con uno scambio. Poi il perno va tra i due gruppi, dove resta per sempre. Ogni lato viene poi ordinato allo stesso modo.
Quando conviene usarlo
Uno dei modi più veloci per ordinare nella pratica, e non richiede quasi memoria extra. Ma se continua a scegliere un perno sbagliato, per esempio su una lista già ordinata, diventa lento. Le versioni reali scelgono il perno con più cura.