C Algorithms – Counting Sort

Exforsys

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:

  1.  #include < iostream >
  2. using namespace std;
  3. int main()
  4. {
  5. 	long int A[10000];
  6. 	long int n = 100;
  7. 	int *p=new int[50];
  8. 	int i;
  9. 	int B[10];
  10. 	cout << "Please insert the number of elements to be sorted: ";
  11. 	cin >> n;	// The total number of elements
  12. 	for(int i=0;i< n;i++)
  13. 	{
  14. 		cout << "Input " << i << " element: ";
  15. 		cin >>A[i]; // Adding the elements to the array
  16. 	}
  17. 	cout << "Unsorted list:" << endl;	// Displaying the unsorted array
  18. 	for(int i=0;i < n;i++)
  19. 	{
  20. 		cout << A[i] << " ";
  21. 	}
  22. 	int k=A[0];
  23. 	for(int i=1;i< n;++i)
  24. 	{
  25. 		if(k< A[i])
  26. 		{
  27. 			k=A[i];
  28. 		}
  29. 	}
  30. 	for(int i=0;i< =k;++i)
  31. 	{
  32. 		p[i]=0;
  33. 	}
  34. 	for(int j=0;j< n;++j)
  35. 	{
  36. 		p[A[j]]=p[A[j]]+1;
  37. 	}
  38. 	for(int i=1;i< =k;++i)
  39. 	{
  40. 		p[i]=p[i-1]+p[i];
  41. 	}
  42.  
  43. 	for(int j=n-1;j>=0;--j)
  44. 	{
  45. 		i=A[j];
  46. 		B[p[i]-1]=i;
  47. 		p[i]=p[i]-1;
  48. 	}
  49. 	cout << "nSorted list:" << endl;	// Displaying the sorted array
  50. 	for(int i=0;i< n;i++)
  51. 	{
  52. 		cout << B[i] << " ";
  53. 	}
  54. 	return 0; 
  55. }

Output:

Code explanation:

  1. for(int i=0;i< =k;++i)
  2. 	{
  3. 		p[i]=0;
  4. 	}

The array that holds the number of occurrences is p, and at first, all the values will be set to 0.

  1. 	for(int j=0;j< n;++j)
  2. 	{
  3. 		p[A[j]]=p[A[j]]+1;
  4. 	}

The array p is filled up with the number of occurrences for each element.

  1. for(int i=1;i< =k;++i)
  2. 	{
  3. 		p[i]=p[i-1]+p[i];
  4. 	}

The sum of the previous element + current element is calculated.

  1. for(int j=n-1;j>=0;--j)
  2. 	{
  3. 		i=A[j];
  4. 		B[p[i]-1]=i;
  5. 		p[i]=p[i]-1;
  6. 	}

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.

[catlist id=197].

Related posts