CODEWITHSUNDEEP
c
hassan
hassan

Reputation: 13

Counting Sort issue in array

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;
}

Upvotes: 0

Views: 93

Answers (2)

manveti
manveti

Reputation: 1711

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.

Upvotes: 0

Weather Vane
Weather Vane

Reputation: 34585

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.

Upvotes: 1

Related Questions