Count sort algorithm and it's exampels

In this tutorial, you'll find out how to count sort algorithm works. you'll also find practical samples of count sort in C, C ++, Java, and Python.

Count sorting may be an algorithm that sorts the weather of an array by counting the number of occurrences of every unique element within the array. The count is stored in an auxiliary array and sorting is completed by mapping the count as an index of the auxiliary array.

 

How does the count sort Algorithm work?

•  Find the utmost element (be it max) from the given array.

counting sort in c

• Initialize an array of max length + 1 with all 0 elements. This array is employed to store the number of elements within the array.

count sort algorithm

• Store the amount of every element at their respective index within the count array

count sort algorithm

For example: if the count of element 3 is 2 then, 2 is stored within the 3rd position of the count table. If element "5" isn't present within the array, then 0 is stored in the 5th position.

• Store the cumulative sum of things within the count array. This helps to put the weather within the correct index of the sorted array.

counting sort

• Find the index of every element within the original array within the count array. this provides the cumulative count. Place the element at the calculated index as shown within the figure below.

counting sort algorithm in c programming

• After placing each item in its correct position, decrease its number by one

Counting Sort Algorithm

Counting Sort Algorithm

C Program For Counting Sort Algorithm

// Counting sort in C programming

#include <stdio.h>

void countingSort(int array[], int size) {
  int output[10];

  // Find the largest element of the array
  int max = array[0];
  for (int i = 1; i < size; i++) {
    if (array[i] > max)
      max = array[i];
  }

  int count[10];

  // Initialize count array with all zeros.
  for (int i = 0; i <= max; ++i) {
    count[i] = 0;
  }

  // Store the count of each element
  for (int i = 0; i < size; i++) {
    count[array[i]]++;
  }

  for (int i = 1; i <= max; i++) {
    count[i] += count[i - 1];
  }


  for (int i = size - 1; i >= 0; i--) {
    output[count[array[i]] - 1] = array[i];
    count[array[i]]--;
  }

 
  for (int i = 0; i < size; i++) {
    array[i] = output[i];
  }
}

void printArray(int array[], int size) {
  for (int i = 0; i < size; ++i) {
    printf("%d  ", array[i]);
  }
  printf("\n");
}


int main() {
  int array[] = {4, 2, 2, 8, 3, 3, 1};
  int n = sizeof(array) / sizeof(array[0]);
  countingSort(array, n);
  printArray(array, n);
}

counting sort of time complexity

Time complexities:

There are mainly four main loops. (The look for the most important value are often done outside of the function.)

Overall complexity = O (max) + O (size) + O (max) + O (size) = O (max + size)

•  Worst case complexity: O (n + k)
•  Best case complexity: O (n + k)
•  Average complexity of cases: O (n + k)

In all of the above cases, the complexity is that the same because regardless of how the weather is placed within the array, the algorithm goes through n + k times.

There is no comparison between items, so it's better than comparison based sorting techniques. But, it's bad if the integers are very large because the array of that size must be created.

Space complexity For counting sort algorithm:

The spatial complexity of count sorting is O (max). The greater the range of elements, the greater the complexity of the space.

Counting sorting Applications

•  there are smaller integers with multiple counts.

•  linear complexity is the need.