Sunday, December 13, 2009
This is the second in my series of algorithm posts in trying to become a better programmer. Counting sort is possibly my favorite of the sorting algorithms because it looks so complicated at first glance, but its actually very simple and graceful.
The principle behind counting sort is to store a count of each value that appears in the array and use that as a way to place the original value in the resulting array. It's generally used for fairly low numbered positive integer values, and the running time of the algorithm depends on both the number of elements, and the range of values within the array. For example, a simple array with the values (1, 6, 1000000000) will take a LONG time to be sorted, even though there are only three elements because at some point there will be a loop from 0 to 1000000000. Also note that the sort method requires a parameter k, which is the maximum value contained in the array.
If you don't understand the algorithm, it would probably be better to read the wikipedia article instead of trying to rely on my brief and badly written version.
Language Choice
I decided to do a version in Python because I've never really used the language much and I figured it was a good way to give it a try. My first impressions are pretty positive, and I love how it uses indenting as part of the language semantics.
My C Implementation:
My Python Implementation