We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
the general idea for counting sort is that we make a histogram of which numbers occur how many times. We know the range in which the numbers will lie in, so we create an array accordingly. The wikipedia explanation and algorithm might help you understand better.
Yeah. Same problem. How have they counted the numbers? A number that comes 4 times in the list is written 0 at first then 1 or even 4 somewhere.. What's actually going on?
If the range of number in a array is between [0,9], then we can create a count array of size 10, where i'th elements can store the number of times integer i occured in the original array. Lets say we have a array: {7, 2, 7, 1, 5} Then our count will have element count[1] = 1, count [2] = 1, count[5] = 1, count[7] = 2 and other elements of count will be zero. Hope that this will help.
Counting Sort 1
You are viewing a single comment's thread. Return to all comments →
In this problem how they have counted the numbers, i dont understand. Could any1 please explain it to me.
the general idea for counting sort is that we make a histogram of which numbers occur how many times. We know the range in which the numbers will lie in, so we create an array accordingly. The wikipedia explanation and algorithm might help you understand better.
Yeah. Same problem. How have they counted the numbers? A number that comes 4 times in the list is written 0 at first then 1 or even 4 somewhere.. What's actually going on?
If the range of number in a array is between [0,9], then we can create a count array of size 10, where i'th elements can store the number of times integer
ioccured in the original array. Lets say we have a array:{7, 2, 7, 1, 5}Then ourcountwill have elementcount[1] = 1, count [2] = 1, count[5] = 1, count[7] = 2and other elements of count will be zero. Hope that this will help.Yeah. Got it. Solved. Thanks
Isn't the example given wrong? It has 63 zero times and 25 2 times! Actually 63 appears one time and 25 appears 3 times...
No amalfra, I have cross checked sample cases again. It is right.