Questão de Algoritmos e Estrutura de Dados — Algoritmos — CESGRANRIO 2024
Algoritmos e Estrutura de Dados›Algoritmos
Código
cg022021
Banca
CESGRANRIO
Órgão
Caixa
Ano
2024
Nível
Médio
Cargo
Técnico Bancário Novo - Tecnologia da Informação - Rio Grande do Sul
A ordenação de dados é crucial na ciência da computação, permitindo busca eficiente e melhorando a performance de algoritmos. Além disso, facilita a visualização e a interpretação dos dados, preparando-os para operações futuras. Em interfaces de usuário, a ordenação melhora a usabilidade, pois organiza os dados de forma relevante para os usuários. Nesse contexto, considere que se quer ordenar um pequeno conjunto de dados que já está quase totalmente ordenado.O algoritmo de ordenação mais eficiente para essa tarefa é a(o)
Abusca binária
Bbusca sequencial
Cordenação por seleção
Dordenação por inserção
Emétodo da bolha
Revelar gabarito e comentário▾
GabaritoD — ordenação por inserção
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: Eficiência em dados quase ordenados
Gabarito: letra D (ordenação por inserção). Em um conjunto pequeno e quase totalmente ordenado, o algoritmo mais eficiente é a ordenação por inserção (Insertion Sort), que apresenta complexidade O(n) no melhor caso, quando os dados já estão parcialmente ordenados.
A questão testa o conhecimento do comportamento de diferentes algoritmos de ordenação em cenários específicos. Enquanto a ordenação por inserção percorre os dados inserindo cada elemento em sua posição correta com poucas trocas quando o conjunto está quase ordenado, outros algoritmos como seleção e bolha têm desempenho O(n²) mesmo nesse caso.
Veja a análise de cada alternativa:
Alternativa A — ❌ Incorreta
Busca binária é um algoritmo de busca, não de ordenação. Ela exige que os dados já estejam ordenados para funcionar, mas não realiza a ordenação em si.
Alternativa B — ❌ Incorreta
Busca sequencial também é um algoritmo de busca, percorre os dados linearmente para encontrar um elemento, sem capacidade de ordenar o conjunto.
Alternativa C — ❌ Incorreta
Ordenação por seleção (Selection Sort) tem complexidade O(n²) em todos os casos, mesmo quando os dados estão quase ordenados. A cada iteração, busca o menor elemento e o coloca na posição correta, realizando muitas comparações independentemente da ordenação inicial.
Alternativa D — ✅ Correta ⟵ GABARITO
Ordenação por inserção (Insertion Sort) é a mais eficiente para pequenos conjuntos quase ordenados. No melhor caso (dados já ordenados), faz apenas n-1 comparações e zero trocas, resultando em O(n). No pior caso (dados invertidos), é O(n²), mas para entradas quase ordenadas, seu desempenho é próximo do linear.
Alternativa E — ❌ Incorreta
Método da bolha (Bubble Sort) tem complexidade O(n²) no pior caso e, embora possa ser otimizado para parar quando não há trocas, ainda é menos eficiente que a inserção para dados quase ordenados, realizando mais comparações e trocas.
PEGA ESSA DICA!
Em questões sobre eficiência de algoritmos, lembre-se da tabela de complexidades:
Algoritmo
Melhor caso
Caso médio
Pior caso
Inserção
O(n)
O(n²)
O(n²)
Seleção
O(n²)
O(n²)
O(n²)
Bolha
O(n) (otimizado)
O(n²)
O(n²)
Para dados quase ordenados, a inserção é a melhor opção entre os tradicionais.