Sorting is a fundamental concept in computer science, and there are many sorting algorithms to choose from. One of the most efficient algorithms for sorting integers within a limited range is Counting Sort. In this blog, we will explore how Counting Sort works and write its implementation in C.
PermalinkWhat is Counting Sort?
Counting Sort is a non-comparison-based sorting algorithm. Instead of comparing elements, it uses the frequency (or count) of each unique element in the array to determine their sorted position. It works best when:
The range of input values is not excessively large.
The input contains integers or data that can be mapped to integers (like characters).
Counting Sort is particularly efficient for scenarios where data falls within a predictable and narrow range, making it a great choice for specific use cases like sorting grades, ages, or digits of numbers.
PermalinkHow Does Counting Sort Work?
Here are the steps for Counting Sort:
Find the Range: Determine the maximum value in the array (this defines the range of the count array).
Create the Count Array: Create an auxiliary array (count array) to store the frequency of each element.
Cumulative Count: Update the count array so that each index contains the sum of its own count and all previous counts. This step helps determine the position of each element in the sorted array.
Build the Output Array: Traverse the original array in reverse order to maintain stability and use the count array to place elements in their correct position in a new output array.
Copy Back: Copy the sorted elements from the output array back to the original array.
PermalinkKey Points to Note
Stability: Counting Sort is stable, meaning that it preserves the relative order of elements with the same value.
Space Complexity: The algorithm uses additional space for the count array and output array, making its space complexity O(n + k), where
n
is the size of the input array andk
is the range of input values.Time Complexity: The time complexity is O(n + k), making it very efficient for small ranges of
k
.
PermalinkImplementation of Counting Sort in C
Here’s the code for Counting Sort in C:
#include <stdio.h>
#include <string.h>
void countingSort(int arr[], int n) {
// Find the maximum value in the array
int max = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max)
max = arr[i];
}
// Create and initialize the count array
int count[max + 1];
memset(count, 0, sizeof(count));
// Count the occurrences of each element
for (int i = 0; i < n; i++) {
count[arr[i]]++;
}
// Update the count array to store cumulative counts
for (int i = 1; i <= max; i++) {
count[i] += count[i - 1];
}
// Create the output array
int output[n];
// Build the sorted output array
for (int i = n - 1; i >= 0; i--) {
output[count[arr[i]] - 1] = arr[i];
count[arr[i]]--;
}
// Copy the sorted array back to the original array
for (int i = 0; i < n; i++) {
arr[i] = output[i];
}
}
// Utility function to print an array
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {4, 2, 2, 8, 3, 3, 1};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: \n");
printArray(arr, n);
countingSort(arr, n);
printf("\nSorted array: \n");
printArray(arr, n);
return 0;
}
PermalinkExplanation of the Code
Finding the Maximum Value: The maximum value determines the size of the count array.
Count Array:
The count array is initialized to zero.
Each index represents a value in the input array, and the value at that index represents the frequency of the element.
Cumulative Count: This step ensures that each index in the count array contains the position of the last occurrence of the element in the sorted order.
Building the Output Array: Traversing the input array in reverse ensures the stability of the algorithm.
Copy Back: The sorted elements are copied back to the original array.
PermalinkExample Walkthrough
PermalinkInput Array:
arr = {4, 2, 2, 8, 3, 3, 1}
PermalinkSteps:
Find the Range: Max value is
8
.Count Array: After counting occurrences:
[0, 1, 2, 2, 1, 0, 0, 0, 1]
Cumulative Count: After cumulative count:
[0, 1, 3, 5, 6, 6, 6, 6, 7]
Output Array: Using the count array:
[1, 2, 2, 3, 3, 4, 8]
Final Result: Sorted array:
[1, 2, 2, 3, 3, 4, 8]
PermalinkAdvantages and Disadvantages
PermalinkAdvantages:
Very fast for small ranges.
Simple to implement for integer or character data.
PermalinkDisadvantages:
Inefficient for large ranges due to high space usage.
Cannot be used directly for non-integer data.
PermalinkIn Short
Counting Sort is a powerful algorithm when the range of input values is limited and predictable. It is fast and stable, making it an excellent choice for specific sorting tasks. However, for larger or more general cases, other sorting algorithms like Quick Sort or Merge Sort may be better suited.