Counting Sort Algorithm

Last updated on July 13th, 2024 at 10:27 am

We will discuss the Counting Sort Algorithm, pseudo code, Code implementation of Counting Sort in C, C++, Java, JavaScript, Python, advantages & disadvantages, and time & space complexity of Counting Sort.

1. What is Counting Sort Algorithm?

Counting Sort is an integer sorting algorithm that works by counting the occurrences of each unique element in the input array. It then calculates the position of each element in the sorted array. It is efficient for sorting integers within a small range.

1. Counting Sort is efficient if the range of input data is not significantly greater than the number of objects to be sorted.
2. It is not a comparison-based sorting. Its running time complexity is O(n) with space proportional to the range of data.
3. This can be used as a subroutine to some other algorithm. It is often used as a subroutine to another sorting algorithm, such as radix sort.
4. It uses partial hashing to count the occurrence of the data object in O(1).
5. It can be extended to work for negative inputs also.

2. Pseudocode for Counting Sort

COUNTING_SORT(A[], B[], k)
1. for i = 1 to k do
2. C[i] = 0 
3. for j = 1 to length(A) do 
4. C[A[j]] = C[A[j]] + 1
5. for 2 = 1 to k do
6. C[i] = C[i] + C[i-1] 
7. for j = 1 to length(A) do 
       B[C[A[j]]] = A[j] 
       C[A[j]] = C[A[j]] - 1

3. Code Implementation of Bubble Sort

3.1 Counting Sort in C

#include <stdio.h>
#include <string.h>

void countingSort(int arr[], int n, int max) {
    int count[max + 1];
    int output[n];
    
    memset(count, 0, sizeof(count));

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

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

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

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

int main() {
    int arr[] = {1, 4, 1, 2, 7, 5, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    int max = 7;  // maximum element in arr

    countingSort(arr, n, max);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

3.1.1 Explanation of Counting Sort

1. countingSort: Main function to perform counting sort.
   • count: Array to store the count of each unique element.
   • output: Array to store the sorted output.
   • memset: Initializes the count array to zero.
2. First loop: Counts occurrences of each element.
3. Second loop: Modifies the count array to store the cumulative count.
4. Third loop: Constructs the output array using the count array.
5. Final loop: Copies the sorted elements back to the original array

3.2 Counting Sort in C++

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

void countingSort(vector<int>& arr, int max) {
    int n = arr.size();
    vector<int> count(max + 1, 0);
    vector<int> output(n);

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

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

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

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

int main() {
    vector<int> arr = {1, 4, 1, 2, 7, 5, 2};
    int max = 7;  // maximum element in arr

    countingSort(arr, max);

    cout << "Sorted array: ";
    for (int num : arr) {
        cout << num << " ";
    }
    return 0;
}

3.3 Counting Sort in Java

import java.util.Arrays;

public class CountingSort {
    public static void main(String[] args) {
        int[] arr = {1, 4, 1, 2, 7, 5, 2};
        int max = 7;  // maximum element in arr

        countingSort(arr, max);

        System.out.println("Sorted array: " + Arrays.toString(arr));
    }

    public static void countingSort(int[] arr, int max) {
        int n = arr.length;
        int[] count = new int[max + 1];
        int[] output = new int[n];

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

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

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

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

3.4 Counting Sort in JavaScript

function countingSort(arr, max) {
    const count = new Array(max + 1).fill(0);
    const output = new Array(arr.length);

    for (let i = 0; i < arr.length; i++) {
        count[arr[i]]++;
    }

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

    for (let i = arr.length - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }

    for (let i = 0; i < arr.length; i++) {
        arr[i] = output[i];
    }
}

const arr = [1, 4, 1, 2, 7, 5, 2];
const max = 7;  // maximum element in arr

countingSort(arr, max);

console.log("Sorted array:", arr);

3.5 Counting Sort in Python

def countingSort(arr, max):
    count = [0] * (max + 1)
    output = [0] * len(arr)

    for num in arr:
        count[num] += 1

    for i in range(1, max + 1):
        count[i] += count[i - 1]

    for num in reversed(arr):
        output[count[num] - 1] = num
        count[num] -= 1

    for i in range(len(arr)):
        arr[i] = output[i]

arr = [1, 4, 1, 2, 7, 5, 2]
max = 7  # maximum element in arr

countingSort(arr, max)

print("Sorted array:", arr)

4. Advantages of Counting Sort

1. Linear Time Complexity: Counting Sort has a time complexity of O(n + k), where n is the number of elements and k is the range of input.
2. Stable Sort: Counting Sort preserves the relative order of equal elements.
3. Efficient for Small Range: It is very efficient when the range of input elements (k) is not significantly larger than the number of elements (n).

5. Disadvantages of Counting Sort

1. Limited Range: Counting Sort is not suitable for large ranges of numbers or non-integer data.
2. Space Complexity: The algorithm requires additional space for the count array, making it less space-efficient for large ranges.
3. Not Comparison-Based: Counting Sort cannot be used as a general-purpose sorting algorithm since it relies on the numerical range of the data.

6. Time and Space Complexity of Counting Sort

Time Complexity
Worse Case	O(n+k)
Best Case	O(n+k)
Average Case	O(n+k)
Space Complexity
Worst Case	O(max)

7. Applications of Counting Sort

Counting Sort is used when:

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

FAQs