Counting Sort

Counting sort is a linear time sorting algorithm used to sort items when they belong to a fixed and finite set. Integers which lie in a fixed interval, say k1 to k2, are examples of such items.


1. Count for every key j, 1 ≤ j ≤ m how often it occurs in the input array. Store results in an array C.

2. The counting information stored in C can be used to determine the position of each element in the sorted array. Suppose we modify the values of the C [ j ] so that now C [ j ] = the number of keys less than or equal to j . Then we know that the elements with key “ j ” must be stored at the indices C [ j − 1 ]+ 1 ,…, C [ j ] of the final sorted array.

3. We use a “trick” to move the elements to the right position of an auxiliary array. Then we copy the sorted auxiliary array back to the original one.

The algorithm makes two passes over A and one pass over B. If size of the range k is smaller than size of input n, then time complexity=O(n). Also, note that it is a stable algorithm, meaning that ties are resolved by reporting those elements first which occur first.

void countSort(int * arr)
    // The output array that will have sorted  arr
    int output[ count( arr)];
    // Create a count array to store count of individual element and
    // initialize count array as 0
    int count[RANGE + 1], i;
    memset(count, 0, sizeof(count));
    // Store count of each element
    for(i = 0;  arr[i]; ++i)
        ++count[ arr[i]];
    /* modified count array indicates the position of each object in 
	the output sequence. */
    for (i = 1; i <= RANGE; ++i)
        count[i] += count[i-1];
    // Build the output array
    for (i = 0;  arr[i]; ++i)
        output[count[ arr[i]]-1] =  arr[i];
        --count[ arr[i]];
    // Copy the output array to  arr
    for (i = 0;  arr[i]; ++i)
         arr[i] = output[i];

Time Complexity: O(n+k) where n is the number of elements in input array and k is the range of input.
Auxiliary Space: O(n+k)

Source: Counting Sort

2 Thoughts on “Counting Sort

  1. satish on August 1, 2014 at 2:19 pm said:

    Algorithm is fine. But where can I get its program in c.
    See this : best c compiler for windows

  2. i dont understand what 4th line meaning can admin explain

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation