Cesgranrio 2024 · Informática

Question

Considere as seguintes características, encontradas em alguns algoritmos de ordenação: I - É estável, ou seja, não altera a ordem relativa dos elementos que possuem o mesmo valor de chave de ordenação. II - Percorre repetidamente a lista a ser ordenada, comparando o elemento corrente com o seguinte e, se necessário, trocando os seus valores. III - Divide a lista a ser ordenada em duas partes: uma sublista ordenada de elementos, que é construída da esquerda para a direita (ordem crescente), à frente de uma sublista referente aos elementos não ordenados, sendo que, inicialmente, a primeira lista é vazia, enquanto a segunda contém todos os elementos a serem ordenados. Essas características se aplicam, respectivamente, aos seguintes métodos de ordenação:

A) por inserção, da bolha e por seleção
B) por inserção, por seleção e da bolha
C) por seleção, da bolha e por inserção
D) por seleção, por inserção e da bolha
E) da bolha, por seleção e por inserção

Accepted Answer

Gabarito oficial: A. # Comentário da Questão

A questão exige conhecimento sobre as características fundamentais dos três principais algoritmos de ordenação simples. A chave está em associar corretamente cada descrição ao seu algoritmo.

## Por que A está correta

A característica I (estabilidade) é exclusiva do **insertion sort**. Este algoritmo preserva a ordem relativa de elementos com chaves iguais porque insere cada novo elemento em sua posição correta sem deslocar desnecessariamente os demais. A característica II (comparação repetida com o próximo elemento e troca) descreve perfeitamente o **bubble sort**, que faz múltiplas passagens comparando pares adjacentes e "borbulhando" o maior elemento para o final a cada iteração. A característica III (partição em sublista ordenada à esquerda e não-ordenada à direita) é o conceito-chave do **selection sort**, que constrói incrementalmente uma região ordenada pegando sempre o menor elemento da região não-ordenada.

## Erro das demais alternativas

B inverte bubble e selection nas posições II e III, invertendo também o algoritmo responsável pela estabilidade — selection sort não é estável pois realiza trocas de posições que podem alterar a ordem relativa de elementos iguais. C coloca selection na posição I, o que é incorreto: selection sort não é estável. D também erra na primeira posição com selection sort. E começa com bubble sort na posição I, quando na verdade bubble sort é apenas estável em sua implementação clássica, mas essa não é sua característica distintiva — insertion sort é mais notoriamente estável.

**Decorar: Insertion é estável e constrói lista ordenada incrementalmente; Bubble compara vizinhos repetidamente; Selection escolhe o mínimo.**

Informática — Cesgranrio 2024

Mais questões de Informática

Fonte