Counting Sort

The counting sort algorithm is a type of sort algorithm that can be used to sort collections of values whose range is known. By that, we mean that the algorithm is based on the assumption that we know all possible values of the sort key beforehand. That’s not as terrible as it sounds – it may be as simple as knowing that our sort key will be a byte value, and hence be limited to the range of numbers between 0 and 255, for example.

Unlike the insertion sort, the counting sort is not based on the comparison of one sort key against another. Instead, when we start to sort using this algorithm, we first create an index of all possible values of the key. If we are going to sort a collection of bytes for instance, we’d create an array with 256 positions. This index is used to store the number of items in the collection we are sorting, that is smaller than or equal to the given key.

All this looks hideously complicated when you put it down in words, but it’s really rather simple, Let’s assume we have the following array of bytes: {9, 8, 4, 6, 3, 2, 1, 0, 4}

We first create the index:

[ 0 ][ 1 ][ 2 ][ 3 ][ 4 ][ 5 ][ 6 ][ 7 ][ 8 ][ 9 ] … [255]
[ 0 ][ 0 ][ 0 ][ 0 ][ 0 ][ 0 ][ 0 ][ 0 ][ 0 ][ 0 ] … [ 0 ]

Next, we iterate through the input collection, and add 1 to the value of the key matching the value we get from the input array:

input[0] is 9, so:
[ 0 ][ 1 ][ 2 ][ 3 ][ 4 ][ 5 ][ 6 ][ 7 ][ 8 ][ 9 ] … [255]
[ 0 ][ 0 ][ 0 ][ 0 ][ 0 ][ 0 ][ 0 ][ 0 ][ 0 ][ 1 ] … [ 0 ]

input[1] is 8:
[ 0 ][ 1 ][ 2 ][ 3 ][ 4 ][ 5 ][ 6 ][ 7 ][ 8 ][ 9 ] … [255]
[ 0 ][ 0 ][ 0 ][ 0 ][ 0 ][ 0 ][ 0 ][ 0 ][ 1 ][ 1 ] … [ 0 ]

input[2] is 4:
[ 0 ][ 1 ][ 2 ][ 3 ][ 4 ][ 5 ][ 6 ][ 7 ][ 8 ][ 9 ] … [255]
[ 0 ][ 0 ][ 0 ][ 0 ][ 1 ][ 0 ][ 0 ][ 0 ][ 1 ][ 1 ] … [ 0 ]

.. and so on, until after input 8 we have …

input[8] is 4:
[ 0 ][ 1 ][ 2 ][ 3 ][ 4 ][ 5 ][ 6 ][ 7 ][ 8 ][ 9 ] … [255]
[ 1 ][ 1 ][ 1 ][ 1 ][ 2 ][ 0 ][ 1 ][ 0 ][ 1 ][ 1 ] … [ 0 ]

Right now this tells us what how many instances of each key we have in our input array. What we really want, though, is to have a count of how many elements are smaller than or equal to a given key, so what we do next is, starting from the SECOND element in our index, we add the number of items from the previous key:

index[1] = index[1] + index[0]
[ 0 ][ 1 ][ 2 ][ 3 ][ 4 ][ 5 ][ 6 ][ 7 ][ 8 ][ 9 ] … [255]
[ 1 ][ 2 ][ 1 ][ 1 ][ 2 ][ 0 ][ 1 ][ 0 ][ 1 ][ 1 ] … [ 0 ]

index[2] = index[2] + index[1]
[ 0 ][ 1 ][ 2 ][ 3 ][ 4 ][ 5 ][ 6 ][ 7 ][ 8 ][ 9 ] … [255]
[ 1 ][ 2 ][ 3 ][ 1 ][ 2 ][ 0 ][ 1 ][ 0 ][ 1 ][ 1 ] … [ 0 ]

index[3] = index[3] + index[2]
[ 0 ][ 1 ][ 2 ][ 3 ][ 4 ][ 5 ][ 6 ][ 7 ][ 8 ][ 9 ] … [255]
[ 1 ][ 2 ][ 3 ][ 4 ][ 2 ][ 0 ][ 1 ][ 0 ][ 1 ][ 1 ] … [ 0 ]

index[4] = index[4] + index[3]
[ 0 ][ 1 ][ 2 ][ 3 ][ 4 ][ 5 ][ 6 ][ 7 ][ 8 ][ 9 ] … [255]
[ 1 ][ 2 ][ 3 ][ 4 ][ 6 ][ 0 ][ 1 ][ 0 ][ 1 ][ 1 ] … [ 0 ]

… until, a long time later …

index[255] = index[255] + index[254]
[ 0 ][ 1 ][ 2 ][ 3 ][ 4 ][ 5 ][ 6 ][ 7 ][ 8 ][ 9 ] … [255]
[ 1 ][ 2 ][ 3 ][ 4 ][ 6 ][ 6 ][ 7 ][ 7 ][ 8 ][ 9 ] … [ 9 ]

Which tells us that in the array there are 7 values less than or equal to 7, 6 values less than or equal to 4, and so on. We can use this information to create our output array, and reserve space for our keys. If we know that there are 3 values that are less than or equal to 2, for example, we know that, if we place, say, 3 in our output array, we must leave space for those 3 values.

Now we can iterate through our input array backwards, and use the index to see where it fits in the output array. Every time we do this, we subtract 1 from its count in the index array – we’ve already handled one instance of this key, so that’s one less to worry about.

Now, the bit about iterating backwards can sound a bit weird – why backwards? Well, to make sure we have enough space, counting sort drops the value into the output array at the last available space reserved for it. If we were to iterate forward, the first instance of the key would be placed *after* the last instance of the same key. Consider the following scenario:

Input collection {{Name=”Bob”, Age=”10″}, {Name=”Emilyn”,Age=”3″}, {Name=”Tim”,Age=”10″}}

If we sort by age and iterate forward, we get back {{Name=”Emilyn”,Age=”3″}, {Name=”Tim”,Age=”10″}, {Name=”Bob”, Age=”10″}}
If instead we iterate backwards, we get {{Name=”Emilyn”,Age=”3″}, {Name=”Bob”,Age=”10″}, {Name=”Tim”, Age=”10″}}

Since some uses of counting sort assume that items with equal key values will be returned in the same order as they were given in, we should play nice and satisfy that assumption. When a sort algorithm behaves in this way (equal value items returned in same order as given), that algorithm is said to be stable.

As we said, every time we drop a value in its place inside the output collection, we decrease the value of its count in the index by 1. This way, the next time we encounter the same value, the index will be pointing to it’s new home in the output collection, just next to its friend.

Now all that may look terribly wordy – and it is – but the code itself is pretty nice and sweet:

   1: public byte[] Sort(byte[] input)
   2: {
   3:     int[] index = new int[byte.MaxValue + 1];
   4:
   5:     for (int j = 0; j < input.Length; j++)
   6:      index[input[j]]++;
   7:
   8:     for (int i = 1; i < index.Length; i++)
   9:      index[i] = index[i] + index[i - 1];
  10:
  11:     byte[] output = new byte[input.Length];
  12:
  13:     for (int i = input.Length - 1; i >= 0; i--)
  14:     {
  15:      output[index[input[i]] -1] = input[i];
  16:      index[input[i]]--;
  17:     }
  18:
  19:     return output;
  20: }

As you can see, unlike comparison sort, this algorithm will always iterate through the input array twice, and will always iterate the index once – for a given size of input array, we will always have the same number of operations being performed. This means that, barring external factors, a search on an array of a given size will always take roughly the same amount of time.

We can also see that we’re creating two arrays here. This method will be consuming 256 bytes, plus the size of the input array in bytes when it creates the output array. This also means that we can know how much memory the method will consume beforehand, if we need to know that.

kick it on DotNetKicks.com

About these ads

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: