Browse Tutorials
Counting Sort in Data Structures

Counting Sort in Data Structures

29 Dec 2023
Intermediate
1.02K Views
15 min read
Learn via Video Course & by Doing Hands-on Labs

Data Structures & Algorithms For Beginners Free Course

Counting Sort: An Overview

In this DSA tutorial, we will learn about the counting sort algorithm that works by counting each distinct element in the array. To further enhance your understanding and application of counting sort concepts, consider enrolling in the best Data Structures and Algorithms Course, to gain comprehensive insights into effective data structure utilization for improved problem-solving and time management.

What is Counting Sort in Data Structures?

Counting sort is a linear non-comparison-based sorting algorithm that works great for a specific range of values. It counts the number of occurrences of each distinct element in an array and uses that information to determine the sorted order. The count is stored in an auxiliary array and the sorting is done by mapping the count as an index of the auxiliary array.

Counting Sort Algorithm

countingSort(array, size)
  max <- find largest element in array
  initialize count array with all zeros
  for j <- 0 to size
    find the total count of each unique element and 
    store the count at jth index in count array
  for i <- 1 to max
    find the cumulative sum and store it in count array itself
  for j <- size down to 1
    restore the elements to array
    decrease count of each element restored by 1

Working of the Counting Sort Algorithm

  1. Find out the maximum element max from the given array.

    Initial array

  2. Initialize an array of length max+1 with all elements 0. This array is used for storing the count of the elements in the array.

    count array

  3. Store the count of each element at their respective index in the count array

    For example: if the count of element 3 is 2 then, 2 is stored in the 3rd position of the count array. If element 6 is not present in the array, then 0 is stored in 6th position.

    Count of each element stored

  4. Store the cumulative sum of the elements of the count array. It helps in placing the elements into the correct index of the sorted array.

    Cumulative Count

  5. Find the index of each element of the original array in the count array. This gives the cumulative count. Place the element at the index calculated as shown in the figure below.

    Counting Sort

  6. After placing each element in its correct position, decrease its count by one.

Implementation of Counting Sort in Different Languages in Data Structures


def countingSort(array):
    size = len(array)
    output = [0] * size

    # Initialize count array
    count = [0] * 10

    # Store the count of each element in the count array
    for i in range(0, size):
        count[array[i]] += 1

    # Store the cumulative count
    for i in range(1, 10):
        count[i] += count[i - 1]

    # Find the index of each element of the original array in the count array
    # Place the elements in the output array
    i = size - 1
    while i >= 0:
        output[count[array[i]] - 1] = array[i]
        count[array[i]] -= 1
        i -= 1

    # Copy the sorted elements into the original array
    for i in range(0, size):
        array[i] = output[i]

def print_list(arr):
    for i in range(len(arr)):
        print(arr[i], end=" ")
    print()

arr = [5, 3, 3, 9, 4, 4, 1]
print("Original array is:", end=" ")
print_list(arr)

countingSort(arr)

print("Sorted Array in Ascending Order:", end=" ")
print_list(arr)
    

public class CountingSort {
    static void countingSort(int[] array) {
        int size = array.length;
        int[] output = new int[size];

        // Initialize count array
        int[] count = new int[10];

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

        // Store the cumulative count
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        // Find the index of each element of the original array in the count array
        // Place the elements in the output array
        int i = size - 1;
        while (i >= 0) {
            output[count[array[i]] - 1] = array[i];
            count[array[i]] -= 1;
            i -= 1;
        }

        // Copy the sorted elements into the original array
        System.arraycopy(output, 0, array, 0, size);
    }

    static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 3, 9, 4, 4, 1};
        System.out.print("Original array is: ");
        printArray(arr);

        countingSort(arr);

        System.out.print("Sorted Array in Ascending Order: ");
        printArray(arr);
    }
}
    

#include <iostream>
using namespace std;

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

    // Initialize count array
    int count[10] = {0};

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

    // Store the cumulative count
    for (int i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

    // Find the index of each element of the original array in the count array
    // Place the elements in the output array
    int i = size - 1;
    while (i >= 0) {
        output[count[array[i]] - 1] = array[i];
        count[array[i]] -= 1;
        i -= 1;
    }

    // Copy the sorted elements into the original array
    copy(output, output + size, array);
}

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

int main() {
    int arr[] = {5, 3, 3, 9, 4, 4, 1};
    int size = sizeof(arr) / sizeof(arr[0]);

    cout << "Original array is: ";
    printArray(arr, size);

    countingSort(arr, size);

    cout << "Sorted Array in Ascending Order: ";
    printArray(arr, size);

    return 0;
}
    

Output

 Original array is: 5 3 3 9 4 4 1 
Sorted Array in Ascending Order: 1 3 3 4 4 5 9 

Complexity Analysis of Counting Sort Algorithm

  1. Time Complexity
    CaseTime Complexity
    Best O(n + k)
    Average O(n + k)
    WorstO(n + k)
  2. Space Complexity: Here, we use an additional array of size K, which is the maximum element of the array to store the frequencies of all the elements in the range [0, K]. Thus, the space complexity largely depends on the value of K, and is equivalent to O(K).

Applications of Counting Sort Algorithm

  1. Counting sort is used when there are smaller integers with multiple counts.
  2. When you need an algorithm with linear complexity.

Advantages of Counting Sort Algorithm

  1. Counting sort generally performs faster than all comparison-based sorting algorithms, such as merge sort and quick sort, if the range of input is of the order of the number of inputs.
  2. Counting sort is easy to code.
  3. Counting sort is a stable algorithm i.e. it maintains the relative order of elements with equal values.

Disadvantages of Counting Sort Algorithm

  1. Counting sort doesn’t work on decimal values. It is designed for sorting integer values.
  2. Counting sort is inefficient if the range of values to be sorted is very large.
  3. Counting sort is not an in-place sorting algorithm. It uses extra space for sorting the array elements.
Summary

So, here we saw every aspect of the counting sort algorithm in data structures. The power of Counting Sort is its linear running time. It works differently compared to the sorting algorithms we have learned so far. To apply your knowledge of counting sort algorithm, enroll in our DSA Programming Course.

Similar Sorting Algorithms

FAQs

Q1. Is counting sort stable?

Yes, counting sort is an example of a stable sorting algorithm, as it does not change the relative order of elements of the same value in the input.

Q2. Is counting sort an in-place sorting algorithm?

No, counting sort is not an in-place sorting algorithm. In counting sort, we use an auxiliary array of the size of the range of data.

Q3. Where should counting sort be used?

Counting sort works better than the other comparison-based sorting algorithms when we have to sort many numbers that lie in a comparatively smaller range on the number line.
Accept cookies & close this