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.
Good question. Technically you may be right, but I think whether I can call it counting sort is open to debate. Here is my original version of counting sort that more closely follows the pseudocode on wikipedia in case you were wondering how it would be done in Java. However, I like my new version better.
In my new version, I still attempt to create a histogram, but instead of using an array, I use a HashMap. I believe it's easier to picture a histogram using this HashMap. I still like to label my algorithm as counting sort since it uses a histogram.
You are right, my algorithm technically does not do a prefix sum, and maybe should not be called counting sort since I don't calculate a prefix sum. The point of doing a prefix sum is just to figure out where to place the original elements into our final sorted array. When using a HashMap, getting this information is actually a little easier though and can be done while looping through the HashMap as I do in my code when I "print output".
The Full Counting Sort
You are viewing a single comment's thread. Return to all comments →
Good question. Technically you may be right, but I think whether I can call it counting sort is open to debate. Here is my original version of counting sort that more closely follows the pseudocode on wikipedia in case you were wondering how it would be done in Java. However, I like my new version better.
In my new version, I still attempt to create a histogram, but instead of using an array, I use a HashMap. I believe it's easier to picture a histogram using this HashMap. I still like to label my algorithm as counting sort since it uses a histogram.
You are right, my algorithm technically does not do a prefix sum, and maybe should not be called counting sort since I don't calculate a prefix sum. The point of doing a prefix sum is just to figure out where to place the original elements into our final sorted array. When using a HashMap, getting this information is actually a little easier though and can be done while looping through the HashMap as I do in my code when I "print output".
HackerRank solutions.