Algoritmos e Estrutura de Dados · IDCAP · 2025 | Questão sqc-qg517177

Algoritmos e Estrutura de DadosAlgoritmos

Código: qg517177
Banca: IDCAP
Órgão: HEMOBA
Ano: 2025
Nível: Superior

Cargo: Analista Técnico - Área de Atuação: Análise de Sistemas

Uma empresa de logística precisa processar diariamente um arquivo de 100 GB contendo registros de entregas que precisam ser ordenados por data e hora para gerar um relatório consolidado. O servidor responsável pelo processamento possui apenas 8 GB de memória RAM disponível para a aplicação. A escolha do algoritmo de ordenação é crítica para que a tarefa seja executada eficientemente sem exceder a capacidade de memória. Considerando as restrições de memória, o algoritmo de ordenação adequado para esta situação é:

AO Heapsort, pois ele garante uma complexidade de tempo de pior caso de O(nlogn) e opera "in-place", modificando o próprio array sem necessitar de memória adicional significativa.
BO Bubble Sort, porque sua implementação é simples e, embora sua complexidade seja O(n2), seu consumo de memória é constante, O(1), o que o torna ideal para ambientes com memória restrita.
CO Quicksort, pois possui uma complexidade de tempo média de O(nlogn), sendo um dos algoritmos de ordenação internos mais rápidos na prática para conjuntos de dados de grande porte.
DO Insertion Sort, porque ele é eficiente para conjuntos de dados que já estão parcialmente ordenados e seu baixo overhead o torna mais rápido que algoritmos mais complexos para blocos de dados menores.
EO External Merge Sort, pois ele é projetado para lidar com volumes de dados maiores que a memória principal, dividindo o arquivo em blocos que cabem na memória, ordenando esses blocos individualmente e, em seguida, mesclando-os de volta em um único arquivo ordenado.

Revelar gabarito e comentário

GabaritoE — O External Merge Sort, pois ele é projetado para lidar com volumes de dados maiores que a memória principal, dividindo o arquivo em blocos que cabem na memória, ordenando esses blocos individualmente e, em seguida, mesclando-os de volta em um único arquivo ordenado.

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 e restrição de memória

Gabarito: letra E. O problema central é que o arquivo de 100 GB é muito maior que os 8 GB de RAM disponíveis. Algoritmos de ordenação interna (Heapsort, Bubblesort, Quicksort, Insertion Sort) assumem que todos os dados cabem na memória principal e, portanto, não conseguem processar o arquivo inteiro de uma só vez. O External Merge Sort foi projetado exatamente para essa situação: ele divide o arquivo grande em blocos que cabem em memória, ordena cada bloco individualmente (usando um algoritmo interno) e depois mescla os blocos ordenados em um único arquivo final.

A banca testa a compreensão de que a eficiência prática de um algoritmo depende não apenas da complexidade de tempo, mas também dos recursos disponíveis – aqui, a memória.

Alternativa A — ❌ Incorreta

O Heapsort é de fato in-place e tem complexidade O(n log n) no pior caso, mas exige que o array inteiro esteja na memória principal. Com 100 GB para 8 GB de RAM, isso é impossível. O algoritmo não consegue lidar com dados que não cabem inteiramente na memória.

Alternativa B — ❌ Incorreta

O Bubble Sort tem consumo de memória constante O(1), mas ainda precisa que todo o conjunto de dados esteja acessível na memória para ser percorrido e comparado. Além disso, sua complexidade O(n²) o torna proibitivo para 100 GB, mesmo que coubesse. A memória é o gargalo principal: o arquivo não cabe.

Alternativa C — ❌ Incorreta

O Quicksort é um dos algoritmos internos mais rápidos na prática para dados que cabem em memória (complexidade média O(n log n)), mas, assim como os demais, pressupõe que todo o vetor está carregado em RAM. Para 100 GB e 8 GB de RAM, ele falha por falta de memória.

Alternativa D — ❌ Incorreta

O Insertion Sort é eficiente para pequenos conjuntos ou dados quase ordenados, mas, novamente, requer que todos os elementos estejam na memória. Sequer seria viável para 100 GB, e sua complexidade O(n²) o torna inviável mesmo para blocos que coubessem.

Alternativa E — ✅ Correta ⟵ GABARITO

O External Merge Sort é a técnica clássica para ordenar dados que excedem a memória principal. Ele opera em duas fases:

Divisão e ordenação de blocos: o arquivo é lido em partes (runs) que cabem na RAM, cada parte é ordenada internamente (por exemplo, com Quicksort) e salva em um arquivo temporário.
Mesclagem (merge): os blocos ordenados são lidos simultaneamente e intercalados para gerar o arquivo final ordenado, usando buffers que cabem na memória.

Dessa forma, o algoritmo respeita o limite de 8 GB e consegue processar os 100 GB de forma eficiente.

NÃO CAIA NESSA!

A banca explora a confusão entre eficiência temporal (complexidade O(n log n)) e viabilidade prática (memória). Muitos candidatos escolhem Quicksort ou Heapsort por serem rápidos, esquecendo que o arquivo não cabe na RAM. A questão deixa explícita a restrição de memória – ela é o fator decisivo, não apenas o tempo de CPU.

Gabarito: letra E – External Merge Sort é a única alternativa que resolve o problema de ordenação externa com memória insuficiente.

Link permanente: /questoes/qg517177