Counting Sort issue in array

Question

I am making an algorithm for counting sort. In first step i have initialized the second array with 0. Secondly i counted the frequency of elements in second for loop. In third loop i am trying to sort the array. The third loop does not run in code blocks. Also it's not giving me right sorted result.Any issue with third loop. As it changes array to 1-1-2-0-2-2-0-1-1 rather it should be 0-0-0-1-1-1-1-2-2-2

printf("Hello world!\n");
unsigned m=3;
unsigned n=10;
unsigned x;
unsigned k;
unsigned data[10] = {0, 2, 1, 1, 0, 2, 2, 0, 1, 1};
unsigned *count;

count =(unsigned *)malloc(sizeof(unsigned)*m);
int y=sizeof(data);

for(int i=0;i<m;i++)
{
    count[i]=0;

}

for(int j=0;j<n;j++)
{
    x=data[j];
    count[x]++;
}

 for(k=n-1;k>=0;k--)
    {
             data[count[data[k]]-1]=data[k];
             count[data[k]]=count[data[k]]-1;
    }


for(int i=0;i<n;i++)
{
    printf("%d \n",data[i]);

}


return 0;
}

Make your example to be a minimal reproducible example.

ryyker
– ryyker

2019-03-28 19:15:17 +00:00
Commented Mar 28, 2019 at 19:15 — ryyker
– ryyker, Commented Mar 28, 2019 at 19:15

Weather Vane · Accepted Answer · 2019-03-28 19:18:23Z

1

In this line

for(k=n-1;k>=0;k--)

k is unsigned so k >= 0 is always true. When an unsigned integer would go below zero, its value "wraps".

Also, your sorting loop does not sort anything. It can't because there are no comparisons. You may like to review your algorithm.

edited Mar 28, 2019 at 19:18

answered Mar 28, 2019 at 19:15

Weather Vane

34.8k7 gold badges43 silver badges63 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

hassan Over a year ago

what about sort logic in third loop?

manveti Over a year ago

A counting sort doesn't have comparisons as such: values aren't compared to each other, they're used as indices into a counts array.

manveti · Accepted Answer · 2019-03-28 23:11:53Z

The problem (in addition to the loop condition error mentioned in another answer) is that this appears to be a combination of two incompatible counting sort approaches.

The "traverse the input array backwards, inserting each element into the appropriate place in the output array" approach requires a separate output array. Consider the simple case of sorting {2, 1}: if we copy the 1 into the appropriate slot in the same array, it becomes {1, 1}, which will end up being our final output. Instead, that 1 needs to be placed into the appropriate slot of a separate array so that we don't overwrite the 2.

Additionally, this approach requires us to make a second pass over the count array to change its semantic meaning from "count of elements with value n" to "index of first element with value > n". This is accomplished by adding the total so far to each element of count (so in your case, count would go from {3, 4, 3} to {3, 7, 10}). After this step, count[n] - 1 is the index in the output array at which the next n should be placed.

Given that you're sorting integers, a second (easier) approach is also possible: once you've finished your initial traversal of the input array, count holds all the information you need, so you can freely overwrite the input array. Just start at the beginning and insert count[0] 0s, count[1] 1s, etc. This approach doesn't require any postprocessing of count or any separate output array.

Collectives™ on Stack Overflow

Counting Sort issue in array

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related