CC-7 : Implement Radix Sort Algorithm.

Description:

Radix Sort works by sorting numbers by processing individual digits of the input numbers. It calls a modified Counting Sort algorithm to sort digits at same level across numbers. First, we find the maximum integer in the input array called maxInt and maximum number of digits k in maxInt. Now we perform k iteration on each number in the input array. For first iteration using modified Counting Sort, we will sort digit at unit’s position of each number in input array. Then using this array with sorted units digit as base, we will sort digits at 10s position and so on till we have done k passes. At end of k passes the input array will be sorted. Given an input array, sort its elements using Radix Sort.

Test cases and expected outputs:

Input Parameters	Expected outputs
Array: 33, 3, 4, 97, 62, 122, 124, 20, 1,	Sorted Array: 1, 3, 4, 20, 33, 62, 97, 122, 124,

Pseudocode:

RadixSort(nums[]):

Integer array named nums is received as input parameter.

Using a for loop find the maximum integer in nums and store it a variable named maxInt.

Using a for loop and exp as loop variable with initial value 1 execute following steps while maxInt/exp > 0 and increment exp to exp*10 at each iteration and execute following steps:

Call countingSort(nums,exp).

The elements of nums array have been sorted now using Radix Sort, so return nums array from the method.

CountingSort(nums, exp):

Initialize an int array named sorted with length nums.length.

Initialize an int array count with size 10 (as current radix is 10).

Iterate through count using for loop with idx as iteration variable and values of idx ranging from 0 to count.length-1:

Set count[idx]=0.

Iterate through nums using for loop with idx as iteration variable and values of idx ranging from 0 to nums.length-1:

Increment count[nums[idx]/exp%10] by 1.

Iterate through count using for loop with idx as iteration variable and values of idx ranging from 1 to count.length-1:

Increment count[idx] by count[idx-1].

Iterate through nums using for loop with idx as iteration variable and values of idx ranging from 0 to nums.length-1:

Set sorted[count[nums[idx]/exp%10]-1]=nums[idx]; to position element to its sorted position.

Decrement count[nums[idx]/exp%10] by 1.

Copy all elements of sortedArr to nums.

Return nums.

Code:

public int[] countingSort(int[] nums, int exp) {
	int[] sorted=new int[nums.length];
	int[] count=new int[10];
	for (int idx=0; idx < count.length; idx++) {
		count[idx]=0;
	}
	for (int idx=0; idx < nums.length; idx++) {
		count[nums[idx]/exp%10]++;
	}
	for (int idx=1; idx < count.length; idx++) {
		count[idx] += count[idx-1];
	}
	for (int idx=nums.length-1; idx >=0; idx--) {
		sorted[count[nums[idx]/exp %10]-1]=nums[idx];
		count[(nums[idx]/exp)%10]--;
	}
	System.arraycopy(sorted, 0, nums, 0, nums.length);
	return nums;
}


public int[] radixSort(int[] nums) {
	int maxInt=Integer.MIN_VALUE;
	for (int idx=0; idx < nums.length; idx++) {
		if (nums[idx] > maxInt) {
			maxInt=nums[idx];
		}
	}
	for (int exp=1; maxInt/exp>0; exp*=10) {
		countingSort(nums, exp);
	}
	return nums;
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

public class SortRadixSort {
 
	
public int[] countingSort(int[] nums, int exp) {
	int[] sorted=new int[nums.length];
	int[] count=new int[10];
	for (int idx=0; idx < count.length; idx++) {
		count[idx]=0;
	}
	for (int idx=0; idx < nums.length; idx++) {
		count[nums[idx]/exp%10]++;
	}
	for (int idx=1; idx < count.length; idx++) {
		count[idx] += count[idx-1];
	}
	for (int idx=nums.length-1; idx >=0; idx--) {
		sorted[count[nums[idx]/exp %10]-1]=nums[idx];
		count[(nums[idx]/exp)%10]--;
	}
	System.arraycopy(sorted, 0, nums, 0, nums.length);
	return nums;
}


public int[] radixSort(int[] nums) {
	int maxInt=Integer.MIN_VALUE;
	for (int idx=0; idx < nums.length; idx++) {
		if (nums[idx] > maxInt) {
			maxInt=nums[idx];
		}
	}
	for (int exp=1; maxInt/exp>0; exp*=10) {
		countingSort(nums, exp);
	}
	return nums;
}


public static void main(String[] args) {
	/***********************
	 Test cases given below:
	 **********************/
	int[] retVal;
	try {
	SortRadixSort sort=new SortRadixSort();
	int[] nums= { 33,3,4,97,62,122, 124, 20,1};
	System.out.println("\nArray:");
	int arrayIndex=0;
	for (arrayIndex=0; arrayIndex < nums.length; arrayIndex++) {
		System.out.print(nums[arrayIndex]+", ");		
	} 
	System.out.println("\nSorted Array:");
	retVal=sort.radixSort(nums);
	for (arrayIndex=0; arrayIndex < retVal.length; arrayIndex++) {
		System.out.print(retVal[arrayIndex]+", ");		
	} 
	
			
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
		
}
}