counting sort

Counting sort is an integer sorting algorithm which sorts the input array or collection of objects according to the keys. The algorithm takes the advantage of known range of objects. this range is used to sort the objects. According to wikipedia “It operates by counting the number of objects that have each distinct key value, and using arithmetic on those counts to determine the positions of each key value in the output sequence. Its running time is linear in the number of items and the difference between the maximum and minimum key values, so it is only suitable for direct use in situations where the variation in keys is not significantly greater than the number of items.

Here is sample code in c for counting sort algorithm:

counting sort step by step:
input array = { 1, 3, 1, 4}
<1)max element is 4
2)min element is 1
3)range will be (4 -1) +2 = 5
4) Now Make an array of length 5 and initialize with zero.
count[5] = {0,0,0,0,0};
5) Now all index of count[5] is having 0. the index of count is key for our algo.
calculate the histogram of key frequencies.
6) like as our input array is { 1, 3, 1, 4} then if we select first element 1,
then the index 1 of count[5] will be incremented by 1. same as if we select element
3 of  our input array { 1, 3, 1, 4} then the index of count[3] will be incremented by 1.
7) after step 3 the count[5] will be {0 2 0 1 1}
The value at index represents the number of occurrence of keys i.e count[0] is 0, it refers 0 is not present in
input array. count[1] is 2 refers 1 is present in input array with two times.
8) calculate the starting index for each key.
  count[5] = {0 0 2 2 3}
9) Make an output array as same size as input array.
 copy to output array, preserving order of inputs with equal keys.
 Print the output array.

#include<stdio.h>
#include<string.h>

void Countsort (int arr[], int k, int size)
{
  int count[k];
  memset (count, 0, sizeof (count));
/*# calculate the histogram of key frequencies*/
   int i = 0;
   for (i; i <size; i++)
   {
        ++count[arr[i]];
   }

/* make an output array */
int output_arr[size];
memset (output_arr, 0, sizeof (output_arr));

/*calculate the starting index for each key*/
int total = 0;
int oldCount = 0;
        for (i = 0; i < k; i++)
        {
           oldCount = count[i];
           count[i] = total;
           total += oldCount;
        }
/* copy to output array, preserving order of inputs with equal keys */
for (i = 0; i< size; i++)
{
        output_arr[count[arr[i]]] = arr[i];
        count[arr[i]] += 1;
}
/*print output */
for (i = 0; i < size; i++)
printf ("%d ", output_arr[i]);
printf ("\n");
}

int get_count_range (int arr[], int size)
{
      int min = arr[0];
      int max = arr[0];
      int i = 1;
      for (i; i <= size - 1; i++)
      {
          if (max < arr[i])
          {
              max = arr[i];
          }

         if (min > arr[i])
         {
            min = arr[i];
         }
      }
     return (max - min);
}
int main ()
{
    int k = 0;
    int arr_size = 0;
    int arr[] = { 1, 3, 1, 4};
    arr_size = sizeof (arr) / sizeof (arr[0]);
k = get_count_range (arr, arr_size) + 2;
int i =0;
      // call counting sort algo
          Countsort (arr, k, arr_size);
return 0;
}

Analysis of counting sort:

O(n+k) where n is the number of size of input array and k is the range of input as algorithm implementation takes simple for loops. one is used for initializing counting array and second one is used for calculating prefix sum of counting array for calculating starting position of each key.



Related Contents to follow