Implement Counting Sort Editorial

Practice Problem Link: Implement Counting Sort

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given an array, sort it using counting sort.

Approach

The counting sort algorithm is used to sort an array in linear time and can be used when the largest element in the array and the size of the array are of the same order of magnitude. In this algorithm, we map the frequencies of the elements of the main array into an auxiliary array and store them in sorted order. The algorithm's steps are :

• Make an auxiliary hash array and map the frequencies of elements of the original array into it.
• Make a new array that will store the sorted array later of the appropriate size. 
• Iterate over all the numbers from the smallest to the largest element in the array, and add hash[A[i]] number of elements into the new array.
• Finally, empty the new array into the old array to get our sorted array.

Make sure to handle the negative elements, if any effectively. 

Analysis

• Time Complexity : O(n)
• Space Complexity : O(n)

Implementation

C++

void countingSort(vector<int> &arr) {
	vector<int> output(arr.size() + 1, 0);
	int maximum = 0;
	for(int i = 0; i < arr.size(); i++) {
		maximum = max(maximum, abs(arr[i]));
	}
	vector<int> count(2 * maximum + 2, 0);
	for(auto &x: arr) {
		x += maximum;
	}
	for(int i = 0; i < arr.size(); i++) {
		count[arr[i]]++;
	}
	for(int i = 1; i <= 2 * maximum + 1; i++) {
		count[i] += count[i - 1];
	}
	for(int i = 0; i < arr.size(); i++) {
		output[count[arr[i]] - 1] = arr[i];
		count[arr[i]]--;
	}
	for(int i = 0; i < arr.size(); i++) {
		arr[i] = output[i] - maximum;
	}
}

Java

class Solution {
	void countingSort (int[] arr) {
		int[] output = new int[arr.length + 1];
		int maximum = Integer.MIN_VALUE;
		for(int i = 0; i < arr.length; i++) {
			maximum = Math.max(maximum, Math.abs(arr[i]));
		}
		int[] count = new int[2 * maximum + 2];
		for(int i = 0; i < arr.length; i++) {
			arr[i] += maximum;
		}
		for(int i = 0; i < arr.length; i++) {
			count[arr[i]]++;
		}
		for(int i = 1; i <= 2 * maximum + 1; i++) {
			count[i] += count[i - 1];
		}
		for(int i = 0; i < arr.length; i++) {
			output[count[arr[i]] - 1] = arr[i];
			count[arr[i]]--;
		}
		for(int i = 0; i < arr.length; i++) {
			arr[i] = output[i] - maximum;
		}
	}
}