Counting Sort
Last semester I took a paper called Algorithms and Data Structures. On of the topics we covered was non-comparing sorts.
Most sorting algorithms are comparing sorts in that they put a sequence in order by comparing values to each other and putting lower ones before higher ones.
Non-comparing sorts allow us to sort a series of numbers without ever comparing them to each other. Counting sort is a well known non-comparing sort. There is a cost to non comparing sorts though, Counting sort only works when we know the range and minimum value of the data to be sorted*.
Say we want to sort this sequence of numbers and we're told that they are all less than 10 and greater than 0:
5, 7, 3, 2, 1, 3, 2, 4, 8, 5, 9, 2
1. We calculate the range of the sequence and create an array of that size with all values set to 0. Here the range is 9 (max - min + 1) so we create an array like this:
0 1 2 3 4 5 6 7 8 << Index
[0][0][0][0][0][0][0][0][0] << Value
2. We move through the sequence of numbers incrementing the corresponding cell in our new array. The first number is 5, so we subtract the minimum to calculate its relative location. 5 - 1 = 4. Now we increment the value at index four in our array like so:
0 1 2 3 4 5 6 7 8
[0][0][0][0][1][0][0][0][0]
We repeat this for the rest of our sequence. The finished array should look like this:
0 1 2 3 4 5 6 7 8
[1][3][2][1][2][0][1][1][1]
3. Almost there, now we just need to print out the result. Moving through our array we print out the index of each cell a number of times as denoted by the cells value.
Don't forget we need to add one to each value because the array indexes start at 0 but our data range starts at 1, this can be thought of as an offset.
1, 2, 2, 2, 3, 3, 4, 5, 5, 7, 8, 9
There you have the initial array sorted without ever comparing one value to another.
* You could calculate the maximum and minimum (and derive range) beforehand and then perform counting sort, and this is often done, but it requires comparing values.
