Counting sort is a sorting algorithm that is not based on comparison like most other methods. This method of sorting is used when all elements to be sorted fall in a known, finite and reasonably small range.
How it works:
The algorithm refers to finding for each element a[i] the number of elements from the array that are lower than it.
Step by step example :
Having the following list, let;s try to use counting sort to arrange the numbers from lowest to greatest:
Unsorted list, the array A contains the elements to be sorted:
We count the number of occurrences from the list into the array C, and for example we found one occurrence for the element 3 so far :
PS: A – list of sorting elements, B – Sorted list, C – number of occurences.
The next element is 2, so we increment by 1 the array C and so on until the end of the array:
The next element is 3, so we increment by 1 :
The next element is 9, so we increment by 1 :
The next element is 2, so we increment by 1 :
The next element is 8, so we increment by 1 :
The next element is 1, so we increment by 1 :
The next element is 4, so we increment by 1 :
The next element is 10, so we increment by 1 :
The next element is 1, so we increment by 1 :
Now, using the elements of the C array, we add the current element with the one from below:
Now let us sort things out a bit. First, look at the last element from the sorting list, which is 1, next look at what number is on the position with 1 as the index from the C array – where all the occurrences are. That number will point to the position in the final sorted array B, which is 2:
Decrease the number of occurrences by 1 since we found a place for a number:
Now, we do the same for the next element which is 10, and the position for it is 10:
Decrease the number of occurrences by 1 since we found a place for a number:
4 is the next element, after which we decrease the number of occurrences:
1 is the next element, after which we decrease the number of occurrences:
8 is the next element, after which we decrease the number of occurrences:
2 is the next element, after which we decrease the number of occurrences:
9 is the next element, after which we decrease the number of occurrences:
3 is the next element, after which we decrease the number of occurrences:
2 is the next element, after which we decrease the number of occurrences:
3 is the next element, after which we decrease the number of occurrences:
The data has been sorted! Look at the B array!
Sample code:
#include < iostream >using namespace std;
int main()
{long int A[10000];
long int n = 100;
int *p=new int[50];
int i;
int B[10];
cout << "Please insert the number of elements to be sorted: ";
cin >> n; // The total number of elements
for(int i=0;i< n;i++)
{cout << "Input " << i << " element: ";
cin >>A[i]; // Adding the elements to the array
}cout << "Unsorted list:" << endl; // Displaying the unsorted array
for(int i=0;i < n;i++)
{cout << A[i] << " ";
}int k=A[0];
for(int i=1;i< n;++i)
{if(k< A[i])
{k=A[i];
}}for(int i=0;i< =k;++i)
{p[i]=0;
}for(int j=0;j< n;++j)
{p[A[j]]=p[A[j]]+1;
}for(int i=1;i< =k;++i)
{p[i]=p[i-1]+p[i];
}for(int j=n-1;j>=0;--j)
{i=A[j];
B[p[i]-1]=i;
p[i]=p[i]-1;
}cout << "nSorted list:" << endl; // Displaying the sorted array
for(int i=0;i< n;i++)
{cout << B[i] << " ";
}return 0;
}
Output:
Code explanation:
for(int i=0;i< =k;++i)
{p[i]=0;
}
The array that holds the number of occurrences is p, and at first, all the values will be set to 0.
for(int j=0;j< n;++j)
{p[A[j]]=p[A[j]]+1;
}
The array p is filled up with the number of occurrences for each element.
for(int i=1;i< =k;++i)
{p[i]=p[i-1]+p[i];
}
The sum of the previous element + current element is calculated.
for(int j=n-1;j>=0;--j)
{i=A[j];
B[p[i]-1]=i;
p[i]=p[i]-1;
}
The elements are inserted into the proper places, and the last instruction decrements the number of occurrences.
Complexity:
Counting sort has a running time of O(n + k), where n is the number of elements to be sorted and k is the range of those numbers. If k = O(n), this algorithm has O(n) performance. Counting sort does not sort in place, since it creates two other arrays, counting array C and output array. The space complexity is O(n + k), where n and k are the length of the array A and C, respectively. No swap operations is performed during the process.
Advantages:
- is stable;
- is fast.
Disadvantages:
- unsuitable for strings;
- memory requirement, it requires both an array and a heap of size n;
- not recommended on large sets of data.
Conclusion:
Counting sort may for example be the best algorithm for sorting numbers whose range is between 0 and 100, but it is probably unsuitable for sorting a list of names alphabetically. However, counting sort can be used with radix sort to sort a list of integers whose range is too large for counting sort to be suitable alone.
