Alternativa B - Algoritmos de ordenação interna podem exigir O(n) de espaço adicional, como no Merge Sort, ou O(1), quando implementados in-place, como no Bubble Sort, Insertion Sort e Selection Sort.
Análise da Questão
Esta questão aborda dois conceitos fundamentais em Estrutura de Dados: a diferença entre ordenação interna e externa, além da complexidade de espaço (auxiliar) necessária para cada algoritmo.
1. Ordenação Interna vs. Externa
A questão define corretamente que estamos falando de ordenção interna.
- Ordenação Interna: Os dados cabem inteiramente na memória RAM durante o processo. É o cenário padrão para vetores e arrays pequenos/médios.
- Ordenação Externa: Usada quando os dados são muito grandes para caber na memória, exigindo armazenamento secundário (disco rígido).
2. Complexidade de Espaço Auxiliária
A complexidade de espaço refere-se à quantidade de memória extra que o algoritmo precisa para funcionar, além do espaço ocupado pelos próprios dados a serem ordenados. Existem duas categorias principais:
- In-Place (O(1)): O algoritmo reorganiza os elementos dentro do próprio array original, usando apenas variáveis temporárias constantes (como índices ou trocas simples).
- Exemplos citados: Bubble Sort, Insertion Sort, Selection Sort e Heap Sort.
- Por que O(1)? Eles não criam novos arrays grandes; apenas manipulam posições existentes.
- Não In-Place / Auxiliares (O(n)): Alguns algoritmos precisam de um buffer ou array auxiliar para realizar a ordenação de forma eficiente.
- Exemplo citado: Merge Sort.
- Por que O(n)? Para fundir (merge) duas metades ordenadas, ele precisa copiar os dados para um array temporário do mesmo tamanho do original antes de voltar a colocá-los no lugar certo.
Tabela Comparativa de Espaço
| Algoritmo | Tipo de Implementação | Complexidade de Espaço |
|---|
| Bubble Sort | In-Place | O(1) |
| Insertion Sort | In-Place | O(1) |
| Selection Sort | In-Place | O(1) |
| Merge Sort | Não In-Place (clássico) | O(n) |
| Quick Sort | In-Place (recursivo) | O(\log n) (pilha de chamadas) |
Por que as outras alternativas estão erradas?
- A e C: Estão incorretas ao afirmar que todos os algoritmos exigem O(n^2) ou O(n \log n). A maioria dos algoritmos clássicos usa pouco espaço (O(1) ou O(\log n)).
- D: Afirma que nunca é possível usar O(1), o que é falso dado que existem diversos algoritmos in-place.
- E: A complexidade O(n^3) é extremamente alta para espaço e não se aplica à realidade dos algoritmos de ordenação padrão.
Portanto, a alternativa B é a única que descreve corretamente a diversidade de requisitos de memória encontrados nos algoritmos de ordenação interna.