Gabarito disponível
Assinale a opção que completa corretamente as lacunas das sentenças abaixo.
Considerando um arranjo de entrada de n números, o ______________ é um algoritmo de ordenação cujo tempo de execução do pior caso é ______. Apesar desse tempo de execução lento no pior caso, o algoritmo, com frequência, é a melhor opção prática para ordenação, devido a sua notável eficiência na média, em que seu tempo de execução esperado é _________.
Considerando um arranjo de entrada de n números, o ______________ é um algoritmo de ordenação cujo tempo de execução do pior caso é ______. Apesar desse tempo de execução lento no pior caso, o algoritmo, com frequência, é a melhor opção prática para ordenação, devido a sua notável eficiência na média, em que seu tempo de execução esperado é _________.
Resolução comentada
Quicksort: pior caso Θ(n²) e caso médio esperado Θ(n lg n).
O Quicksort tem pior caso Θ(n²), mas na média seu tempo esperado é Θ(n lg n), com constantes pequenas e ordenação in-place. Por isso costuma ser a melhor opção prática.
Análise das alternativas
Heapsort é Θ(n lg n) no pior caso. Bellman-Ford é um algoritmo de caminhos mínimos em grafos, não de ordenação. Os tempos Θ(n), Θ(lg n) e Θ(1) são impossíveis para ordenação por comparação.
Referência: Cormen et al. – Algoritmos: Teoria e Prática, cap. Quicksort.
Resolução comentada do VaiConcursos.