No replies to this topic

[pigimoth]

Hi there, I have some problem solving a pretty simple question and could use some help. We are given the count sort algorithm:

init C[k]
for i=1 to n
C[A[i]]++
for j=2 to k
C[j] = C[j] + C[j-1]
for j=n down to 1
B[C[A[j]]] = A[j]
C[A[j]]--

when A is the array to sort, B is the new sorted array and C is the temporary array in which we store the counts of each number and then how many numbers are lower than the i slot in C.

Now the question is: if we change last loop to run from 1 to n, the sort becomes unstable, fix the algorithm to be stable without changing the B[C[A[j]]] = A[j] line.

Any help will be much appreciated.