Counting Sort

Here, We will discuss about Counting Sort in C, their algorithm, implementation code in C, time and space complexity, and their applications.

What is Counting Sort?

Counting Sort is a sorting algorithm but not a comparison sort algorithm.

The algorithm based on idea that sorting the elements of an array by frequencies of distinct/unique elements of the array.

Counting Sort becomes linear sorting which is better than comparison based sorting algorithm.

Counting Sort Algorithm

Sorting of elements of an array by frequencies of distinct elements of array. The count is stored in auxiliary array and the sorting is done by mapping its value as an index of the auxiliary array.

Counting Sort Code Implementation

Program code in C

#include<stdio.h> void countingsort(int arr[], int n) { int output[10]; //find the largest element of array int max = arr[0]; for(int i=1; i<n; i++) { if(arr[i] > max) max = arr[i]; } //the size of count must be at least (max+1) 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<n; i++) { count[arr[i]]++; } //store the cummulative count of each array for(int i=1; i<=max; i++) { count[i] += count[i-1]; } //find index of each elements of original array in count array and //place the elements in output array for(int i=n-1; i>=0; i--) { output[count[arr[i]]-1] = arr[i]; count[arr[i]]--; } //copy the sorted elements into original array for(int i=0; i<n; i++) { arr[i] = output[i]; } } //function to print array void printarray(int arr[], int n) { for(int i=0; i<n; i++) { printf("%d ", arr[i]); } printf("\n"); } //Driver code int main() { int data[] = {5, 2, 9, 5, 2, 3, 5}; int n = sizeof(data) / sizeof(data[0]); countingsort(data, n); printf("Sorted Array : ") printarray(data, n); }
Code language: C++ (cpp)

Output:

Sorted Array : 2 2 3 5 5 5 9
Code language: JavaScript (javascript)

Time and Space Complexity of Counting Sort

Time Complexity
Worse CaseO(n+k)
Best CaseO(n+k)
Average CaseO(n+k)

In all cases, the complexity is the same because no matter how the elements are placed in the array, the algorithm goes through (n+k) times.

Space Complexity
Worst CaseO(max)

Larger the range of elements, larger is the space complexity.

Applications of Counting Sort

Counting Sort is used when:

  • there are smaller integers with multiple counts.
  • linear complexity is the need.

Quick Sort

Here, We will discuss about Quick sort in C, their algorithm, implementation in C, time & space complexity and their applications. What is Quick Sort? Quick …
Read More

Merge Sort

Here, We will discuss about Merge Sort in C, their algorithm, implementation code in C, time and space complexity, and their applications. What is Merge Sort? Merge …
Read More

Bubble Sort

Here, We will learn about bubble sort in C, their algorithm, implementation in C, time & space complexity and their applications. What is Bubble Sort? Bubble Sort …
Read More

Selection Sort

Here, We will discuss about selection sort in C, their algorithm, implementation code in C, time and space complexity and their advantages. What is Selection Sort? Selection …
Read More

Insertion Sort

Here, We will learn about insertion sort in C, their algorithm, implementation code in C, time and space complexity and advantages.. What is Insertion sort? Insertion Sort …
Read More

Radix Sort

Here, We will discuss about Radix Sort in C, their algorithm, implementation code in C, time and space complexity, and their applications. What is …
Read More

Want to Contribute:-

If you like “To The Innovation” and want to contribute, you can mail your articles to [email protected]. See your articles on the main page and help other coders.