Counting Sort
by Isai Damier

/***************************************************************************
 * Author: Isai Damier
 * Title: Countingsort
 * Project: GeekViewpoint
 * Package: algorithms
 *
 * Statement:
 *   Given a disordered list of repeated integers, rearrange the integers
 *   in natural order.
 *
 * Sample Input: {4,3,2,1,4,3,2,4,3,4}
 *
 * Sample Output: {1,2,2,3,3,3,4,4,4,4}
 *
 * Time Complexity of Solution:
 *   Best Case O(n+k); Average Case O(n+k); Worst Case O(n+k),
 *   where n is the size of the input array and k means the
 *   values range from 0 to k.
 *
 * Approach:
 *   Counting sort, like radix sort and bucket sort,
 *   is an integer based algorithm (i.e. the values of the input
 *   array are assumed to be integers). Hence counting sort is
 *   among the fastest sorting algorithms around, in theory. The
 *   particular distinction for counting sort is that it creates
 *   a bucket for each value and keep a counter in each bucket.
 *   Then each time a value is encountered in the input collection,
 *   the appropriate counter is incremented. Because counting sort
 *   creates a bucket for each value, an imposing restriction is
 *   that the maximum value in the input array be known beforehand.
 *
 *   There is a great number of counting sort code on the Internet,
 *   including on university websites, that erroneously claim to be
 *   bucket sort. Bucket sort uses a hash function to distribute
 *   values; counting sort, on the other hand, creates a counter for
 *   each value -- hence the name.
 *
 * Implementation notes:
 *
 * 1] Since the values range from 0 to k, create k+1  buckets.
 * 2] To fill the buckets, iterate through the input array and
 *    each time a value appears, increment the counter in its
 *    bucket.
 * 3] Now fill the input array with the compressed data in the
 *    buckets. Each bucket's key represents a value in the
 *    array. So for each bucket, from smallest key to largest,
 *    add the index of the bucket to the input array and
 *    decrease the counter in said bucket by one; until the
 *    counter is zero.
**************************************************************************/ 
 public void countingsort(int[] input, int k) {
    // create buckets
    int counter[] = new int[k + 1];
    // fill buckets
    for (int i : input) {
      counter[i]++;
    }
    // sort array
    int ndx = 0;
    for (int i = 0; i < counter.length; i++) {
      while (0 < counter[i]) {
        input[ndx++] = i;
        counter[i]--;
      }
    }
  }
import org.junit.Test;
import static org.junit.Assert.*;

public class SortingTest {
  
  
  /**
   * Test of countingsort method, of class Sorting.
   */
  @Test
  public void testCountingsort() {
    System.out.println(""countingsort"");
    int[] input = {6, 4, 3, 2, 1, 4, 3, 6, 6, 2, 4, 3, 4};
    int k = 6;
    Sorting instance = new Sorting();
    instance.countingsort(input, k);
    for (int i = 1; i < input.length; i++) {
      if (input[i - 1] > input[i]) {
        fail(""countingsort method fails."");
      }
    }
  }
}
Phuzz! Turn your photo into a puzzle!