Search

# 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.

8 views0 comments

See All

# programmersdoor@gmail.com

©2023 by Programmers Door