Questão 5605672

• Banca: FGV
• Órgão: Banestes
• Ano: 2021
• Provas: FGV - 2021 - Banestes - Analista em Tecnologia da Informação - Desenvolvimento de Sistemas; FGV - 2021 - Banestes - Analista em Tecnologia da Informação - Segurança da Informação; FGV - 2021 - Banestes - Analista em Tecnologia da Informação - Suporte e Infraestrutura
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Algoritmos de Ordenação

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.

Gabarito: A

Comentários

• • Bubble sort é o algoritmo mais simples, mas o menos eficientes. Neste algoritmo cada elemento da posição i será comparado com o elemento da posição i + 1, ou seja, um elemento da posição 2 será comparado com o elemento da posição 3. Caso o elemento da posição 2 for maior que o da posição 3, eles trocam de lugar e assim sucessivamente. Por causa dessa forma de execução, o vetor terá que ser percorrido quantas vezes que for necessária, tornando o algoritmo ineficiente para listas muito grandes.

• [8, 6, 14, 12, 4, 16] Entendo a primeira execução do Bubble soort:

  1 - 8 comparou com 6 e mudou de posição com ele ( 6, 8...)

  2 - 8 comparou com 14 e permaneceu em seu lugar, pois o 14 é maior (6, 8, 14...)

  3 - agora o 14 começa sua saga e compara com 12, conquistando sua posição, pois 14 > 12, ficando momentaneamente assim (6, 8, 12, 14...),

  4 - o 14 continua doidão e vai comparar com o próximo, que é o 4 (adversário fraquinho, igual o flamengo...), e troca de lugar com ele, pois 14> 4. O 4, ficando parcialmente assim (6, 8, 4, 12, 14...)

  5 - agora o 14 torou milho seco, pois comparou com o 16 e perdeu. Ficando, após a primeira execução, dessa forma:

  [6, 8, 12, 4, 14, 16]

  A partir daí é só realizar o mesmo raciocínio: 6 compara com 8, que compara com 4....

  [6, 8, 4, 12, 14, 16]

  [6, 4, 8, 12, 14, 16]

  [4, 6, 8, 12, 14, 16]