MO417 - Questão para a prova oral

Número:

Enunciado: Considere o algoritmo do quicksort ligeiramente modificado para sempre eleger o elemento aproximadamente do meio para ser o pivô. Isto é, PARTITION(A,p,r) elege o elemento A[⌈(r-p+1)/2⌉] como pivô. Desta forma, é correto afirmar que:

a) Quando e entrada A está em ordem decrescente o tempo de execução do quicksort é T(n)=Θ(nlgn), 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 fim de cada execução de PARTITION, 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)=Θ(nlgn), refletindo o melhor caso.

e) NDA

Ideia original de: Jacqueline Midlej do Espírito Santo