C# Counting Sort Algorithm
last modified March 9, 2025
This tutorial explains the counting sort algorithm in C#. We'll define it, show examples for sorting numbers and text, and compare it with Quick Sort.
An algorithm is a clear, step-by-step method to solve a problem or do a task. It's the foundation of how programs process and manage data.
Sorting arranges data in a specific order, like ascending or descending. It's essential in computing for organizing and retrieving data.
Common Sorting Algorithms
Here are some well-known sorting algorithms:
- Bubble Sort
- Selection Sort
- Insertion Sort
- Merge Sort
- Quick Sort
- Counting Sort
Counting Sort Algorithm
Counting sort is a non-comparison-based sorting method. It counts how many times each element appears in the input, then uses this count to place elements in their correct sorted positions.
It's fast for small ranges of integers but requires extra memory for the count array. Unlike comparison sorts, it doesn't compare elements directly.
Counting Sort Example
Here's a C# implementation of counting sort for integers using top-level statements.
// CountingSort.cs
int[] CountingSort(int[] arr)
{
if (arr.Length == 0)
{
return arr;
}
int maxVal = arr.Max();
int[] count = new int[maxVal + 1];
foreach (int num in arr)
{
count[num]++;
}
List<int> sorted = [];
for (int i = 0; i < count.Length; i++)
{
while (count[i] > 0)
{
sorted.Add(i);
count[i]--;
}
}
return sorted.ToArray();
}
int[] arr = [4, 2, 2, 8, 3, 3, 1];
int[] sorted = CountingSort(arr);
Console.WriteLine("Sorted array: " + string.Join(" ", sorted));
This code sorts an integer array in ascending order using counting sort.
Sorting Textual Data
Counting sort can also sort text, like a string's characters. Here's an example:
// CountingSortText.cs
string CountingSortText(string text)
{
if (string.IsNullOrEmpty(text))
{
return text;
}
int maxVal = text.Max();
int[] count = new int[maxVal + 1];
foreach (char c in text)
{
count[c]++;
}
char[] sorted = new char[text.Length];
int index = 0;
for (int i = 0; i < count.Length; i++)
{
while (count[i] > 0)
{
sorted[index] = (char)i;
index++;
count[i]--;
}
}
return new string(sorted);
}
string text = "counting";
string sorted = CountingSortText(text);
Console.WriteLine("Sorted text: " + sorted);
This sorts a string's characters in ascending order using counting sort.
Sorting in Descending Order
To sort in descending order, we reverse the output loop in counting sort.
// CountingSortDesc.cs
int[] CountingSortDesc(int[] arr)
{
if (arr.Length == 0)
{
return arr;
}
int maxVal = arr.Max();
int[] count = new int[maxVal + 1];
foreach (int num in arr)
{
count[num]++;
}
List<int> sorted = [];
for (int i = count.Length - 1; i >= 0; i--)
{
while (count[i] > 0)
{
sorted.Add(i);
count[i]--;
}
}
return sorted.ToArray();
}
int[] arr = [4, 2, 2, 8, 3, 3, 1];
int[] sorted = CountingSortDesc(arr);
Console.WriteLine("Sorted array (descending): " + string.Join(" ", sorted));
This sorts an integer array in descending order.
Comparison with Quick Sort
Counting sort excels with small integer ranges, running in O(n + k) time, where k is the range of values. Quick Sort, a comparison-based method, averages O(n log n) and handles larger datasets better.
Benchmark Example
This example compares counting sort and Quick Sort performance.
// Benchmark.cs
using System.Diagnostics;
int[] CountingSort(int[] arr)
{
if (arr.Length == 0)
{
return arr;
}
int maxVal = arr.Max();
int[] count = new int[maxVal + 1];
foreach (int num in arr)
{
count[num]++;
}
List<int> sorted = [];
for (int i = 0; i < count.Length; i++)
{
while (count[i] > 0)
{
sorted.Add(i);
count[i]--;
}
}
return sorted.ToArray();
}
int[] QuickSort(int[] arr)
{
if (arr.Length <= 1)
{
return arr;
}
int pivot = arr[arr.Length / 2];
var left = new List<int>();
var middle = new List<int>();
var right = new List<int>();
foreach (int x in arr)
{
if (x < pivot)
{
left.Add(x);
}
else if (x == pivot)
{
middle.Add(x);
}
else
{
right.Add(x);
}
}
return [.. QuickSort(left.ToArray()), .. middle, .. QuickSort(right.ToArray())];
}
Random rand = new(Random.Shared.Next());
int[] data = new int[10000];
for (int i = 0; i < data.Length; i++)
{
data[i] = rand.Next(1000);
}
int[] countingData = data.ToArray();
Stopwatch sw = Stopwatch.StartNew();
CountingSort(countingData);
double countingTime = sw.Elapsed.TotalSeconds;
int[] quickData = data.ToArray();
sw = Stopwatch.StartNew();
QuickSort(quickData);
double quickTime = sw.Elapsed.TotalSeconds;
Console.WriteLine($"Counting sort time: {countingTime:F6} seconds");
Console.WriteLine($"Quick sort time: {quickTime:F6} seconds");
This benchmarks both algorithms on 10,000 random integers. Counting sort may win with small ranges, but Quick Sort scales better.
Source
We've explored counting sort in C# and compared it with Quick Sort.
Author
List all C# tutorials.