MO417 - Questão para a prova oral

Número: 031

Enunciado: Considere o algoritmo QUICKSORT e uma variação deste na qual a cada chamada da função de particionamento, a mediana do vetor a ser particionado é encontrada em tempo linear e usada como pivô. Dadas as seguintes afirmações, assinale a alternativa correta:

1. A quantidade total de memória (incluindo o vetor) utilizada pelo QUICKSORT modificado seria &Omega(n lg n).
2. Dentro do modelo de ordenação por comparação, a modificação do QUICKSORT não produz um algoritmo assintoticamente ótimo.
3. Dentro do modelo de ordenação por comparação, o QUICKSORT original é assintoticamente ótimo.
4. O tempo de execução no pior caso do QUICKSORT modificado é Θ(n log n).
5. NDA.

Autor(a): Carlos Eduardo Seo