CountingSort_GL
  1. What is Counting sort
  2. Counting sort Pseudo-code
  3. Counting sort Algorithm
  4. Counting sort Algorithm Dry Run
  5. Counting sort Time Complexity
  6. Counting sort Space Complexity
  7. Counting sort in C
  8. Counting sort in Java
  9. Counting sort in C++
  10. Counting sort in Python

What is Counting Sort

Counting sort is a sorting technique which is based on the range of input value. It is used to sort elements in linear time. In Counting sort, we maintain an auxiliary array which drastically increases space requirement for the algorithm implementation

It works just like hashing, first, we calculate the max value in the input array, the array to be sorted. Then we count the number of occurrences of each array element from 0 to length-1 and assign it into the auxiliary array. This array is used again to retrieve the sorted version of the input array

It actually has linear time complexity but we can’t say that it’s the best algorithm because the space complexity is quite high and it is only suitable to use in a scenario where input array element range is close to the size of the array.

Counting Sort Pseudo-code

  • Iterate the input array and find the maximum value present in it.
  • Declare a new array of size max+1 with value 0
  • Count each and every element in the array and increment its value at the corresponding index in the auxiliary array created
  • Find cumulative sum is the auxiliary array we adding curr and prev frequency
  • Now the cumulative value actually signifies the actual location of the element in the sorted input array
  • Start iterating auxiliary array from 0 to max
  • Put 0 at the corresponding index and reduce the count by 1, which will signify the second position of the element if it exists in the input array
  • Now transfer array received in the above step in the actual input array

Counting Sort Algorithm

countingSort(arr, n)
  maximum <- find the largest element in arr
  create a count array of size maximum+1
  initialise count array with all 0's
  for i <- 0 to n
    find the total frequency/ occurrences of each element and 
    store the count at ith index in count arr
  
  for i <- 1 to maximum
    find the cumulative sum by adding current(i) and prev(i-1) count and store 
	it in count arr itself
  
  for j <- n down to 1
    copy the element back into the input array
    decrement count of each element copied by 1

Counting Sort Algorithm Dry Run

input:

01234
21142

First step – marking count array

01234
00000

After calculating all the frequency of every element

01234
02201

do cumulative sum

01234
02445

Now start iterating input array and check frequency array to map it to the output array 

Iteration 1

input:

01234
21142

cumulative sum

01234
02345

Output:

01234
00020
Iteration 2

input:

01234
21142

cumulative sum

01234
01345

Output:

01234
01020
Iteration 3

input:

01234
21142

cumulative sum

01234
00345

Output:

01234
11020
Iteration 4

input:

01234
21142

cumulative sum

01234
00334

Output:

01234
11024
Iteration 5

input:

01234
21142

cumulative sum

01234
00234

Output:

01234
11224

Now transfer the output to the input array

Counting Sort Time Complexity

  • Time is taken to find max say k
  • Count array initialization will take k time
  • To maintain count array again k time
  • Now linear iteration of the input array to do the actual sorting
  • Since all the above steps are fixed for no matter what the input array is, therefore best, average and worst time complexity will remain the same
  • Best Time Complexity : O(n+k)
  • Average Time Complexity : O(n+k)
  • Worst Time Complexity : O(n+k)

Counting Sort Space Complexity

  • Auxiliary space is required in Counting sort implementation as we have to create a count array of size max+1
  • Hence space complexity is: O(max)

Counting sort in C 

#include <stdio.h>

void countingSort(int arr[], int n) {
  int arr1[10];

  int x = arr[0];
  for (int i = 1; i < n; i++) {
    if (arr[i] > x)
      x = arr[i];
  }

  
  int count_arr[10];

  for (int i = 0; i <= x; ++i) {
    count_arr[i] = 0;
  }

  for (int i = 0; i < n; i++) {
    count_arr[arr[i]]++;
  }

  for (int i = 1; i <= x; i++) {
    count_arr[i] += count_arr[i - 1];
  }

 
  for (int i = n - 1; i >= 0; i--) {
    arr1[count_arr[arr[i]] - 1] = arr[i];
    count_arr[arr[i]]--;
  }

  for (int i = 0; i < n; i++) {
    arr[i] = arr1[i];
  }
}

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

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





Output of the program:
 1  2  2  3  3  4  8  

Learn about heap sort

Counting sort in Java

import java.util.Arrays;

class CountingSort {
  void countSort(int arr[], int n) {
    int[] arr1 = new int[n + 1];

    int x = arr[0];
    for (int i = 1; i < n; i++) {
      if (arr[i] > x)
        x = arr[i];
    }
    int[] count_arr = new int[x + 1];

    for (int i = 0; i < x; ++i) {
      count_arr[i] = 0;
    }

    for (int i = 0; i < n; i++) {
      count_arr[arr[i]]++;
    }

    for (int i = 1; i <= x; i++) {
      count_arr[i] += count_arr[i - 1];
    }

    for (int i = n - 1; i >= 0; i--) {
      arr1[count_arr[arr[i]] - 1] = arr[i];
      count_arr[arr[i]]--;
    }

    for (int i = 0; i < n; i++) {
      arr[i] = arr1[i];
    }
  }

  void display(int[] arr){
	for (int i = 0; i < arr.length; i++) {
		System.out.print(arr[i]+" ");
	}
  }
  
  public static void main(String args[]) {
    int[] arr = { 4, 2, 2, 8, 3, 3, 1 };
    int n = arr.length;
    CountingSort cs = new CountingSort();
    cs.countSort(arr, n);
    cs.display(arr);
  }
}







Output of the program:
 1 2 2 3 3 4 8 

Counting sort in C++


#include <iostream>
using namespace std;

void countSort(int arr[], int n) {
  
  int arr1[10];
  int count_arr[10];
  int x = arr[0];

  for (int i = 1; i < n; i++) {
    if (arr[i] > x)
      x = arr[i];
  }

  for (int i = 0; i <= x; ++i) {
    count_arr[i] = 0;
  }

  for (int i = 0; i < n; i++) {
    count_arr[arr[i]]++;
  }

  for (int i = 1; i <= x; i++) {
    count_arr[i] += count_arr[i - 1];
  }


  for (int i = n - 1; i >= 0; i--) {
    arr1[count_arr[arr[i]] - 1] = arr[i];
    count_arr[arr[i]]--;
  }

  for (int i = 0; i < n; i++) {
    arr[i] = arr1[i];
  }
}

void display(int arr[], int n) {
  for (int i = 0; i < n; i++)
    cout << arr[i] << " ";
  cout << endl;
}

int main() {
  int arr[] = {4, 2, 2, 8, 3, 3, 1};
  int n = sizeof(arr) / sizeof(arr[0]);
  countSort(arr, n);
  display(arr, n);
}







Output of the program:
 1 2 2 3 3 4 8 

Counting sort in Python

def countingSort(arr):
    n = len(arr)
    arr1 = [0] * n

    x = [0] * 10

    for i in range(0, n):
        x[arr[i]] += 1

    for i in range(1, 10):
        x[i] += x[i - 1]


    i = n - 1
    while i >= 0:
        arr1[x[arr[i]] - 1] = arr[i]
        x[arr[i]] -= 1
        i -= 1

    for i in range(0, n):
        arr[i] = arr1[i]


arr = [4, 2, 2, 8, 3, 3, 1]
countingSort(arr)
print(arr)


Output of the program:
 [1, 2, 2, 3, 3, 4, 8]

This brings us to the end of this article where we learned about heap sort. To get a free course on data structures and algorithms, click on the banner below. Also, visit the great learning academy to see all the free courses we are providing.

counting sort
0

LEAVE A REPLY

Please enter your comment!
Please enter your name here

seventeen + nine =