Ordenação rápida · Complexidade
Fonte: Ordenação rápida · Algoritmos
Ideia do algoritmo
Algoritmos- Escolher pivô -> particionar -> recursar as duas metades
- In-place, não estável
Tabela de complexidade
Algoritmos| Caso | Tempo | Espaço |
|---|---|---|
| Best | Θ(n log n) | O(log n) |
| Average | Θ(n log n) | O(log n) |
| Worst | Θ(n²) | O(n) |
Recorrência
Algoritmos- T(n) = 2·T(n/2) + Θ(n) ⇒ Θ(n log n)
Cartões de entrevista
Algoritmos- Q: Por que usar pivô aleatório? R: para evitar Θ(n²) em entradas ordenadas ou adversariais.



