Counting sort (Java)

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>>=
/** Sorts array a where each element is between 0 and numValues-1. */
public static void sort(int[] a) {
    find range
    int[] counts = new int[numValues];
    perform sort
}

To find the range of numbers, we traverse the array to find the minimum and maximum. If you already know the range, then you can skip this step and pass it into the function directly.

<<find range>>=
if (a.length == 0)
  return;
int max = a[0], min = a[0];
for (int i = 1; i < a.length; i++) {
    if (a[i] > max)
        max = a[i];
    else if (a[i] < min)
        min = a[i];
}
int numValues = max - min + 1;

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]-min]++;
}

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+min;
        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 Java's [) Arrays.sort()] method. The list size and range are specified on the command line.

<<CountingSort.java>>=
import java.util.Arrays;
import java.util.Random;
public class CountingSort {
    CountingSort method
    public static void main(String[] args) {
        int listSize = Integer.parseInt(args[0]);
        int numValues = Integer.parseInt(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.nextInt(numValues);
        }
        // Copy list to new array
        int[] a2 = new int[listSize];
        System.arraycopy(a, 0, a2, 0, listSize);
        // Sort the two arrays
        sort(a);
        Arrays.sort(a2);
        // Compare the two arrays
        for (int i = 0; i < listSize; i++) {
            if (a[i] != a2[i]) {
                System.out.println("Error: Results do not match.");
                return;
            }
        }
        System.out.println("Sort successful");
    }
}

Download code