#
Counting Sort

/*************************************************************************** * 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.""); } } } }