Sorting is one of the most important tasks in programming. It helps organize data so that it can be accessed, searched, or processed efficiently. One of the unique sorting techniques is Counting Sort, which is particularly fast when working with integers within a small range. Unlike comparison-based sorting algorithms such as Bubble Sort or Quick Sort, Counting Sort uses the frequency of elements to sort an array. This makes it very efficient for certain types of datasets.
with hands-on learning.
get the skills and confidence to land your next move.
Counting Sort works by counting how many times each element appears in the input array. Then, it calculates the correct position of each element in the sorted array. It’s widely used in applications like digit sorting, radix sort preprocessing, and organizing scores or small-range data. Beginners will find Counting Sort interesting because it introduces a different way of thinking about sorting without direct comparisons between elements.
Program 1: Simple Counting Sort
This first program shows a basic Counting Sort implementation for positive integers using loops. It is perfect for beginners to understand the fundamental concept of counting and placing elements.
using System;
class Program
{
static void CountingSort(int[] arr)
{
int max = arr[0];
for (int i = 1; i < arr.Length; i++)
if (arr[i] > max)
max = arr[i];
int[] count = new int[max + 1];
for (int i = 0; i < arr.Length; i++)
count[arr[i]]++;
int index = 0;
for (int i = 0; i < count.Length; i++)
while (count[i]-- > 0)
arr[index++] = i;
}
static void Main()
{
int[] arr = { 4, 2, 2, 8, 3, 3, 1 };
CountingSort(arr);
Console.WriteLine("Sorted array:");
foreach (int num in arr)
Console.Write(num + " ");
Console.WriteLine();
}
}In this program, we first find the largest element in the array, then create a counting array to store the frequency of each number. Finally, we rebuild the sorted array based on the counts. This approach is easy to understand and demonstrates how Counting Sort avoids element comparisons.
Program 2: Counting Sort with Negative Numbers
Counting Sort can also handle negative numbers by adjusting the counting array indices. This version shifts all elements to a positive range before sorting.
using System;
class Program
{
static void CountingSortWithNegatives(int[] arr)
{
int min = arr[0];
int max = arr[0];
foreach (int num in arr)
{
if (num < min) min = num;
if (num > max) max = num;
}
int range = max - min + 1;
int[] count = new int[range];
foreach (int num in arr)
count[num - min]++;
int index = 0;
for (int i = 0; i < range; i++)
while (count[i]-- > 0)
arr[index++] = i + min;
}
static void Main()
{
int[] arr = { -5, -10, 0, -3, 8, 5, -1 };
CountingSortWithNegatives(arr);
Console.WriteLine("Sorted array with negatives:");
foreach (int num in arr)
Console.Write(num + " ");
Console.WriteLine();
}
}Here, the minimum value is used to shift the array so that indices are non-negative, allowing the counting array to function properly. This is useful in real-world datasets where negative numbers often appear.
Program 3: Counting Sort Using Recursion
This program demonstrates a recursive approach to Counting Sort, showing how recursion can be applied to rebuild the sorted array from the counts. Beginners can see a different way to process the counting array step by step.
using System;
class Program
{
static void RecursiveFill(int[] arr, int[] count, int index, int value)
{
if (index >= arr.Length) return;
if (count[value] > 0)
{
arr[index] = value;
count[value]--;
RecursiveFill(arr, count, index + 1, value);
}
else if (value + 1 < count.Length)
{
RecursiveFill(arr, count, index, value + 1);
}
}
static void CountingSortRecursive(int[] arr)
{
int max = arr[0];
for (int i = 1; i < arr.Length; i++)
if (arr[i] > max) max = arr[i];
int[] count = new int[max + 1];
foreach (int num in arr) count[num]++;
RecursiveFill(arr, count, 0, 0);
}
static void Main()
{
int[] arr = { 4, 2, 2, 8, 3, 3, 1 };
CountingSortRecursive(arr);
Console.WriteLine("Sorted array using recursive Counting Sort:");
foreach (int num in arr)
Console.Write(num + " ");
Console.WriteLine();
}
}The recursive approach helps beginners understand breaking down a problem into smaller steps, which is a key programming concept. The array is filled one number at a time based on counts, using recursive calls.
Program 4: Counting Sort for Larger Ranges
When the dataset contains large numbers with sparse distribution, we can optimize Counting Sort by dynamically determining the range and efficiently filling the array.
using System;
class Program
{
static void CountingSortLargeRange(int[] arr)
{
int min = arr[0], max = arr[0];
foreach (int num in arr)
{
if (num < min) min = num;
if (num > max) max = num;
}
int[] count = new int[max - min + 1];
foreach (int num in arr) count[num - min]++;
int index = 0;
for (int i = 0; i < count.Length; i++)
while (count[i]-- > 0)
arr[index++] = i + min;
}
static void Main()
{
int[] arr = { 100, 500, 200, 300, 1000 };
CountingSortLargeRange(arr);
Console.WriteLine("Sorted array for large range:");
foreach (int num in arr)
Console.Write(num + " ");
Console.WriteLine();
}
}This version highlights that Counting Sort is versatile and can handle arrays with both small and large ranges efficiently, making it useful in different scenarios.
Frequently Asked Questions (FAQ)
Counting Sort often raises questions for beginners. Here are some answers:
Q1: Can Counting Sort handle negative numbers?
Yes, by shifting the array so that all numbers are non-negative indices in the counting array.
Q2: Is Counting Sort faster than Quick Sort?
It can be faster for integers within a small range because it avoids comparisons, but Quick Sort is better for general datasets.
Q3: Can Counting Sort sort decimals or strings?
Counting Sort is mainly for integers. Decimals can be converted to integers (e.g., multiplied by a factor), but strings require different sorting techniques like Radix Sort.
Q4: Is Counting Sort stable?
Yes, Counting Sort preserves the relative order of equal elements, which is important for some applications.
Conclusion
Counting Sort is an efficient, non-comparison-based sorting algorithm that is easy to implement and understand. It works best when the array contains integers in a small or moderately sized range. By exploring the simple, recursive, negative-number-friendly, and large-range versions, beginners can gain a solid understanding of how Counting Sort operates in different scenarios. Practicing these variations helps build a deeper grasp of sorting techniques and prepares you for more advanced algorithms like Radix Sort or Tim Sort.
