There are many sorting algorithms like merge sort, quick sort, etc to sort a linear data structure.
Of all the sort algorithms the fastest is the Counting sort, whose time complexity is approx O(n).
But counting sort is only viable when
- values of element lie in the small range.
- the values are non-negative.
Implementation of Counting Sort in 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 temp array with 0
for(i=0; i<sizeTemp; i++){
temp[i] = 0;
}
for(i=0; i<=e; i++){
temp[arr[i]-mn]++;
}
for (i=mn; i<=mx; i++){
while(temp[i-mn]-->0){
arr[k++]=i;
}
}
for(i=0; i<=8; i++){
printf("%d ",arr[i]);
}
}
Output
2 5 8 9 10 10 11 12 15
Reference: My Blog