(Questão 03-03 pontos)

Qual algoritmo de ordenação você usaria para cada um dos seguintes casos, justifique brevemente:
a) O tempo de execução não deve apresentar grandes variações para nenhum caso.
b) A lista a ser ordenada já está bem próxima da ordem final

Passo 1

O enunciado pede que a gente escolha um algoritmo de ordenação distinto para dois cenários bem específicos, justificando por que cada escolha é adequada. O conteúdo envolve análise de complexidades de tempo nos melhores, piores e casos médios, além de adaptividade a dados quase ordenados.

Passo 2

Para o caso (a) “o tempo de execução não deve apresentar grandes variações para nenhum caso”, queremos um algoritmo cujo tempo seja uniformemente Theta(nlog n) no melhor, no médio e no pior caso. O Heap Sort satisfaz isso:
– No pior caso, ele faz Theta(nlog n) extrações da heap.
– No melhor caso também permanece Theta(nlog n), pois mesmo que os dados já estejam quase ordenados, ainda precisamos construir a heap e extrair elementos.
Além disso, o Heap Sort é in-place (usa espaço adicional O(1)) e não sofre degraus de desempenho.

Passo 3

Para o caso (b) “a lista já está bem próxima da ordem final”, vale usar um método adaptativo, que aproveita sequências já ordenadas para acelerar o processo. O Insertion Sort é ideal aqui porque:
– No melhor caso (lista quase ou totalmente ordenada), sua complexidade chega a Theta(n).
– Ele trabalha comparando e “inserindo” cada elemento na posição certa, e quando há poucas inversões, cada inserção custa em média O(1), resultando em tempo próximo de linear.

Resposta

a) Heap Sort, pois garante Theta(nlog n) em todos os casos e varia pouco entre melhor, médio e pior.
b) Insertion Sort, pois é adaptativo e atinge cerca de Theta(n) quando a entrada já está quase ordenada.

Exercícios relacionados