Questão 36 · Informática: Programação e algoritmos
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:
- A) Bubble Sort;
- B) Insertion Sort;
- C) QuickSort;
- D) Selection Sort;
- E) Shellsort.
Marque a alternativa correta:
Gabarito: A
Gabarito definitivo divulgado pela banca FGV (BANESTES 2021).
Comentário
Gabarito: A.
O algoritmo percorre o array repetidamente trocando vizinhos fora de ordem, e as listas mostram o estado após cada passagem. Na primeira, o 16 é comparado com o 8, o 6, o 14, o 12 e o 4 e vai sendo empurrado para o fim: [8, 6, 14, 12, 4, 16]. Na segunda, o 8 troca com o 6, o 14 troca com o 12 e o 14 troca com o 4: [6, 8, 12, 4, 14, 16]. A cada passagem o maior elemento restante sobe até sua posição final e os demais só se movem por trocas entre vizinhos, comportamento do Bubble Sort.
- (B) o Insertion Sort mantém a parte inicial ordenada; após o primeiro ciclo, porém, o início [8, 6, 14, 12, 4] não está ordenado.
- (C) o QuickSort particiona o array em torno de um pivô, o que em geral move elementos a longas distâncias; aqui só há trocas entre vizinhos.
- (D) o Selection Sort coloca o menor elemento na primeira posição já no primeiro ciclo; isso levaria o 4 ao início, mas ele ficou na quinta posição.
- (E) o Shellsort começa comparando e trocando elementos separados por um intervalo maior que 1; aqui todas as trocas são entre vizinhos.
Dica: observe como o maior elemento se desloca em cada ciclo: no Bubble Sort, ele vai para o fim a cada passagem, por trocas de elementos adjacentes.
Fundamentos: Bubble Sort e trocas de vizinhos · ordenação in place · comparação entre algoritmos de ordenação
Comentário gerado pela Cravei IA a partir do enunciado e do gabarito definitivo divulgado pela banca, e conferido por uma verificação automática. A IA pode errar: o gabarito oficial sempre prevalece.
Fonte: prova FGV BANESTES 2021 (Desenvolvimento de Sistemas), questão 36, com o gabarito definitivo da banca. Comentário: Equipe Cravei · como fazemos e revisamos.