Counting Sort in Data Structures

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 Dsa 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.

   

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.

   

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.

   

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.

   

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.

   

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

Read More - Data Structure Interview Questions for Experience

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

   Case	Time Complexity
   Best	O(n + k)
   Average	O(n + k)
   Worst	O(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 Free Data Structures And Algorithms Course.

Similar Sorting Algorithms

• Radix Sort
• Merge Sort
• Quick Sort
• Bucket Sort