MO417 - Questão para a prova oral

Número: 2009-043

Enunciado: Considere o seguinte algoritmo COUNTING SORT modificado, que recebe como parâmetros um vetor A a ser ordenado, que deve conter valores inteiros no intervalo de 1..k, e o próprio k:

COUNTING-SORT-Modificado (A, k) 
1. for i := 0 to k 
2.      do C[i] := 0 
3. for j := 1 to comprimento[A] 
4.      do C[A[j]] := C[A[j]] +1 
5. j := 1 
6. for i := 1 to k 
7.     for cont := 1 to C[i] 
8.            A[j] := i 
9.            j := j + 1 

Sobre este algoritmo é CORRETO afirmar:

1. É estável como o COUNTING-SORT original.
2. O vetor auxiliar C deve ter tamanho mínimo n.
3. Sua complexidade de tempo no pior caso é Θ(n²).
4. Ordena A corretamente no próprio vetor A, sem utilizar um vetor de SAÍDA auxiliar B.
5. NDA

Ideia original de: Renato Hirata