Sorting is one of the most important tasks in programming and data processing. Whenever you want to organize a collection of numbers or arrange data in a specific order, sorting algorithms come into play. In C programming, there are several algorithms available to perform sorting, and each one has its own advantages. Among them, Counting Sort stands out for its simplicity and speed when dealing with non-negative integers.
with hands-on learning.
get the skills and confidence to land your next move.
Counting Sort is not a comparison-based algorithm like Bubble Sort or Quick Sort. Instead, it works by counting the occurrences of each element and using that information to place elements directly in their correct positions. This makes it extremely efficient for datasets with a known, limited range of values. If you’ve ever wondered how sorting can be done without repeated comparisons, Counting Sort provides a clear and clever example.
Program 1: Simple Counting Sort Using Loops
The first version of Counting Sort uses basic loops. This approach is straightforward and helps beginners understand how the algorithm works internally.
#include <stdio.h>
void countingSort(int arr[], int n) {
int output[n];
int max = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max)
max = arr[i];
}
int count[max + 1];
for (int i = 0; i <= max; i++)
count[i] = 0;
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[] = {4, 2, 2, 8, 3, 3, 1};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array:\n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
countingSort(arr, n);
printf("Sorted array:\n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}In this program, the algorithm first finds the largest element in the array. Then it creates a counting array to keep track of how many times each element appears. Using this information, the program calculates the correct position of each element in the output array. The result is a neatly sorted list of numbers without any comparisons between individual elements. For beginners, this approach shows how logic and counting can replace repetitive comparisons in sorting.
Program 2: Counting Sort Using Recursion
This version introduces recursion to the Counting Sort process. Although Counting Sort is typically implemented with loops, recursion can also be used to make the logic more modular and to help students understand recursive problem solving in C.
#include <stdio.h>
void recursiveCopy(int arr[], int output[], int i, int n) {
if (i == n)
return;
arr[i] = output[i];
recursiveCopy(arr, output, i + 1, n);
}
void countingSortRecursive(int arr[], int n) {
int output[n];
int max = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max)
max = arr[i];
}
int count[max + 1];
for (int i = 0; i <= max; i++)
count[i] = 0;
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]]--;
}
recursiveCopy(arr, output, 0, n);
}
int main() {
int arr[] = {9, 4, 1, 7, 9, 1, 2, 0};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array:\n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
countingSortRecursive(arr, n);
printf("Sorted array:\n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}In this recursive version, the program works the same way as the loop-based version but uses a recursive function to copy the sorted output back into the original array. This helps learners see how recursion can simplify certain repetitive tasks. It also strengthens understanding of how function calls and base cases work in C. The logic of Counting Sort remains consistent, but the use of recursion adds a new learning dimension.
Program 3: Counting Sort with User Input
This program allows the user to enter their own numbers, making it interactive and more practical. It’s a good exercise for beginners who want to combine user input handling with sorting logic.
#include <stdio.h>
void countingSort(int arr[], int n) {
int output[n];
int max = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max)
max = arr[i];
}
int count[max + 1];
for (int i = 0; i <= max; i++)
count[i] = 0;
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 n;
printf("Enter number of elements: ");
scanf("%d", &n);
int arr[n];
printf("Enter %d elements (non-negative integers):\n", n);
for (int i = 0; i < n; i++)
scanf("%d", &arr[i]);
countingSort(arr, n);
printf("Sorted array:\n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}Here, the program reads the number of elements and their values directly from the user. It then applies the Counting Sort algorithm to arrange them in ascending order. This version is especially useful for beginners because it connects sorting logic to real-world input and output handling. By entering different values, learners can test how the algorithm behaves with various types of data.
Program 4: Counting Sort That Handles Negative Numbers
Now comes the interesting part—handling negative numbers. Normally, Counting Sort doesn’t work with negative integers because array indexes can’t be negative. However, we can easily fix this by shifting all numbers by the smallest (negative) value before sorting, and then shifting them back after sorting.
#include <stdio.h>
void countingSortWithNegatives(int arr[], int n) {
int output[n];
int max = arr[0], min = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max) max = arr[i];
if (arr[i] < min) min = arr[i];
}
int range = max - min + 1;
int count[range];
for (int i = 0; i < range; i++)
count[i] = 0;
for (int i = 0; i < n; i++)
count[arr[i] - min]++;
for (int i = 1; i < range; i++)
count[i] += count[i - 1];
for (int i = n - 1; i >= 0; i--) {
output[count[arr[i] - min] - 1] = arr[i];
count[arr[i] - min]--;
}
for (int i = 0; i < n; i++)
arr[i] = output[i];
}
int main() {
int arr[] = {-5, -10, 0, -3, 8, 5, -1, 10};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array:\n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
countingSortWithNegatives(arr, n);
printf("Sorted array:\n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}This version introduces a simple adjustment to handle negative integers. By finding both the minimum and maximum values, the program calculates the total range. It then shifts all values based on the smallest number to make them positive for counting. After sorting, the algorithm restores them to their original values. This modification allows Counting Sort to work with any integer array, whether it contains positive or negative numbers.
Frequently Asked Questions (FAQ)
The following section answers some common questions beginners often have about Counting Sort.
Can Counting Sort handle negative numbers?
Yes, by adjusting the algorithm to account for the smallest (negative) value and shifting all elements temporarily, Counting Sort can handle negative numbers easily.
Why is Counting Sort fast?
Counting Sort doesn’t compare elements directly. It counts occurrences and calculates positions mathematically, making it faster for certain types of data.
When should I use Counting Sort?
It’s best used when the range of numbers is not too large compared to the number of elements.
What is the time complexity of Counting Sort?
The time complexity is O(n + k), where n is the number of elements and k is the range between the smallest and largest values.
Conclusion
Counting Sort is a simple yet powerful algorithm that shows how we can sort data without comparing elements. It’s particularly effective when the range of input numbers is small compared to the number of elements. For beginners learning C programming, implementing Counting Sort is an excellent way to understand arrays, loops, and how mathematical counting can lead to efficient sorting.
Whether you prefer using loops or recursion, the logic behind Counting Sort remains the same — counting, positioning, and outputting in order. Keep practicing this algorithm with different inputs to strengthen your understanding. Once you grasp this concept, you’ll find it much easier to learn and appreciate more complex sorting algorithms in the future.
