Counting sort (C Sharp)

From LiteratePrograms

Other implementations: C | C# | Haskell | Java | Python, functional | Scala

Counting sort is a very simple sort that is efficient for lists that take on only a small number of values. A linear-time algorithm based on array indexing, it trades time for space.

For the purposes of this article, we'll assume the elements take on integer values, but the same ideas apply to any type. We begin by declaring an array that will hold a counter for each possible value that an element can take on:

<<CountingSort method>>=
/// <summary>Sorts array a where each element is between 0 and numValues-1.</summary>
static void Sort(int[] a, int numValues) {
    int[] counts = new int[numValues];
    perform sort
}

Next, we perform the sort. There are two phases to counting sort. In the first phase, count occurrences, we iterate through the list, counting the number of times we observe each element by incrementing the array value corresponding to each element:

<<count occurrences>>=
for(int i=0; i < a.Length; i++) {
    counts[a[i]]++;
}

Note the use of a[i] as an array index. This is what makes counting sort not a comparison sort. In the second phase, generate result, we iterate through the counts array, outputting the counted number of elements for each value:

<<generate result>>=
int outputPos = 0;
for (int i=0; i < numValues; i++) {
    for (int j=0; j < counts[i]; j++) {
        a[outputPos] = i;
        outputPos++;
    }
}

Although this is a doubly-nested loop, the way in which we set the counters guarantees that the inner loop is executed only a linear (O(n)) number of times. Putting together these two phases, the sort is now complete:

<<perform sort>>=
count occurrences
generate result

We test the implementation by generating a list of integers falling in a given range, sorting it, and verifying that the results match those of the .NET Framework's Array.Sort() method. The list size and range are specified on the command line.

<<CountingSort.cs>>=
using System;
using System.IO;
public class CountingSort {
    CountingSort method
    public static void Main(string[] args) {
        int listSize = int.Parse(args[0]);
        int numValues = int.Parse(args[1]);
        // Generate list of random values
        int[] a = new int[listSize];
        Random r = new Random();
        for(int i=0; i < a.Length; i++) {
            a[i] = r.Next(numValues);
        }
        // Copy list to new array
        int[] a2 = new int[listSize];
        Array.Copy(a, a2, listSize);
        // Sort the two arrays
        Sort(a, numValues);
        Array.Sort(a2);
        // Compare the two arrays
        for (int i=0; i < listSize; i++) {
            if (a[i] != a2[i]) {
                Console.WriteLine("Error: Results do not match.");
                return;
            }
        }
        Console.WriteLine("Sort successful");
    }
}

Download code