Algorithm
Counting Sort is an integer sorting algorithm that operates in linear time complexity. It is not a comparison-based sorting algorithm, which means it doesn't rely on comparing elements to each other. Instead, it exploits the fact that the input elements are integers within a specific range.
The basic idea behind Counting Sort is to count the occurrences of each element in the input and then use that information to place the elements in their sorted order. Here's a step-by-step explanation of how Counting Sort works:
-
Counting Phase:
- Find the range of input elements (minimum and maximum values).
- Create an auxiliary array (count array) to store the count of each element in the input range.
- Traverse the input array and increment the count for each element in the count array.
-
Cumulative Counting Phase:
- Modify the count array by updating each element to represent the cumulative count of elements before it.
- This step helps determine the correct position of each element in the sorted output.
-
Sorting Phase:
- Create an output array to store the sorted elements.
- Traverse the input array in reverse order (to maintain stability) and use the cumulative count array to determine the correct position of each element in the output array.
- Decrease the count of the corresponding element in the count array after placing it in the output array.
-
Output Phase:
- The output array now contains the sorted elements.
Code Examples
#1 Counting Sort implement in Python
Code -
Python Programming
def counting_sort(arr):
# Find the maximum value in the array to determine the range
max_value = max(arr)
# Create a count array to store the count of each element
count = [0] * (max_value + 1)
# Count the occurrences of each element in the array
for num in arr:
count[num] += 1
# Update the count array to store the cumulative count
for i in range(1, max_value + 1):
count[i] += count[i - 1]
# Create a result array to store the sorted elements
result = [0] * len(arr)
# Place the elements in the result array according to their count
for num in reversed(arr):
result[count[num] - 1] = num
count[num] -= 1
return result
# Example usage:
arr = [4, 2, 3, 1, 4, 2, 1]
sorted_arr = counting_sort(arr)
print("Original array:", arr)
print("Sorted array:", sorted_arr)
#2 Counting Sort implement in Java
Code -
Java Programming
import java.util.Arrays;
public class CountingSort {
public static void countingSort(int[] array) {
if (array == null || array.length < = 1) {
return; // No need to sort
}
// Find the maximum value in the array
int max = Arrays.stream(array).max().getAsInt();
// Create a counting array to store the count of each element
int[] countArray = new int[max + 1];
// Count the occurrences of each element in the input array
for (int value : array) {
countArray[value]++;
}
// Update the counting array to store the cumulative count
for (int i = 1; i < countArray.length; i++) {
countArray[i] += countArray[i - 1];
}
// Create a temporary array to store the sorted result
int[] resultArray = new int[array.length];
// Build the sorted array using the counting array
for (int i = array.length - 1; i >= 0; i--) {
int value = array[i];
int index = countArray[value] - 1;
resultArray[index] = value;
countArray[value]--;
}
// Copy the sorted array back to the original array
System.arraycopy(resultArray, 0, array, 0, array.length);
}
public static void main(String[] args) {
int[] array = {4, 2, 7, 1, 9, 5, 3};
System.out.println("Original array: " + Arrays.toString(array));
countingSort(array);
System.out.println("Sorted array: " + Arrays.toString(array));
}
}
#3 Counting Sort implement in C
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
void countingSort(int arr[], int n) {
// Find the maximum element to determine the range of counting array
int max = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
// Create and initialize the counting array
int *count = (int *)malloc((max + 1) * sizeof(int));
if (count == NULL) {
fprintf(stderr, "Memory allocation failed\n");
exit(1);
}
for (int i = 0; i < = max; i++) {
count[i] = 0;
}
// Count the occurrences of each element
for (int i = 0; i < n; i++) {
count[arr[i]]++;
}
// Modify the counting array to store the position of each element
for (int i = 1; i < = max; i++) {
count[i] += count[i - 1];
}
// Create a temporary array to store the sorted result
int *output = (int *)malloc(n * sizeof(int));
if (output == NULL) {
fprintf(stderr, "Memory allocation failed\n");
exit(1);
}
// Build the output array
for (int i = n - 1; i >= 0; i--) {
output[count[arr[i]] - 1] = arr[i];
count[arr[i]]--;
}
// Copy the sorted elements back to the original array
for (int i = 0; i < n; i++) {
arr[i] = output[i];
}
// Free the dynamically allocated memory
free(count);
free(output);
}
// Function to print an array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {4, 2, 10, 1, 5, 3};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
printArray(arr, n);
countingSort(arr, n);
printf("Sorted array: ");
printArray(arr, n);
return 0;
}
#4 Counting Sort implement in C++
Code -
C++ Programming
#include <iostream>
#include <vector>
void countingSort(std::vector<int>& arr) {
// Find the maximum element in the array
int maxElement = *std::max_element(arr.begin(), arr.end());
// Create a count array to store the count of each element
std::vector<int> count(maxElement + 1, 0);
// Count the occurrences of each element in the array
for (int i = 0; i < arr.size(); ++i) {
count[arr[i]]++;
}
// Update the count array to store the cumulative count
for (int i = 1; i < = maxElement; ++i) {
count[i] += count[i - 1];
}
// Create a temporary array to store the sorted result
std::vector<int> result(arr.size());
for (int i = arr.size() - 1; i >= 0; --i) {
result[count[arr[i]] - 1] = arr[i];
count[arr[i]]--;
}
// Copy the sorted result back to the original array
for (int i = 0; i < arr.size(); ++i) {
arr[i] = result[i];
}
}
int main() {
std::vector<int> arr = {4, 2, 2, 8, 3, 3, 1};
std::cout << "Original array: ";
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
countingSort(arr);
std::cout << "Sorted array: ";
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
Demonstration
Counting Sort Data Structure and Algorithm