Questão de Algoritmos e Estrutura de Dados — Algoritmos — IUDS 2021
Algoritmos e Estrutura de Dados›Algoritmos
Código
qq664112
Banca
IUDS
Órgão
IF-RJ
Ano
2021
Nível
Superior
Cargo
Analista de Tecnologia da Informação
"Este é o algoritmo mais eficiente na ordenação por comparação. Nele se escolhe um elemento chamado de pivô, a partir disto é organizada a lista para que todos os números anteriores a ele sejam menores que ele, e todos os números posteriores a ele sejam maiores que ele. Ao final desse processo o número pivô já está em sua posição final. Os dois grupos desordenados recursivamente sofreram o mesmo processo até que a lista esteja ordenada."A descrição acima se refere ao algoritmo de ordenação:
ASelection Sort.
BQuick Sort.
CMerge Sort.
DBubble Sort.
Revelar gabarito e comentário▾
GabaritoB — Quick Sort.
Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.
Algoritmo de ordenação Quick Sort
Gabarito: letra B. A descrição do enunciado é a definição clássica do Quick Sort: escolha de um pivô, rearranjo dos elementos para que os menores fiquem antes e os maiores depois, posicionamento do pivô em sua posição final, e aplicação recursiva do mesmo processo às sublistas. Nenhum outro algoritmo de ordenação por comparação possui exatamente este mecanismo de partição com pivô.
O Quick Sort é um algoritmo de ordenação por comparação não estável que utiliza a estratégia de divisão e conquista. Seu funcionamento básico é:
Escolher um elemento como pivô;
Particionar a lista de modo que todos os elementos menores que o pivô fiquem à sua esquerda e todos os maiores à sua direita;
Ao final da partição, o pivô já está em sua posição final;
Recursivamente, ordenar as duas sublistas (esquerda e direita) da mesma forma.
Isso está descrito literalmente no enunciado.
Alternativa A — ❌ Incorreta
O Selection Sort funciona selecionando repetidamente o menor (ou maior) elemento da parte não ordenada e trocando-o com o primeiro elemento não ordenado. Não há escolha de pivô nem partição. O processo é diferente.
Alternativa B — ✅ Correta ⟵ GABARITO
Exatamente o Quick Sort. A menção ao pivô e à partição, com o pivô já na posição final após a partição, é a assinatura desse algoritmo. O texto do enunciado é quase uma transcrição livre da descrição do Quick Sort.
Alternativa C — ❌ Incorreta
O Merge Sort também usa divisão e conquista, mas não trabalha com pivô. Ele divide a lista ao meio recursivamente até obter sublistas de um elemento, e depois as intercala (merge) de forma ordenada. Não há partição em torno de um pivô, e nenhum elemento é colocado em sua posição final antes da intercalação completa.
Alternativa D — ❌ Incorreta
O Bubble Sort percorre a lista repetidamente, comparando elementos adjacentes e trocando-os se estiverem fora de ordem, até que a lista esteja ordenada. Não há escolha de pivô nem recursão (na versão básica).
NÃO CAIA NESSA!
A banca pode tentar confundir Quick Sort com Merge Sort, pois ambos são recursivos e de divisão e conquista. A chave é o pivô: só o Quick Sort particiona em torno de um elemento escolhido como pivô, colocando-o na posição correta. No Merge Sort, a divisão é sempre pelo meio, sem pivô.