Counting Sort Algorithm

Counting sort is an algorithm for sorting a collection of objects according to the keys between a specific integer range

It works based on counting the number of objects with specific keys and doing some arithmetic operations to calculate the positions of the objects in the output sequence.

Example

Input array: [1, 4, 4, 3, 3, 5, 5, 6, 7, 2, 4]
Output array: [1, 2, 3, 3, 4, 4, 4, 5, 5, 6, 7]

1) In count array to store the count of each element.
    Range of elements in the array is 0 to 7 (maximum element)

Index array :

 

Count array is :

2) Update count array such that at each index store the sum of itself and previous count.

3) Output each object from the input sequence by decreasing the count.
    Places of elements:

Output will be: [1, 2, 3, 3, 4, 4, 4, 5, 5, 6, 7]

Algorithm

Time complexity: O(nlogn), n is size of the array

a. First get the maximum element of the array by traversing in the array and store it in Range.

b. Create a count array of size of Range + 1 and initialize with zeroes.

c. Update the array with count of elements in the array according tothere indexes. Store the count of i at index i.

d. Now, update the count array such that at each index  element stores the sum of itself and previous element.

e. Create an auxiliary output array.

f. In this output array store the elements from the input array according to count array, if count[i] = k, store i in k. and decrease the count[i] = count[i] – 1. Do it for all the elements in the input array.

g. Copy the output array into the input array.
    Input_array[i] = output[i]

h. Finally print the sorted input array.

Algorithm working

C++ Program

#include <bits/stdc++.h>

using namespace std;


void CountingSort(int arr[], int n)
{
    //Range will be the maximum element of the array
    int RANGE = 0;
    for (int k = 0; k < n; ++k)
    {
        if (arr[k] > RANGE )
        {
            RANGE = arr[k];
        }
    }
    int count[RANGE + 1], i;
    //Initialize count array with zeroes
    for (int k = 0; k < RANGE + 1; ++k)
    {
        count[k]=0;
    }
    //count array stores the count of elements in the array in the given range
    for(i = 0; i < n; ++i)
    {
            count[arr[i]] = count[arr[i]] + 1;
    }
    //update count array such that the count[i] = count[i] + count[i-1]; 
    for (i = 1; i <= RANGE; ++i)
    {
        count[i] = count[i] + count[i-1];
    }
    //In the output array update elements based on the count array
    //output[count[arr[i]]-1] = arr[i]
    //decrese count
    int output[n];
    for (i = 0; i < n; ++i)
    {
        output[count[arr[i]]-1] = arr[i];
        count[arr[i]] = count[arr[i]] - 1;
    }
    //copy the output array into input array
    for (i = 0; i < n; ++i)
    {
        arr[i] = output[i];
    }
}
//Main function to search the Counting sort
int main()
{
    int input_array[] = {1,4,4,3,3,5,6,7,2,4};
    int size = sizeof(input_array)/sizeof(int);
    CountingSort(input_array,size);
    for (int i = 0; i < size; ++i)
    {
        cout<<input_array[i];
    }
    return 0;
}
Try It


Next > < Prev
Scroll to Top