MO417 - QUESTÃO PARA PROVA ORAL

Número:

Enunciado: Qual modificação devemos realizar no algoritmo PARTITION, para utilizá-lo como rotina auxiliar de um algoritmo que determina o i-ésimo menor elemento de um vetor em tempo linear no pior caso? Observação: pivô é um elemento do vetor ao redor do qual será feito o particionamento.

  PARTITION(A, p, r)

  1. x = A[r]       /* A[r] é o elemento pivô */

  2. i = p - 1

  3. for j = p to r - 1

  4.     if A[j] <= x

  5.         i = i + 1

  6.         exachange A[i] with A[j]

  7. exchange A[i + 1] with A[r]

  8. return i + 1

1. não modifica-se o PARTITION, pois sua modificação não garante uma boa divisão do vetor ao ser particionado;
2. modifica-se o PARTITION para que divida o vetor em 5 partições;
3. modifica-se o PARTITION criando uma rotina auxiliar que seleciona um elemento aleatório  como pivô e faz sua troca antes do particionamento real;
4. modifica-se o PARTITION para que receba como parâmetro de entrada o elemento pivô;
5. NDA.

Ideia original de: Laurindo de Sousa Britto Neto