Ordenação
Quick sort: o pivô na fila
Escolhe um pivô, menores pra esquerda, maiores pra direita.
Na vida real
O professor quer a turma em ordem de altura. Ele chama um aluno (o pivô) e manda: "quem é mais baixo que ele vai pra esquerda, quem é mais alto vai pra direita". Pronto: o pivô já está no lugar certo da fila. Depois faz a mesma coisa com o grupo da esquerda e com o da direita, até cada grupo ter 1 pessoa.
Código
void quick_sort(int v[], int inicio, int fim) { int pivo, i, j; if (inicio >= fim) return; pivo = v[fim]; i = inicio; j = fim; while (i < j) { while (i < j && v[i] <= pivo) i = i + 1; v[j] = v[i]; while (i < j && v[j] >= pivo) j = j - 1; v[i] = v[j]; } v[i] = pivo; quick_sort(v, inicio, i - 1); quick_sort(v, i + 1, fim);}Também dá pra usar as setas ← e → do teclado.
O que o computador está vendo
Vetor (gavetas)
Tela
- trecho atual
- acabou de mudar
- já está no lugar certo
- borda tracejada: pivô
Peça por peça
| Peça | O que significa |
|---|---|
| pivo = v[fim] | O pivô é o último do trecho. A posição fim fica "livre" (o valor já foi guardado em pivo). |
| i = inicio; j = fim; | i começa no início do trecho, j começa onde o pivô estava. |
| while (v[i] <= pivo) i++ | i anda pra direita enquanto achar valor menor ou igual ao pivô. |
| v[j] = v[i] | Quando i para (achou alguém maior que o pivô), esse valor vai pra posição livre j. |
| while (v[j] >= pivo) j-- | j anda pra esquerda enquanto achar valor maior ou igual ao pivô. |
| v[i] = v[j] | Quando j para (achou alguém menor que o pivô), esse valor vai pra posição livre i. |
| v[i] = pivo | i e j se encontraram: o pivô entra na posição final dele. |
| quick_sort(..., inicio, i - 1) e (i + 1, fim) | Ordena os dois lados. O pivô fica de fora porque já está no lugar. |
Complexidade
| Caso | Tempo | Quando |
|---|---|---|
| melhor | O(n log n) | O pivô divide o trecho ao meio. Recorrência T(n) = 2T(n/2) + n. |
| médio | O(n log n) | Vetor bagunçado: as divisões ficam razoavelmente equilibradas. |
| pior | O(n²) | Pivô sempre o maior ou o menor, por exemplo com o vetor já ordenado e pivô = último. Um lado fica com n - 1 e o outro vazio: T(n) = T(n - 1) + n. |
| memória | O(log n) | Ordena no próprio vetor. Só gasta a pilha de chamadas (no pior caso, O(n)). |
Estável: não, as trocas de longe podem inverter elementos iguais. Como evitar o pior caso: escolher o pivô aleatório ou pela mediana de três.
Pra decorar: "pivô no lugar, menores na esquerda, maiores na direita". O trabalho pesado é na hora de particionar. Não precisa juntar nada no fim.
Outra forma de particionar
Dá pra chegar no mesmo resultado trocando elementos de lugar em vez de deixar uma posição livre. O pivô também é o último, mas só vai pro lugar final numa troca no fim. Essa é a versão que aparece em muitos materiais, mas não é a do professor.
| int particiona(int v[], int ini, int fim) { int pivo = v[fim]; int i = ini - 1; for (int j = ini; j < fim; j++) if (v[j] <= pivo) { i++; troca(v, i, j); } troca(v, i + 1, fim); return i + 1; } | O i marca o fim da área dos menores. O j percorre o trecho inteiro, trocando pra dentro dessa área quem for menor ou igual ao pivô. No fim, troca o pivô pra logo depois dela. |
Merge x Quick
| Merge | Quick | |
|---|---|---|
| divide | no meio, sem pensar | pelo pivô (particiona) |
| trabalho pesado | ao juntar (intercala) | ao dividir (particiona) |
| pior caso | O(n log n) | O(n²) |
| memória extra | O(n) | O(log n) |
| estável | sim | não |
Teste rápido: Com pivô = último, qual vetor deixa o quick sort no pior caso?