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