Counting Sort

Reet Maggo
Last Updated: May 13, 2022

Introduction

To grasp the concept of counting sort, it is important to first understand the technique and the series of operations required to make an array sorted using counting sort.

 

In this blog, we have also used an example and its code snippet to understand the concept better.

What is Counting Sort? 

Counting sort is an integer sorting algorithm, which sorts elements in an array according to small positive integer keys. The technique sorts an array by counting the number of occurrences of each unique element of the array.

 

Operations that take place in counting sort are:

  • Finding the count of all distinct elements in the array
  • Calculating the position of each element for the sorted array

 

Example of Counting Sort

First, we need to store the count of all distinct elements in the initial array. For that, the maximum value in the array is stored, and a new array of this length is created. (The size of the new array will be 6.)

 

Now with the length of the array being equal to the largest value stored, the count of the biggest element present in the initial array will be stored at the maximum index of the new array (the count of element ‘6’ in the initial array is stored at index 6 in the new array)

 

 

However, we need to store the count of each element, along with the count of the previous element to finally make the sorted array. This is because the position of the next element depends on the number of times its previous element is repeated. (There are two ‘1’s in the array, so after sorting, ‘2’ will be placed after two ‘1’s, i.e., the second index)

 

 

To calculate the position of elements for the final sorted array, the position of each element is stored at the corresponding index as the sum of the number stored at the previous index and it’s own (The position of element ‘2’ will be 2 + 1 in the sorted array. Similarly, the position of element ‘3’ will be 3 + 3 in the final array)

 

 

Finally, we start with the last element of the initial array (3), go to that particular index (index 3) in the position array and decrement the element at that index(6 is decremented to 5). The resulting number (5) would be the index in the final array where the particular element will be placed.

 

Algorithm

  • The maximum element of the initial array is stored in variable ‘K’
  • ‘Count’ array is created with all elements initially being 0, and then the count is incremented every time the number at the index occurs in the array.
  • ‘Count’ array is updated for positions by taking the sum of previous elements and storing it as the position for the sorted array.
  • Elements are put into the sorted array using a for loop and the function is finally called for sorting a given array.

Code snippet for the given example:

void countingSort(int arr[], int n)
{

    //finding maximum element
   int k = arr[0];
    for (int i = 0; i < n; i++)
    {
        k = max(k, arr[i]);
    }

    //creating count array
   int count[10] = {0};
    for (int i = 0; i < n; i++)
    {
        count[arr[i]]++;
    }

    //changing count array for positions
    for (int i = 1; i <= k; i++)
    {
        count[i] += count[i - 1];
    }

    //for sorted array
   int sorted[n];

    for (int i = n - 1; i >= 0; i--)
    {
        count[arr[i]] = count[arr[i]] - 1;
        sorted[count[arr[i]]] = arr[i];
    }

    //putting arranged output into initial array
    for (int i = 0; i < n; i++)
    {
        arr[i] = sorted[i];
    }
}

int main()
{
   int arr[] = {1, 3, 2, 3, 4, 6, 4, 1, 3};
    countingSort(arr, 9);

    for (int i = 0; i < 9; i++)
    {
        cout << arr[i] << " ";
    }
   return 0;
}

 

Output

1 1 2 3 3 3 4 4 6

 

Time Complexity

The time complexity of the counting sort algorithm is O(N + K), ‘N’ being the number of elements in the array and ‘K’ being the range of elements in it. Counting sort is most efficient if the range of input values is not greater than the number of values to be sorted.

 

The array of count ‘K’ is read on the output pass, and a new array is written with ‘N’ elements. So there are ‘N’ reads and K writes (to zero the counts), then ‘N’ writes and 'K' reads for (2 N + 2 K) operations, but since constant 2 is ignored, the time complexity comes out to be O (N + K).

Space Complexity

For an array with the maximum element being ‘K’, the space complexity is O(K) for counting sort.

A larger range of elements gives larger space complexity. Therefore the Counting array is not ideal for a very large range of integers. 

 

Frequently Asked Questions

  1. What is counting sort used for?
    The counting sort algorithm efficiently sorts arrays with non-negative integer keys, such as a list of positive integers, with keys just the value of the integer or a list of words having keys assigned to them by some scheme.
     
  2. What is the disadvantage of counting sort?
    The use of counting sort is only limited to arrays with integer elements because an array of frequencies cannot be constructed otherwise.
     
  3. What is the difference between counting sort and bucket sort?
    Bucket sort involves linked lists, dynamic arrays, or a large amount of pre-allocated memory, while count sort stores a single number-the count of items per bucket.
     
  4. Which is the fastest sorting technique?
    Quicksort is considered the fastest sorting algorithm because its time complexity is O( N * (log N)) in the best and average case scenarios and O (N ^ 2) in the worst case. Thus, it has an upper hand in most cases.
     
  5. Is counting sort better than quick sort?
    Counting sort has better time complexity. However, it has worse space complexity. So the better option would depend on whether memory consumption is prioritized or CPU consumption.
    Moreover, counting sort might be computationally superior but can only be used for small integer values. Hence it cannot replace quicksort in all conditions.

Key takeaways

In this article, we learned how the counting sort algorithm works and how it is implemented along with an example.

The counting sort algorithm is very efficient for cases where input values are lesser than or equal to the number of values to be sorted. You can go to CodeStudio and try solving problems. Share this blog with your friends if you found it helpful!

Until then, All the best for your future endeavors, and Keep Coding.

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think