Questão nº 36
Questão de Tecnologia da Informação · FGV BANESTES 2021 (nº 36)
Considere um processo de ordenação dos elementos do array `[16,8,6,14,12,4]` em ordem crescente. Supõe-se um algoritmo que percorra o array repetidamente até que esteja ordenado, sem utilização de memória auxiliar para os elementos do array (in place).
A lista a seguir mostra a disposição dos elementos no array após cada ciclo de iteração.
`[8, 6, 14, 12, 4, 16]`
`[6, 8, 12, 4, 14, 16]`
`[6, 8, 4, 12, 14, 16]`
`[6, 4, 8, 12, 14, 16]`
`[4, 6, 8, 12, 14, 16]`
Nesse caso, é correto concluir que foi utilizado o algoritmo:
- ABubble Sort; (alternativa correta)
- BInsertion Sort;
- CQuickSort;
- DSelection Sort;
- EShellsort.
Resposta comentada
Gabarito Alternativa A
O algoritmo de ordenação é um método para organizar os elementos de uma lista (como um array) em uma ordem específica, como crescente ou decrescente. O Bubble Sort funciona comparando e trocando elementos adjacentes repetidamente até que o maior (ou menor) elemento "flutue" para sua posição correta no final de cada passagem.
(A) Correta: O Bubble Sort é o algoritmo utilizado. A cada iteração (passagem), o maior elemento restante na parte não ordenada do array "borbulha" para sua posição correta no final.
[16,8,6,14,12,4]->[8,6,14,12,4,16](16 borbulhou para o final)[8,6,14,12,4,16]->[6,8,12,4,14,16](14 borbulhou para a penúltima posição)[6,8,12,4,14,16]->[6,8,4,12,14,16](12 borbulhou)[6,8,4,12,14,16]->[6,4,8,12,14,16](8 borbulhou)[6,4,8,12,14,16]->[4,6,8,12,14,16](6 borbulhou, array ordenado)
Essa sequência de passos é a característica exata do Bubble Sort.
(B) Incorreta: O Insertion Sort constrói a lista ordenada um elemento por vez, pegando um elemento da parte não ordenada e inserindo-o na posição correta da parte já ordenada. Os passos mostrados não seguem esse padrão de inserção.
(C) Incorreta: O QuickSort é um algoritmo de "dividir para conquistar" que seleciona um pivô e particiona o array em dois subarrays, um com elementos menores que o pivô e outro com maiores. Os movimentos dos elementos seriam muito mais "saltitantes" e não as trocas adjacentes observadas.
(D) Incorreta: O Selection Sort encontra o menor (ou maior) elemento da parte não ordenada do array e o troca com o elemento na primeira posição não ordenada. No primeiro passo, o menor elemento (4) deveria ir para a primeira posição, o que não acontece. (Armadilha: Pode ser tentador pensar que a cada passo um elemento é colocado na posição final, mas o Selection Sort coloca o menor no início da parte não ordenada, enquanto o Bubble Sort coloca o maior no final da parte não ordenada.)
(E) Incorreta: O Shellsort é uma versão aprimorada do Insertion Sort que compara elementos distantes, reduzindo gradualmente a distância entre as comparações. Seus passos seriam mais complexos e não as simples trocas adjacentes mostradas.
Fonte: FGV BANESTES 2021 Conhecimentos Comuns (Analista em Tecnologia da Informação) (Caderno Tipo 1). Reproduzida para fins de estudo.