Counting Sort.

Write a C++ program to implement Counting Sort.

As we know counting sort algorithm works when the input is known to be within a range. First of all, create an array of size of input range than go through each of the numbers in the input and increment the appropriate array value. Now overwrite this original input with key values in the array and repeating as many times as that index counter holds. It's not a comparison sort. The best, average and worst case complexity of this algorithm is O(N).

Program Code:

#include <iostream>

using namespace std;

int n = 9;

int k = 10;

void display(int *input)

{

for ( int i = 0; i < n; i++ )

cout << input[i] << " ";

cout << endl;

}

void counting_sort(int* input)

{

int CountArr[k] = { 0 };

for (int i=0;i<n;i++)

{

CountArr[input[i]]++;

}

int outputindex=0;

for (int j=0;j<k;j++)

{

while (CountArr[j]--)

input[outputindex++] = j;

}

}

int main()

{

int input[n] = { 3, 5, 2, 1, 7, 6, 8, 4, 9};

cout << "Input elements are : ";

display(input);

counting_sort(input);

cout << "Output elements are : ";

display(input);

return 0;

}

The program output is tested on www.jdoodle.com

Output:

Input elements are : 3 5 2 1 7 6 8 4 9 

Output elements are : 1 2 3 4 5 6 7 8 9 

Thanks

Mukesh Rajput