Counting Sort Algorithm

In this tutorial, we will learn about the Quick sort algorithm.

Sorting is one of the fundamental operations in computer science, and there are numerous sorting algorithms available. Merge sort is one such algorithm, which is efficient and widely used in programming languages. In this article, we will discuss the merge sort algorithm and its implementation in C++, Java, and Python.

Counting Sort Algorithm is an efficient algorithm used to sort a collection of integers. It works by counting the number of occurrences of each element in the input array and then using this information to reconstruct a sorted array. Counting Sort is a non-comparison-based sorting algorithm and has a time complexity of O(n+k), where k is the range of the input data.

In this article, we will explore the implementation of Counting Sort in C++, Java, and Python, along with an explanation of each pass of the algorithm.

C++ Implementation of Counting Sort:

void countingSort(int arr[], int n, int max_value) {
    int count[max_value + 1] = {0};

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

    int j = 0;
    for (int i = 0; i <= max_value; i++) {
        while (count[i] > 0) {
            arr[j++] = i;
            count[i]--;
        }
    }
}

The C++ implementation of Counting Sort takes an array of integers, the length of the array, and the maximum value of any element in the array as input. The function first creates an array called count of size max_value + 1 and initializes all its values to 0. Then it loops through the input array and increments the value in the count array corresponding to the current element in the input array. Next, the function iterates over the count array and reconstructs the sorted array by iterating through the count array and outputting the index i a number of times equal to the count of i in the count array.

Java Implementation of Counting Sort:

public static void countingSort(int[] arr, int max_value) {
    int[] count = new int[max_value + 1];

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

    int j = 0;
    for (int i = 0; i <= max_value; i++) {
        while (count[i] > 0) {
            arr[j++] = i;
            count[i]--;
        }
    }
}

The Java implementation of Counting Sort is similar to the C++ implementation. The function takes an array of integers and the maximum value of any element in the array as input. The function creates an array called count of size max_value + 1 and initializes all its values to 0. Then it loops through the input array and increments the value in the count array corresponding to the current element in the input array. Next, the function iterates over the count array and reconstructs the sorted array by iterating through the count array and outputting the index i a number of times equal to the count of i in the count array.

Python Implementation of Counting Sort:

def counting_sort(arr):
    max_value = max(arr)
    count = [0] * (max_value + 1)

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

    j = 0
    for i in range(max_value + 1):
        while count[i] > 0:
            arr[j] = i
            j += 1
            count[i] -= 1

The Python implementation of Counting Sort is similar to the C++ and Java implementations. The function takes an array of integers as input. The function first determines the maximum value in the input array and creates an array called count of size max_value + 1 and initializes all its values to 0. Then it loops through the input array and increments the value in the count array corresponding to the current element in the input array. Next, the function iterates over the count array and reconstructs the sorted array by iterating through the count array and outputting the index i a number of times equal to the count of i in the count array.

Passes of the Algorithm:

Counting Sort has two passes:

1. Counting Pass: In this pass, the algorithm loops through the input array and counts the number of occurrences of each element in the array. The algorithm creates a count array to store the count of each element. The size of the count array is determined by the maximum value of any element in the input array. The time complexity of this pass is O(n).
2. Reconstructing Pass: In this pass, the algorithm reconstructs the sorted array using the count array. The algorithm iterates over the count array and outputs the index i a number of times equal to the count of i in the count array. The time complexity of this pass is O(k).

Comparing each pass:

The counting pass of Counting Sort has a time complexity of O(n), which is faster than the O(nlogn) time complexity of comparison-based sorting algorithms like Merge Sort and Quick Sort. However, the reconstructing pass of Counting Sort has a time complexity of O(k), where k is the range of the input data. This means that Counting Sort becomes less efficient when the range of the input data is large. In contrast, Merge Sort and Quick Sort have a worst-case time complexity of O(nlogn), which is not affected by the range of the input data.

In terms of space complexity, Counting Sort has a space complexity of O(k), which is the size of the count array. This means that Counting Sort requires more memory than Merge Sort and Quick Sort, which have a space complexity of O(n).

Conclusion

Counting Sort is an efficient algorithm used to sort a collection of integers. It has a time complexity of O(n+k), where k is the range of the input data. Counting Sort is faster than comparison-based sorting algorithms like Merge Sort and Quick Sort for small input sizes or when the range of the input data is small. However, Counting Sort becomes less efficient when the range of the input data is large. Counting Sort has a space complexity of O(k), which is larger than the space complexity of Merge Sort and Quick Sort. Counting Sort is a stable sorting algorithm, meaning that it preserves the relative order of equal elements in the input array.