Questão de Algoritmos e Estrutura de Dados — Algoritmos — IDECAN 2023
Algoritmos e Estrutura de Dados›Algoritmos
Código
qq944802
Banca
IDECAN
Órgão
SEFAZ-RR
Ano
2023
Nível
Superior
Cargo
Implementador de Software
Na computação existem algoritmos que utilizam diferentes técnicas de ordenação para organizar um conjunto de dados. Selecione o algoritmo de ordenação que usa um método eficiente com complexidade C(n) = O(n²) no pior caso, e C(n) = O(n log n) no melhor e médio caso, com o seguinte funcionamento:➢ Escolhe um elemento da lista chamado pivô.➢ Reorganiza a lista de forma que os elementos menores que o pivô fiquem de um lado, e os maiores fiquem de outro.➢ Recursivamente ordena a sub-lista abaixo e acima do pivô.Assinale a alternativa correta.
ASelection Sort
BInsertion Sort
CQuick Sort
DMerge Sort
EShell Sort
Revelar gabarito e comentário▾
GabaritoC — 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”.
Algoritmos de ordenação
Gabarito: letra C. O algoritmo descrito é o Quick Sort, que utiliza um pivô para particionar a lista e ordena recursivamente as partições. Sua complexidade é O(n²) no pior caso (quando o pivô é sempre o menor ou maior elemento) e O(n log n) no melhor e médio caso.
A questão testa o conhecimento das complexidades e do funcionamento dos principais algoritmos de ordenação. O Quick Sort é o único que se encaixa perfeitamente na descrição: escolhe um pivô, rearranja os elementos menores de um lado e maiores do outro, e aplica recursão nas sublistas.
Algoritmos de ordenação
1Quick Sort
Funcionamento
Escolhe pivô
Particiona (menores / maiores)
Recursão nas sublistas
Complexidade
Melhor/médio: O(n log n)
Pior: O(n²)
2Selection Sort
Seleciona o menor → troca
Sempre O(n²)
3Insertion Sort
Insere na posição correta
Melhor: O(n) / Médio/pior: O(n²)
4Merge Sort
Divide ao meio → intercala
Sempre O(n log n)
5Shell Sort
Intervalos decrescentes
Complexidade variável
LEVEL · soulevel.com.br
Alternativa A — ❌ Incorreta
O Selection Sort funciona selecionando o menor elemento e trocando-o com a primeira posição, sem usar pivô ou recursão. Sua complexidade é O(n²) em todos os casos, não apresentando O(n log n) em nenhum cenário.
Alternativa B — ❌ Incorreta
O Insertion Sort constrói a lista ordenada inserindo cada elemento na posição correta, sem pivô. Também possui complexidade O(n²) no pior e médio caso, e O(n) no melhor caso (lista já ordenada), mas nunca O(n log n).
Alternativa C — ✅ Correta ⟵ GABARITO
O Quick Sort é o algoritmo descrito: escolhe um pivô, particiona a lista em menores e maiores, e recursivamente ordena as partições. No pior caso (ex.: lista já ordenada e pivô sempre no extremo) atinge O(n²); no melhor e médio caso, O(n log n).
Alternativa D — ❌ Incorreta
O Merge Sort utiliza o paradigma de divisão e conquista, mas não escolhe um pivô. Ele divide a lista ao meio recursivamente e depois intercala as metades ordenadas. Sua complexidade é O(n log n) em todos os casos, sem pior caso O(n²).
Alternativa E — ❌ Incorreta
O Shell Sort é uma generalização do Insertion Sort que usa intervalos decrescentes. Não utiliza pivô nem recursão. Sua complexidade varia conforme a sequência de intervalos, mas não é O(n log n) no melhor e médio caso com pior O(n²) de forma padronizada; em geral, é pior que O(n log n) em média.
PEGA ESSA DICA!
Decore as complexidades dos principais algoritmos: Quick Sort (pior O(n²), médio O(n log n)), Merge Sort (sempre O(n log n)), Selection/Insertion Sort (sempre O(n²)), Shell Sort (variável, entre O(n) e O(n²)). O Quick Sort é o único que tem pior caso quadrático e médio caso linearítmico, além de ser baseado em pivô.