Ordinamento rapido · Complessità
Fonte: Ordinamento rapido · Algoritmi
Idea dell'algoritmo
Algoritmi- Scegli pivot -> partiziona -> ricorri su entrambe le metà
- In-place, non stabile
Tabella complessità
Algoritmi| Caso | Tempo | Spazio |
|---|---|---|
| Best | Θ(n log n) | O(log n) |
| Average | Θ(n log n) | O(log n) |
| Worst | Θ(n²) | O(n) |
Ricorrenza
Algoritmi- T(n) = 2·T(n/2) + Θ(n) ⇒ Θ(n log n)
Schede da colloquio
Algoritmi- Q: Perché usare un pivot casuale? R: per evitare Θ(n²) su input ordinati o avversari.



