Count Sort

Sort by counting element frequencies

Introduction

Count Sort is a non-comparison-based sorting algorithm that sorts elements by counting their occurrences. It works efficiently for small integer ranges by using an auxiliary array to store frequency counts, then computes prefix sums to place elements directly into their sorted positions.

How Count Sort Works?

Find Maximum Element

Find the maximum element in the input array to determine the size of the frequency array.

Create Frequency Array

Create a frequency array of size maxi + 1 initialized with zero. This array will store the count of each element from the input array.

Count Element Frequencies

Traverse the input array and for each element, increment the frequency by 1. This will give the frequency of each element.

Cumulative Frequency

Modify the frequency array to hold the cumulative frequency. For each index i, update freq[i] to be the sum of freq[i] and freq[i-1]. This step allows placement of elements in their correct positions later.

Build Sorted Array

Create an empty array answer of the same size as the input array.
Traverse the input array in reverse order. For each element, place it in the correct position in the answer array using the frequency array.

Return Sorted Array

The array answer now contains the sorted elements, which are returned as the result.

Implementation of Count Sort

// countsort.cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> countSort(vector<int> &arr)
{
int maxi = *max_element(arr.begin(), arr.end());
vector<int> freq(maxi + 1, 0);
for (int &ele : arr)
{
    freq[ele]++;
}
for (int i = 1; i < freq.size(); i++)
{
    freq[i] = freq[i] + freq[i - 1];
}
vector<int> ans(arr.size());
for (int i = arr.size() - 1; i >= 0; i--)
{
    ans[--freq[arr[i]]] = arr[i];
}
return ans;
}
int main()
{
vector<int> arr{7, 2, 1, 5, 3, 6, 7};
vector<int> ans = countSort(arr);
for (int &ele : ans)
{
    cout << ele << " ";
}
}

Why Cumulative Frequency?

Cumulative frequency in Counting Sort is an essential technique that helps the algorithm efficiently determine the correct position for each element in the sorted output.Cumulative frequency tells us the position up to which an element will be placed in the sorted array. To get the correct position for each element, we use the cumulative frequency - 1.

Why Traversing from end?

While storing the final sorted result in the array, we traverse from the end to maintain the stability of the algorithm. If we move from the beginning, the relative order of duplicate elements will be broken.

Time Complexity of Count Sort

Finding the Maximum Element O(n)
Building the Frequency Array O(n)
Building the Cumulative Frequency Array O(k)
Placing Elements in Sorted Order O(n)

Time Complexity : O(n+k)

Space Complexity of Count Sort

For Frequency Array:O(n)
For Output Array:O(k)

Space Complexity : O(n+k)

Limitations of the Count Sort Algorithm

The above implementation of Count Sort will fail when dealing with negative indices. This is because the implementation stores the frequency of each element at its own index in the frequency array, which assumes that all values are non-negative.

Overcoming this limitation

To handle negative element, subtract the most negative number in the array to every element. This ensures that all elements in the array are shifted into the non-negative range, allowing the Count Sort algorithm to work correctly.While returning the answer we must add to every element to get the correct sorted array.

Implementation

Implementation of Count Sort if negative elements are present.

// countsort.cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> countSort(vector<int> &arr)
{
int mini = *min_element(arr.begin(), arr.end());
for(int i=0;i<arr.size();i++){
    arr[i]-=mini;
}
int maxi = *max_element(arr.begin(), arr.end());
vector<int> freq(maxi + 1, 0);
for (int &ele : arr)
{
    freq[ele]++;
}
for (int i = 1; i < freq.size(); i++)
{
    freq[i] = freq[i] + freq[i - 1];
}
vector<int> ans(arr.size());
for (int i = arr.size() - 1; i >= 0; i--)
{
    ans[--freq[arr[i]]] = arr[i]+mini;
}
return ans;
}
int main()
{
vector<int> arr{-10,0,1,10,-4,7};
vector<int> ans = countSort(arr);
for (int &ele : ans)
{
    cout << ele << " ";
}
}

Time Complexity

Finding the Minimum Element: O(n)
Shifting Elements to make all Non-Negative: O(n)
Finding the Maximum Element: O(n)
Building the Frequency Array: O(n)
Building the Cumulative Frequency Array: O(k)
Placing Elements in Sorted Order: O(n)