C++ Programming Code Examples

C++ > Sorting Searching Code Examples

C++ Program to Implement Counting Sort



C++ Program to Implement Counting Sort

This is a C++ program to sort the given data using Counter Sort.

- Counter sort implements on a given finite range (k) of the integers.
- It counts the occurrence of each element.
- Since it maintains the counter of each integer in the range space complexity is O(k).
- The time complexity is O(n+k).

- count the number of occurrences of each element.
- Store it in the array of size same as the range of data input.
- Use the element value to refer the counter index.
- Display the result.
- Exit.

#include<iostream>
 
using namespace std;
 
// A function implementing Counter sort.
void CounterSort(int a[], int n, int r, int lower)
{
	int i, j = 0, counter[r] = {0};	
	// Counting the number occurrence of each element.
	for(i=0; i<n; i++)
		counter[a[i]-lower]++;
 
	i=0;
	// placing the elements back into array.
	while(i < r)
	{
		flag:
		a[j] = lower+i;
		j++;
		counter[i]--;
 
		// place the same element until its counter is zero.
		if(counter[i] > 0)
		goto flag;
 
		i++;
	}
}
 
int main()
{
	int n, i, range, ulimit, llimit;
	cout<<"\nEnter the number of data element to be sorted: ";
	cin>>n;
 
	cout<<"\nEnter the lower and upper limit of the data to be entered: ";
	cin>>llimit>>ulimit;
 
	// Range of the input data. 
	range = ulimit-llimit+1;
 
	int arr[n];
	for(i = 0; i < n; i++)
	{
		cout<<"Enter element "<<i+1<<": ";
		cin>>arr[i];
	}
 
	CounterSort(arr, n, range, llimit);
 
	// Printing the sorted data.
	cout<<"\nSorted Data ";
	for (i = 0; i < n; i++)
        	cout<<"->"<<arr[i];
 
	return 0;
}