Complessità temporale e spaziale

Complessità temporale:

• Caso medio: O(n log n)
  • Un pivot bilanciato divide l'array all'incirca a metà ogni volta, producendo circa log n livelli di lavoro di partizionamento O(n).
• Caso peggiore: O(n²)
  • Se il pivot è sempre l'elemento più piccolo o più grande (per esempio, un array già ordinato con l'ultimo elemento come pivot), ogni volta un lato è vuoto e la ricorsione raggiunge una profondità di n livelli.

Complessità spaziale:

• O(n) per la versione che realizziamo qui, poiché a ogni passaggio creiamo nuove liste di elementi più piccoli e più grandi. Il Quick Sort classico in-place riduce lo spazio aggiuntivo a O(log n).

Riepilogo:

• Quick Sort è molto veloce in media ed è un algoritmo di ordinamento molto usato nella pratica.
• Una scelta poco efficace del pivot può farlo degradare a O(n²); buone strategie per scegliere il pivot (come scegliere un elemento casuale o la mediana) lo evitano.