Counting sort
Introduction:
When we know that all array elements lie between two numbers or between 0 and k then this algorithm is used provided numbers are almost evenly distributed.
This is an algorithm which can sort an array in \(O(n+k)\) time.
This algorithm is not good when n is small and k is big ... because we could have sorted the array in \(O(nlogn)\) time using mergesort.
Problem Statement:
Sort an array of n integers
Algorithm
1. we have an array of n numbers and given that all numbers lie between 0 and k both inclusive.
2. create an array of size k+1 with all numbers initialised to zero.
3. Then for every element a[i] in given array increament count[a[i]].
4. You can now just print the sorted array as output by scanning through count[] array and print i count[i] times.
5. but if you want to store it some other array , you could use similar logic used in step 4 to get sorted array elements
6. Following implementation shows another way getting sorted array ( in another separate array ) but in 2*O(n) time using cummulative frequencies to determine the position of a[i] in sorted array directly and placing it there in sorted array .
Pseudo code :
counting_sort(a[], b[], n, k):
c[k+1] = {0}
for i = 0 to n:
c[ a[i] ]++
for i = 1 to n:
c[i] += c[i-1] // cummulative frequency
for i = 0 to n:
b[ c[a[i]]-1 ] = a[i]
c[a[i]]--
Code :
#include <bits/stdc++.h>
using namespace std;
void counting_sort(int a[], int b[], int n, int k)
{ //a,b, are of size n and have values in range [0,k] (inclusive)
int c[k + 1] = {0};
for (int i = 0; i < n; i++)
{
c[a[i]]++;
}
for (int i = 1; i <= k; i++) // cummulative sum
{
c[i] += c[i - 1];
}
for (int i = 0; i < n; i++)
{
b[c[a[i]] - 1] = a[i]; // 0 based indexing
c[a[i]]--;
}
}
int main()
{
int n, k;
cout << "Enter n: ";
cin >> n;
cout << "Enter k: ";
cin >> k;
int a[n];
int b[n];
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
counting_sort(a, b, n, k);
for (int i = 0; i < n; i++)
{
cout << b[i] << " ";
}
printf("\n");
}
Complexity Analysis :
Time complexity is \(O(n)\)