Questão de Algoritmos e Estrutura de Dados — Algoritmos — CESGRANRIO 2021
Algoritmos e Estrutura de Dados›Algoritmos
Código
cg016178
Banca
CESGRANRIO
Órgão
Banco da Amazônia
Ano
2021
Nível
Superior
Cargo
Técnico Científico
Um determinado programador é responsável por tarefas de ordenação e, ao estudar determinados produtos, resolveu ordenar, de maneira crescente, a sequência [64, 34, 25, 12, 90, 11, 22] utilizando dois algoritmos, o Bubble Sort e o Select Sort, nessa ordem.Ele iniciou o teste com o Bubble Sort, mas, na iteração em que a chave 64 atingiu a sua posição correta pela primeira vez, copiou a sequência alcançada nesse estágio e utilizou-a para continuar o trabalho com o algoritmo Select Sort.A partir do momento em que o programador começa a utilizar o segundo algoritmo, quantas trocas de posições de chaves serão realizadas para atingir, pela primeira vez, a situação em que a sequência está ordenada?
A1
B2
C3
D4
E5
Revelar gabarito e comentário▾
GabaritoB — 2
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: Bubble Sort e Selection Sort
Gabarito: letra B. Após o Bubble Sort deslocar o 64 para sua posição correta (sexta posição), a sequência resultante é [25,12,34,11,22,64,90]. Aplicando o Selection Sort a partir desse ponto, são realizadas exatamente 2 trocas até que a sequência fique completamente ordenada: [11,12,22,25,34,64,90].
A questão testa a capacidade de simular passo a passo os algoritmos e identificar o momento de transição entre eles. O Bubble Sort é executado até que o 64 atinja sua posição final pela primeira vez; a partir daí, o Selection Sort é aplicado na sequência obtida.
Simulação detalhada
1. Bubble Sort até o 64 na posição correta
Sequência inicial: [64,34,25,12,90,11,22]
Passagem 1: percorre todo o array, trocando adjacentes quando necessário. Resultado: [34,25,12,64,11,22,90] (o 64 está no índice 3).
Passagem 2: percorre novamente. Resultado: [25,12,34,11,22,64,90] (o 64 agora está no índice 5 – sua posição final na ordenação crescente).
A sequência copiada para o Selection Sort é: 25,12,34,11,22,64,90.
2. Selection Sort a partir da sequência copiada
Selection Sort: para cada posição i (0 a 5), encontra o menor elemento no subarray [i..6] e troca com a posição i.
i
Subarray (índices i..6)
Menor elemento (índice)
Troca?
Sequência após troca
0
[25,12,34,11,22,64,90]
11 (índice 3)
Sim (troca 25↔11)
[11,12,34,25,22,64,90]
1
[12,34,25,22,64,90]
12 (índice 1)
Não (já está)
[11,12,34,25,22,64,90]
2
[34,25,22,64,90]
22 (índice 4)
Sim (troca 34↔22)
[11,12,22,25,34,64,90]
3
[25,34,64,90]
25 (índice 3)
Não
[11,12,22,25,34,64,90]
4
[34,64,90]
34 (índice 4)
Não
[11,12,22,25,34,64,90]
5
[64,90]
64 (índice 5)
Não
[11,12,22,25,34,64,90]
Total de trocas: 2 (nas iterações i=0 e i=2).
1i=0: 25↔111ª troca
2i=1: 12 já estásem troca
3i=2: 34↔222ª troca
4i=3: 25 já estásem troca
5i=4: 34 já estásem troca
6i=5: 64 já estásem troca
LEVEL · soulevel.com.br
NÃO CAIA NESSA!
É comum o candidato contar as trocas do Bubble Sort também, mas a questão é clara: "A partir do momento em que o programador começa a utilizar o segundo algoritmo, quantas trocas... serão realizadas?". Foco exclusivo no Selection Sort.