Prof. Paulo Rettore
Universidade Federal de Lavras
GAC124 — Introdução aos Algoritmos
QuickSort e MergeSort são métodos de ordenação eficientes baseados em dividir o problema em partes menores.
Particiona em torno de um pivô.
Divide o vetor e depois intercala trechos ordenados.
Os dois métodos usam recursão em suas versões tradicionais.
Escolha um pivô e reorganize o vetor para que os menores fiquem à esquerda e os maiores à direita.
v = {7, 2, 9, 4, 6}
pivô = 6
menores ou iguais: {2, 4, 6}
maiores: {7, 9}Depois do particionamento, o pivô já está em uma posição correta. Restam duas partes menores para ordenar.
void quicksort(int v[], int inicio, int fim) {
if (inicio >= fim) return;
int pivo = particiona(v, inicio, fim);
quicksort(v, inicio, pivo - 1);
quicksort(v, pivo + 1, fim);
}Trecho com zero ou um elemento.
Ordenar as partes à esquerda e à direita do pivô.
int particiona(int v[], int ini, int fim) {
int pivo = v[fim];
int i = ini;
for (int j = ini; j < fim; j++) {
if (v[j] <= pivo) {
swap(v[i], v[j]);
i++;
}
}
swap(v[i], v[fim]);
return i;
}A escolha do pivô influencia o desempenho. Vetores já ordenados podem gerar casos ruins dependendo da estratégia.
O MergeSort divide o vetor ao meio até sobrar um elemento por parte. Depois, intercala partes já ordenadas.
{1, 7, 9} e {2, 4, 10}
intercalação:
{1, 2, 4, 7, 9, 10}Intercalar compara os primeiros elementos disponíveis dos dois trechos e copia o menor.
void mergesort(int v[], int inicio, int fim) {
if (inicio >= fim) return;
int meio = (inicio + fim) / 2;
mergesort(v, inicio, meio);
mergesort(v, meio + 1, fim);
intercala(v, inicio, meio, fim);
}Primeiro divide; depois resolve as chamadas menores e intercala na volta.
enquanto houver elementos nos dois trechos:
copie o menor para o vetor auxiliar
copie o restante do trecho que ainda não terminou
copie o auxiliar de volta para o vetor originalO MergeSort geralmente precisa de memória auxiliar para realizar a intercalação.
| Aspecto | QuickSort | MergeSort |
|---|---|---|
| Estratégia | Particionamento por pivô. | Divisão e intercalação. |
| Memória auxiliar | Geralmente menor. | Normalmente precisa de auxiliar. |
| Pior caso | Pode ser quadrático. | Permanece em O(n log n). |
| Uso típico | Muito eficiente em memória. | Útil para intercalação e dados externos. |
O(n log n)
O(n²)
O(n log n)
Complexidade é uma forma de comparar como o custo cresce. Não substitui observar entradas reais e requisitos de memória.
Para o vetor {8, 3, 6, 2, 7}, mostre uma etapa do particionamento do QuickSort e uma intercalação do MergeSort.
Gabarito orientador: Explique o pivô, o caso base da recursão e como dois trechos ordenados produzem um único trecho ordenado.
Use estas fontes para consultas pontuais depois da aula:
Os slides completos, o Campus Virtual e o DREDD continuam sendo as fontes principais da disciplina.
O último elemento é o pivô. Avance para acompanhar as comparações e trocas do particionamento de Lomuto.
int p = particiona(v, inicio, fim);
quicksort(v, inicio, p - 1);
quicksort(v, p + 1, fim);Primeiro dividimos; depois, intercalamos os trechos ordenados em uma nova sequência.
mergesort(v, inicio, meio);
mergesort(v, meio + 1, fim);
merge(v, inicio, meio, fim);Use a animação para observar trocas, pivôs, divisões e intercalações com diferentes entradas:
PRÓXIMA AULA
Prof. Paulo Rettore
GAC124 — Introdução aos Algoritmos