MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-025

Enunciado: Dado o algoritmo de COUNTING-SORTING a seguir, que ordena o vetor A no vetor B:

COUNTING-SORTING (A,B,k) 
1  let C[0..k] be a new array
2  for i=0 to k
3   C[i]=0
4  for j=1 to A.length
5   C[A[j]]=C[A[j]]+1
6 //C[i] now contains the number of elements equal to i.
7   for i=1 to k
8    C[i]=C[i]+C[i-1]
9  // C[i] now contains the number of elements equal to i. 
10 for j=A.length downto 1 
11   B[C[A[j]]]=A[j]
12   C[A[j]]=C[A[j]]-1

O que acontece quando a linha 10 é substituída por: for j=1 to A.length

a. a complexidade aumenta
b. o algoritmo não é mais estável
c. o algoritmo não é mais correto
d. não produz nenhuma diferença
e. NDA

Ideia original de: Vladimir Jaime Rocca Layza