MO417 - Questão para a prova oral

Número: 039

Enunciado:
Dado o pseudo-código do procedimento de partição do Quick Sort:

PARTITION(A, p, r)
1 x ← A[r]
2 i ← p - 1
3 for j ← p to r - 1
4     do if A[j] ≤ x
5         then i ← i + 1
6             trocar A[i] ↔ A[j]
7 trocar A[i + 1] ↔ A[r]
8 return i + 1

E o invariante do loop das linhas 3 a 6:

Seja k um índice qualquer do arranjo A e x o valor do elemento pivô,
1. Se p ≤ k ≤ i, então A[k] ≤ x.
2. Se i + 1 ≤ k ≤ j - 1, então A[k] > x.
3. Se k = r, então A[k] = x.

Os subarranjos A[p .. i] e A[i + 1 .. j - 1] separam respectivamente:

1. Os elementos ainda não testados; e os elementos maiores que o pivô.
2. Os elementos maiores que o pivô; e os elementos menores ou iguais ao pivô.
3. Os elementos menores ou iguais ao pivô; e os elementos maiores que o pivô.
4. Os elementos menores ou iguais ao pivô; e os elementos ainda não testados.
5. NDA

Autor(a): Milton Aparecido Soares Junior