Counting Sort is a technique used to sort array elements.
In this technique, we store the frequency of unique elements in the array in a special data structure called Map.
Map is a container which stores data in the form of keys and values, and sorts the data based on the key values.
In this technique, unique array elements are considered as keys and its frequency is considered as values.
After storing unique array elements with its frequency in Map, each unique element is restored in the given array, frequency no.of times as per the order of Map. This makes the restored array sorted.
ADVANTAGES :
- This technique can sort array containing negative elements.
- Extra memory is allocated only for unique array elements.
DISADVANTAGES :
- Extra memory is used for sorting.
- Takes more time as compared to regular counting sort.
LET US SEE THE CODE:
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,i,j,x,y;
cout << "Enter no.of elements" << endl;
cin >> n;
vector<int> arr(n);
for(i=0;i<n;i++) // loop to take array input
{
cin >> arr[i];
}
map<int,int> frequency; // declaring map
for(i=0;i<n;i++) //loop to store unique element and its frequency in map
{
if(frequency.find(arr[i])==frequency.end()) //checking if elements already exist in map
{
frequency[arr[i]]=1; // if no, count of the element is 1
}
else
{
frequency[arr[i]]++; // if yes, count of the element is incremented
}
}
map<int,int> :: iterator itr;
i=0;
for(itr=frequency.begin();itr!=frequency.end();itr++) // iterating to each element of the map
{
x=itr->first; // itr->first contains the array element
y=itr->second; // itr->second contains its frequency
for(j=0;j<y;j++) // loop to change next y elements of array to x
{
arr[i++]=x; // changing ith element of array to x and incrementing i
}
}
for(i=0;i<n;i++) // printing sorted array
{
cout << arr[i] << " ";
}
return 0;
}
TESTCASE 1:
Enter no.of elements 5 -3 4 2 5 -1 -3 -1 2 4 5
TESTCASE 2:
Enter no.of elements 6 1 5 4 2 0 6 0 1 2 4 5 6