0
$\begingroup$

Counting sort is originally like below code.

for (int i = 0; i <= 5; i++) c[i] = 0;
for (int i = 1; i <= 8; i++) c[a[i]]++;
for (int i = 1; i <= 5; i++) c[i] = c[i] + c[i - 1];
for (int i = 8; i >= 1; i--) {
    b[c[a[i]]] = a[i];
    c[a[i]]--;
}

In the above, last for loop iterates from last index because of stability of counting sort.

But, I want to iterate from first index 1 as well as maintaining the stability of sorting.

I'm trying and thinking lots of time, I cannot do. How can I do?

$\endgroup$
  • 1
    $\begingroup$ Obviously, your question is valid without any motivation. But, still, why? You have a version of counting sort that works for you, but you want to make an arbitrary-looking change that breaks it, while somehow not breaking it. What's wrong with the original version? $\endgroup$ – David Richerby Jun 8 '18 at 17:25
  • $\begingroup$ @DavidRicherby I just curious about reverse order, just that. $\endgroup$ – molamola Jun 9 '18 at 0:11
0
$\begingroup$

Prior to the last loop, c[i] holds the index of last element of bucket i plus 1. It's why when you use c[i] to address items in bucket i you need to go back. But c[i-1] contains index of the first element of bucket i, so you can just use it... except that you need index for bucket 0 too.

So the simplest way is to modify third cycle making it to write initial index of bucket i to c[i]. It may be done f.e. with extra temporary (note that i in revised loop starts from 0):

sum = 0;
for (int i = 0; i <= 5; i++) 
{
    sum += c[i];  
    c[i] = sum - c[i];
}

Note that since indexes in b starts from 1, you need to pre-increment c[a[i]] in new version of last loop (if indexes in b should go from 0, do post-increment instead):

for (int i = 1; i <= 8; i++)
{
    c[a[i]]++;
    b[c[a[i]]] = a[i];
}
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.