MO417 - Questão para a prova oral

Número: 043

Enunciado:
Suponha o seguinte algoritmo COUNTING SORT modificado (que recebe como parâmetros: A é o vetor 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 

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

Autor(a): Renato Hirata