Questão FC373178
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;
}
A estratégia apresentada em Java é o método de ordenação
- Bubblesort.
- Mergesort.
- Insertion Sort.
- Quicksort.
- Heapsort.
Mostrar resposta e comentário
Gabarito
D
Comentário do professor
A estratégia apresentada é o Quicksort. O método é recursivo: após a partição ele chama-se sobre os subvetores à esquerda e à direita do pivô.
O pivô é escolhido como o primeiro elemento (P = vetor[inicio]). A rotina separar usa dois índices (i e f) que avançam do início e do fim em direção ao centro, comparando com o pivô e trocando elementos quando necessário, até que i > f.
No fim da partição o pivô é colocado na posição f e essa posição é retornada; então ordena(vetor, inicio, f-1) e ordena(vetor, f+1, fim) processam os subproblemas.
Esse esquema de deslocamento simultâneo dos índices caracteriza a partição do tipo Hoare. Complexidade média \(O(n\log n)\); pior caso \(O(n^2)\) se o pivô for sempre ruim.
Conteúdo do catálogo FC Concursos · Atualizado em