/****************************************************************************
* Author: Isai Damier
* Title: Radix Sort
* Project: geekviewpoint
* Package: algorithms
*
* Statement:
* Given a disordered list of integers, rearrange them in natural order.
*
* Sample Input: {18,5,100,3,1,19,6,0,7,4,2}
*
* Sample Output: {0,1,2,3,4,5,6,7,18,19,100}
*
* Time Complexity of Solution:
* Best Case O(k*n); Average Case O(k*n); Worst Case O(k*n),
* where k is the length of the longest number and n is the
* size of the input array.
*
* Note: if k is greater than log(n) then an n*log(n) algorithm would be a
* better fit. In reality we can always change the radix to make k
* less than log(n).
*
* Approach:
* radix sort, like counting sort and bucket sort, is an integer based
* algorithm (i.e. the values of the input array are assumed to be
* integers). Hence radix sort is among the fastest sorting algorithms
* around, in theory. The particular distinction for radix sort is that it
* creates a bucket for each cipher (i.e. digit); as such, similar to
* bucket sort, each bucket in radix sort must be a growable list that may
* admit different keys.
*
* For decimal values, the number of buckets is 10, as the decimal system
* has 10 numerals/cyphers (i.e. 0,1,2,3,4,5,6,7,8,9). Then the keys are
* continuously sorted by significant digits.
***************************************************************************/
public void radixsort(int[] input) {
final int RADIX = 10;
// declare and initialize bucket[]
List<Integer>[] bucket = new ArrayList[RADIX];
for (int i = 0; i < bucket.length; i++) {
bucket[i] = new ArrayList<Integer>();
}
// sort
boolean maxLength = false;
int tmp = -1, placement = 1;
while (!maxLength) {
maxLength = true;
// split input between lists
for (Integer i : input) {
tmp = i / placement;
bucket[tmp % RADIX].add(i);
if (maxLength && tmp > 0) {
maxLength = false;
}
}
// empty lists into input array
int a = 0;
for (int b = 0; b < RADIX; b++) {
for (Integer i : bucket[b]) {
input[a++] = i;
}
bucket[b].clear();
}
// move to next digit
placement *= RADIX;
}
}
import org.junit.Test;
import static org.junit.Assert.*;
public class SortingTest {
@Test
public void testRadixsort() {
System.out.println(""radixsort"");
int[] input = {18, 5, 100, 3, 1, 19, 6, 0, 7, 4, 2};
Sorting instance = new Sorting();
instance.radixsort(input);
for (int i = 1; i < input.length; i++) {
if (input[i - 1] > input[i]) {
fail(""radixsort method fails."");
}
}
}
}