Summary: In this tutorial, we will learn what is Counting Sort algorithm and how to use counting sort algorithm to sort a linear data structure like an array in C, C++, and Java.
Introduction to Counting Sort Algorithm
Counting sort is an algorithm for sorting a collection of objects according to keys that are small integers. It operates by counting the number of objects that have each distinct key value, and using arithmetic on those counts to determine the positions of each key value in the output sequence.
Wikipedia
Counting Sort algorithm sorts the data structure based on the frequency of each distinct element of an array.
If stores the count of each distinct element into the relative index position of another array and then sort the array based on their index and counts.
For example, consider the following array:
Array- 5 9 11 10 15 12 2 8 10
Array values ranges from 2 to 15, therefore the size of the array which will store the count of distinct elements would be 15-2+1=14.
Here is the frequency of each element stored in the counting array at index position relative to their values:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 Counting array- 1 0 0 1 0 0 1 1 2 1 1 0 0 1
The frequency of 2 is stored at index 0, frequency of 3 at 1, frequency of 4 at 2, and so on.
After storing the frequency of each element into the counting array, the algorithm rewrites the original array on the basis of the counts.
It iterates the counting array and writes the elements the number of times its frequency.
In our example, it will write 1 times 2 -> 0 times 3 -> 0 times 4 -> 1 times 5 and so on.
So the final sorted array would be:
Sorted array - 2 5 8 9 10 10 11 12 15
Overall the counting sort algorithm implements the following two steps:
- Store the count of disting array value into another array.
- Iterate the counting array and rewrite the original array.
Here is the implementation of counting sort algorithm in C, C++ and, Java:
C
#include <stdio.h>
#include <stdlib.h>
int main()
{
int arr[] = {5, 9, 11, 10, 15, 12, 2, 8 ,10};
countingSort(arr, 0, 8, 2, 15);
return 0;
}
void countingSort(int arr[], int s, int e, int mn, int mx){
int i, k=0, sizeTemp = mx-mn+1;
int temp[sizeTemp];
// Initializing all element of counting array with 0
for(i=0; i<sizeTemp; i++){
temp[i] = 0;
}
//Store the frequency of each element of the original array
//at the relative position in counting array
for(i=0; i<=e; i++){
temp[arr[i]-mn]++;
}
//Iterate through the counting array and re-write the original array.
for (i=mn; i<=mx; i++){
while(temp[i-mn]-->0){
arr[k++]=i;
}
}
//Output the sorted array
for(i=0; i<=8; i++){
printf("%d ",arr[i]);
}
}C++
#include <iostream>
using namespace std;
void countingSort(int arr[], int s, int e, int mn, int mx);
int main()
{
int arr[] {5, 9, 11, 10, 15, 12, 2, 8 ,10};
countingSort(arr,0,8,2,15);
return 0;
}
void countingSort(int arr[], int s, int e, int mn, int mx){
int i,k=0,sizeTemp = mx-mn+1;
int temp[sizeTemp] {0}; // Initializing all element of temp array with 0
//Store the frequency of each element of the original array
//at the relative position in counting array
for(i=0; i<=e; i++){
temp[arr[i]-mn]++;
}
//Iterate through the counting array and re-write the original array.
for (i=mn; i<=mx; i++){
while(temp[i-mn]-->0){
arr[k++]=i;
}
}
//Output the sorted array
for(i=0; i<=8; i++){
cout << arr[i] << " ";
}
}Java
import java.util.*;
public class App {
public static void main(String args[]){
int arr[] = {5, 9, 11, 10, 15, 12, 2, 8 ,10};
int min = 2;
int max = 15;
CountingSort cs= new CountingSort(arr);
cs.sort(arr,0,arr.length-1, min, max);
}
}
public class CountingSort {
int a[];
public CountingSort(int[] a) {
this.a = a;
}
public void sort(int arr[], int s, int e, int mn, int mx){
int i, k=0, sizeTemp = mx-mn+1;
int temp[] = new int[sizeTemp]; // Initializing all element of temp array with 0
//Store the frequency of each element of the original array
//at the relative position in counting array
for(i=0; i<=e; i++) {
temp[arr[i] - mn]++;
}
//Iterate through the counting array and re-write the original array.
for (i=mn; i<=mx; i++){
while(temp[i-mn]-- > 0){
arr[k++]=i;
}
}
//output the sorted array
for(i=0; i<=8; i++){
System.out.print(arr[i]+" ");
}
}
}Output
2 5 8 9 10 10 11 12 15Overview of Counting Sort
- Counting sort is efficient to use when the array values are non-negative and lie in the small range.
- It is not an in-place algorithm (requires an extra array i.e. counting array).
- It has O(n)-complexity.
- To make it a stable sort, some extra steps are needed.
In this tutorial, we learned what is counting sort algorithm and how to sort an array using counting sort algorithm in C, C++ and Java.