Questão de Algoritmos e Estrutura de Dados — Algoritmos — FCC 2018
Algoritmos e Estrutura de Dados›Algoritmos
Código
fc044546
Banca
FCC
Órgão
DPE-AM
Ano
2018
Cargo
Assistente Técnico de Defensoria - Programador
Para ordenar um vetor com N elementos, o método de ordenação Seleção (Selection Sort) faz o seguinte número de comparações:
A(N² − N)/2, sendo muito lento e inadequado para valores grandes de N.
Blog₂(N² + N) no melhor caso.
C(N² + N −1)/2 no caso médio, ficando lento para valores grandes de N.
D(N − 1) quando o vetor já está originalmente ordenado.
E(N² + N)/4 no pior caso, sendo melhor que o pior caso do Bolha (Bubble Sort) pois faz menos trocas.
Revelar gabarito e comentário▾
GabaritoA — (N² − N)/2, sendo muito lento e inadequado para valores grandes de N.
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”.
##
Gabarito: letra A. O Selection Sort realiza exatamente (N² - N)/2 comparações, independentemente da ordenação inicial do vetor. Essa é a soma da progressão aritmética (N-1) + (N-2) + ... + 1 = N*(N-1)/2.
A questão cobra o conhecimento do número de comparações do Selection Sort. O algoritmo funciona percorrendo o vetor N-1 vezes: na primeira passada, compara o primeiro elemento com os N-1 restantes; na segunda, compara o segundo com os N-2 restantes; e assim sucessivamente até comparar o penúltimo com o último (1 comparação). A soma resulta na fórmula apresentada.
11ª passada: N-1 comparações
22ª passada: N-2 comparações
3… até 1 comparação
4Soma: (N-1)+(N-2)+…+1
5Fórmula: N·(N-1)/2 = (N²-N)/2
LEVEL · soulevel.com.br
Alternativa A — ✅ Correta ⟵ GABARITO
A fórmula (N² − N)/2 corresponde a N*(N-1)/2, exatamente a soma das comparações. O Selection Sort é O(N²), sendo lento para N grandes.
Alternativa B — ❌ Incorreta
Afirma que no melhor caso o número de comparações é log₂(N²+N). O Selection Sort não tem otimização para melhor caso; o número de comparações é sempre (N²-N)/2, independente da ordenação dos dados. A complexidade logarítmica não se aplica.
Alternativa C — ❌ Incorreta
Apresenta (N² + N −1)/2 para o caso médio, mas o número real é (N² - N)/2. A diferença é sutil (N-1 vs N+?), mas a fórmula correta é a da alternativa A.
Alternativa D — ❌ Incorreta
Diz que quando o vetor já está ordenado o número de comparações é (N − 1). No Selection Sort, mesmo que o vetor esteja ordenado, o algoritmo ainda percorre todas as comparações para encontrar o menor elemento; não há detecção de ordenação. Portanto, as comparações continuam sendo (N² - N)/2. O que se reduz a zero são as trocas, não as comparações.
Alternativa E — ❌ Incorreta
Propõe (N² + N)/4 para o pior caso, mas o pior caso também é (N² - N)/2. Além disso, afirma que faz menos trocas que o Bubble Sort – na verdade, o Selection Sort faz exatamente N-1 trocas, enquanto o Bubble Sort pode fazer muitas mais quando o vetor está invertido, mas a comparação de quantidade de trocas é correta. O erro principal está no número de comparações, que é maior do que o informado.