Ordenação
Merge sort: dividir a pilha de provas
Divide até sobrar 1, depois junta em ordem.
Na vida real
O professor tem uma pilha de provas pra ordenar por nota. Ele divide a pilha ao meio e passa metade pra um monitor. Cada um divide de novo, até cada pessoa ficar com uma prova só (que já está "ordenada"). Aí vão juntando de duas em duas: olham a prova de cima de cada pilha, pegam a de menor nota, e repetem até acabar.
Código
void merge_sort(int v[], int ini, int fim) { if (fim - ini <= 1) return; int meio = (fim - ini) / 2; merge_sort(v, ini, ini + meio); merge_sort(v, ini + meio, fim); intercala(v, ini, ini + meio, 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
Peça por peça
| Peça | O que significa |
|---|---|
| ini, fim | O trecho [ini, fim) que essa chamada ordena. O fim NÃO entra. Começa com merge_sort(v, 0, n). |
| if (fim - ini <= 1) return; | PARA: trecho com 0 ou 1 elemento já está ordenado. |
| meio = (fim - ini) / 2 | DIVIDE: meio é a quantidade de elementos da metade esquerda. Com tamanho ímpar, a esquerda fica com MENOS elementos. |
| merge_sort(v, ini, ini + meio) | Ordena a metade da esquerda (recursão). |
| merge_sort(v, ini + meio, fim) | Ordena a metade da direita (recursão). |
| intercala(v, ini, ini + meio, fim) | JUNTA: duas metades ordenadas viram uma só, pegando sempre o menor da frente. Usa um vetor auxiliar. |
A intercala por dentro
| int tmp[fim - ini]; int i = ini, j = meio, k = 0; while (i < meio && j < fim) { if (v[i] <= v[j]) tmp[k++] = v[i++]; else tmp[k++] = v[j++]; } while (i < meio) tmp[k++] = v[i++]; while (j < fim) tmp[k++] = v[j++]; for (k = 0; k < fim - ini; k++) v[ini + k] = tmp[k]; | Aqui dentro meio já é o índice absoluto (o que a chamada passou como ini + meio). O i anda em [ini, meio) e o j em [meio, fim). A cada passo, o menor dos dois vai pro tmp. Quando uma metade acaba, os dois while de baixo copiam o que sobrou da outra. No fim, o tmp volta pro vetor. |
Complexidade
| Caso | Tempo | Por quê |
|---|---|---|
| melhor | O(n log n) | Sempre divide ao meio: são log₂ n níveis. Em cada nível, as intercalas passam por n elementos. n × log n. |
| médio | O(n log n) | |
| pior | O(n log n) | |
| memória | O(n) | Por causa do vetor auxiliar da intercala. |
Recorrência: T(n) = 2T(n/2) + n. Duas chamadas com metade do tamanho, mais n da intercala. Estável: sim, o <= faz o igual da esquerda sair primeiro.
Pra decorar: "divide no meio, ordena os dois lados, junta". O trabalho pesado é na hora de juntar.
Teste rápido: Qual a complexidade do merge sort num vetor que JÁ está ordenado?