MO417 - Questão para a prova oral

Número:

Enunciado: Para o quicksort, considere a seguinte escolha do pivô:

  1  i = random (p,r)       // p = primeiro elemento, r = último elemento
  2  para j = i+1 até r
  3       se A[i] = A[j]
  4            i = j
  5  troque A[i] com A[r]

Qual das seguintes afirmações sobre a implementação é correta?

a. ela aumenta a ordem de grandeza do melhor caso
b. ela aumenta a ordem de grandeza do pior caso
c. ela torna o quicksort-randomizado estável
d. ela dificulta a ocorrência do pior caso
e. NDA

Idéia original de: Jorge Augusto Hongo