CC-6 : Implement Counting Sort Algorithm.

Description:

SCounting Sort works uses a non-comparison based algorithm. Is it suited for sorting arrays with only small positive integers. For input array of size n and with maximum positive element maxVal, the Counting Sort algorithm creates another array named countArr of size maxVal+1. Frequency of each number n in input array is stored in countArr[n]. Now we can collate sorted array from countArr by picking up only indexes that’s data value is > 0. If data value is one, we will add index n one time in sorted array. If data value is m, we will add index n, m times in sorted array. Given an input array, sort its elements using Counting 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:

CountingSort(nums[], maxInt):

Integer array named nums, and its maximum element maxInt are received as input parameters.

Initialize and integer array variable countArr with maxInt+1 size.

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

Increment current value of countArr[idx] by 1.

Initialize int variable ndx to 0. We will use this variable as index of sorted array.

We will re-use input array nums itself to collate the sorted array.

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

Using a while loop, we can collate sorted array from countArr by picking up only indexes that’s data value is > 0. If data value is one, we will add index n one time in sorted array. If data value is m, we will add index n, m times in sorted array.

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

Code:

public int[] countingSort(int[] nums, int maxInt) {
	int[] countArr= new int[maxInt+1];
	for (int idx=0;idx < nums.length; idx++) {
		countArr[nums[idx]]++;
	}
	int ndx=0;
	for (int idx=0; idx < countArr.length; idx++) {
		while (countArr[idx] > 0) {
			nums[ndx]=idx;
			ndx++;
			countArr[idx]--;
		}
	}
	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 SortCountingSort {
	
public int[] countingSort(int[] nums, int maxInt) {
	int[] countArr= new int[maxInt+1];
	for (int idx=0;idx < nums.length; idx++) {
		countArr[nums[idx]]++;
	}
	int ndx=0;
	for (int idx=0; idx < countArr.length; idx++) {
		while (countArr[idx] > 0) {
			nums[ndx]=idx;
			ndx++;
			countArr[idx]--;
		}
	}
	return nums;
}

public static void main(String[] args) {
	/***********************
	 Test cases given below:
	 **********************/
	int[] retVal;
	try {
	SortCountingSort sort=new SortCountingSort();
	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.countingSort(nums,124);
	for (arrayIndex=0; arrayIndex < retVal.length; arrayIndex++) {
		System.out.print(retVal[arrayIndex]+", ");		
	} 
	
			
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
		
}
}