MO417 - Questão para a prova oral

MO417 - Questão para a prova oral

Número: 2013-023

Enunciado: Considere o algoritmo do quicksort ligeiramente modificado para sempre eleger um elemento aproximadamente do meio para ser o pivô. Mais especificamente, no subproblema em A[p,...,r] o elemento A[⌈(r+p)/2⌉] é eleito pivô. Desta forma, é correto afirmar que:

a) Quando e entrada A está em ordem decrescente, o tempo de execução do quicksort é T(n)=Θ(n lg n), refletindo o pior caso.

b) Quando a entrada A está em ordem crescente, o tempo de execução do quicksort é T(n)=Θ(n), refletindo o melhor caso.

c) Quando a entrada A está em ordem crescente ou decrescente, no final de cada procedimento de partição, o pivô sempre começa e termina na mesma posição.

d) Quando a entrada A está em ordem crescente ou decrescente, o tempo de execução do quicksort é T(n)=Θ(n lg n), refletindo o melhor caso.

e) NDA

Ideia original de: Jacqueline Midlej do Espírito Santo