Ordenação¶
A ordenação reorganiza elementos segundo uma relação de ordem. No caso de
comparadores Java, a relação deve satisfazer o contrato de Comparator;
comparações arbitrárias e inconsistentes podem invalidar algoritmos de ordenação.
Propriedades¶
- Estável: elementos com chaves iguais preservam sua ordem relativa da entrada.
- In-place: usa apenas uma pequena quantidade de armazenamento auxiliar sob a convenção declarada.
- Adaptativo: aproveita a ordem existente ou outra estrutura da entrada.
- Baseado em comparações: descobre a ordem apenas comparando elementos.
| Algoritmo | Melhor caso | Caso médio/esperado | Pior caso | Espaço auxiliar | Estável |
|---|---|---|---|---|---|
| Bubble sort com saída antecipada | Θ(n) |
Θ(n²) |
Θ(n²) |
Θ(1) |
Sim |
| Selection sort | Θ(n²) |
Θ(n²) |
Θ(n²) |
Θ(1) |
Não |
| Insertion sort | Θ(n) |
Θ(n²) |
Θ(n²) |
Θ(1) |
Sim |
| Merge sort | Θ(n log n) |
Θ(n log n) |
Θ(n log n) |
Θ(n) |
Sim |
| QuickSort aleatorizado | Θ(n log n) |
esperado Θ(n log n) |
Θ(n²) |
pilha esperada Θ(log n) |
Não |
| Heap sort | Θ(n log n) |
Θ(n log n) |
Θ(n log n) |
Θ(1) |
Não |
A ordenação por comparação requer Ω(n log n) comparações no pior caso sob o
modelo de árvore de decisão. Métodos como Counting sort e Radix sort escapam
desse limite ao adotar premissas adicionais sobre as chaves.