# Counting Sort

Counting sort is a sorting technique based on keys between a specific range. It works by counting the number of objects that have each distinct key value, and using arithmetic on those counts determine the positions of each key value in the output sequence. Example: For simplicity, consider the data in the range 0 to 9.

Input data: 1, 4, 1, 2, 7, 5, 2

1) Take a count array to store the count of each distinct object.

Index: 0 1 2 3 4 5 6 7 8 9

Count: 0 2 2 0 1 1 0 1 0 0

2) Modify the count array such that each element at each index

stores the sum of previous counts.

Index: 0 1 2 3 4 5 6 7 8 9

Count: 0 2 4 4 5 6 6 7 7 7

The modified count array indicates the position of each object in

the output sequence.

3) Output each object from the input sequence followed by

decreasing its count by 1.

Process the input data: 1, 4, 1, 2, 7, 5, 2. Position of 1 is 2.

Put data 1 at index 2 in output. Decrease count by 1 to place

next data 1 at an index 1 smaller than this index. Implementation using C: #include <stdio.h>

#include <string.h>

#define RANGE 255

void count_Sort(char arr[])

{

// The output character array that will have sorted arr

char output[strlen(arr)];

// Create a count array to store count of individual

// characters and initialize count array as 0

int count[RANGE + 1], i;

memset(count, 0, sizeof(count));

// Store count of each character

for(i = 0; arr[i]; ++i)

++count[arr[i]];

/* Change count[i] so that count[i] now contains actual

position of this character in output array */

for (i = 1; i <= RANGE; ++i)

count[i] += count[i-1];

//output character array

for (i = 0; arr[i]; ++i)

{

output[count[arr[i]]-1] = arr[i];

--count[arr[i]];

}

// Copy the output array to arr, so that arr now

// contains sorted characters

for (i = 0; arr[i]; ++i)

arr[i] = output[i];

}

int main()

{

char arr[] = "prateekchauhan";

count_Sort(arr);

printf("Sorted character array: %s\n", arr);

return 0;

} Output:

Sorted character array: aaaceehhknprtu Miscellaneous: 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) It is not a comparison based algorithm.