Questão FC373179
Para responder à questão a seguir, considere a estratégia de ordenação apresentada em Java abaixo. private static void ordena(int[] vetor, int inicio, int fim) { if (inicio < fim)
Algoritmos e Lógica de Programação
FCC · 2018
Para responder à questão a seguir, considere a estratégia de ordenação apresentada em Java abaixo.
private static void ordena(int[] vetor, int inicio, int fim) {
if (inicio < fim) {
int posicaoP = separar(vetor, inicio, fim);
ordena(vetor, inicio, posicaoP - 1);
ordena(vetor, posicaoP + 1, fim);
}
}
private static int separar(int[] vetor, int inicio, int fim) {
int P = vetor[inicio];
int i = inicio + 1, f = fim;
while (i <= f) {
if (vetor[i] <= P)
i++;
else if (P < vetor[f])
f--;
else { int troca = vetor[i];
vetor[i] = vetor[f];
vetor[f] = troca;
i++;
f--;
}
}
vetor[inicio] = vetor[f];
vetor[f] = P;
return f;
}
Considerando que N é número de elementos do vetor a ser ordenado, a estratégia de ordenação apresentada em Java
- também é conhecida como método de ordenação por intercalação e possui uma versão para unir dois vetores já ordenados.
- tem complexidade O(N 2) no pior caso e no caso médio, mas apresenta complexidade O(N) no melhor caso.
- faz um número fixo de comparações dado por log 2N, independente dos valores do vetor original. Isso é garantido pelas chamadas recursivas ao método ordena().
- utiliza o método separar() para dividir o vetor original em 2 sublistas de igual tamanho. Isso garante que mesmo no pior caso o método realize Nlog2N comparações.
- utiliza o método separar() para fazer a partição do vetor, por meio da seleção de um elemento chamado pivô. A escolha do pivô é crucial para o bom desempenho do método, já que a fase de partição é a parte crítica do algoritmo.
Mostrar resposta e comentário
Gabarito
Errado
Comentário do professor
A alternativa descreve o funcionamento do Quicksort: o método separar() realiza a partição usando um elemento escolhido como pivô. Durante a partição, elementos ≤ pivô são colocados à esquerda e elementos > pivô à direita, por meio de comparações e trocas; ao final o pivô é colocado em sua posição definitiva e seu índice é retornado.
Essa escolha do pivô é crucial porque determina o balanceamento das duas subchamadas recursivas. Pivôs que dividem o vetor de forma aproximadamente igual levam a profundidade de recursão ~log N e custo médio total \(O(N\log N)\). Um pivô ruim (por exemplo, sempre extremo) gera recursões desbalanceadas e pior caso \(O(N^2)\).
Portanto, estratégias de seleção do pivô e diferentes esquemas de partição (ex.: Hoare, Lomuto) impactam diretamente a eficiência prática do algoritmo.
Conteúdo do catálogo FC Concursos · Atualizado em