(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
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
no melhor, no médio e no pior caso. O Heap Sort satisfaz isso:
– No pior caso, ele faz extrações da heap.
– No melhor caso também permanece , 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 ) e não sofre degraus de desempenho.
– No pior caso, ele faz
– No melhor caso também permanece
Além disso, o Heap Sort é in-place (usa espaço adicional
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 .
– Ele trabalha comparando e “inserindo” cada elemento na posição certa, e quando há poucas inversões, cada inserção custa em média , resultando em tempo próximo de linear.
– No melhor caso (lista quase ou totalmente ordenada), sua complexidade chega a
– Ele trabalha comparando e “inserindo” cada elemento na posição certa, e quando há poucas inversões, cada inserção custa em média
Resposta
a) Heap Sort, pois garante
em todos os casos e varia pouco entre melhor, médio e pior.
b) Insertion Sort, pois é adaptativo e atinge cerca de quando a entrada já está quase ordenada.
b) Insertion Sort, pois é adaptativo e atinge cerca de