Count Sort – C++, Java, and Python Implementation

Given an integer array, effectively sort it using the count sort algorithm.

We have already discussed the counting sort algorithm in detail, which can be used to sort non-negative integers between a specific range. This post covers a variation of counting sort that can work on negative numbers and can sort numbers in any range. But this version doesn’t produce a stable sort, i.e., the relative order of items with equal keys is not preserved anymore and runs in O(n.log(n)) time, where n is the total number of elements in the input collection.

The idea remains the same – iterate over the collection and construct a map storing information about the total number of times each key occurs within the input collection. Then loop over the collection again and then use those counts to determine each key value’s final positions in the collection. This takes advantage of the fact that a map is sorted according to the keys’ natural order (ascending order).

Following is the C++, Java, and Python implementation of count sort that takes O(n) space:

C++

#include <iostream>

#include <vector>

#include <map>

using namespace std;

void countSort(vector<int> &input)

{

// create an empty map to store the frequency of array elements

map<int, int> freq;

// store distinct values in the input array as key and

// their respective counts as values

for (int x: input) {

freq[x]++;

}

// traverse the map and overwrite the input array with sorted elements

// (the map will iterate based on the sorted order of keys)

int i = 0;

for (auto &p: freq)

{

while (p.second--) {

input[i++] = p.first;

}

int main()

{

vector<int> input = { 4, 2, 1, 4, 1, 4, 2, 1, 10 };

countSort(input);

for (int i: input) {

cout << i << " ";

}

return 0;

}

Download Run Code

Output:

1 1 1 2 2 4 4 4 10

Java

import java.util.Arrays;

import java.util.Map;

import java.util.TreeMap;

class Main

{

public static void countSort(int[] nums)

{

// create a `TreeMap` to store the frequency of array elements

Map<Integer, Integer> freq = new TreeMap<>();

// store distinct values in the input array as key and

// their respective counts as values in the `TreeMap`

for (int num: nums) {

freq.put(num, freq.getOrDefault(num, 0) + 1);

}

// traverse the map (based on the sorted order of keys) and

// overwrite the input array with sorted elements

int i = 0;

for (var entry: freq.entrySet())

{

int value = entry.getValue();

while (value-- > 0) {

nums[i++] = entry.getKey();

}

public static void main(String[] args)

{

int[] nums = { 4, 2, 1, 4, 1, 4, 2, 1, 10 };

countSort(nums);

System.out.println(Arrays.toString(nums));

}

Download Run Code

Output:

[1, 1, 1, 2, 2, 4, 4, 4, 10]

Python

def countSort(nums):

# create a dictionary to store the frequency of list elements

freq = {}

# store distinct values in the input list as keys and

# their respective counts as values in the dictionary

for i in nums:

freq[i] = freq.setdefault(i, 0) + 1

# traverse the dictionary (based on the sorted order of keys) and

# overwrite the input list with sorted elements

i = 0

for key, value in sorted(freq.items()):

while value > 0:

nums[i] = key

value = value - 1

i = i + 1

if __name__ == '__main__':

nums = [4, 2, 1, 4, 1, 4, 2, 1, 10]

countSort(nums)

print(nums)

Download Run Code

Output:

[1, 1, 1, 2, 2, 4, 4, 4, 10]

Count Sort – C++, Java, and Python Implementation

C++

Java

Python

Share this: