Have you ever needed to sort a list of items but didn’t want to use a built-in sorting algorithm? If so, you may have considered using the counting sort algorithm. In this article, we’ll take a look at how counting sort works and how we can implement it in C#. We’ll also compare it to other sorting algorithms and analyze its time and space complexity.
Let’s dive in.
What is Counting Sort?
As its name implies, counting sort works by counting the number of occurrences of each distinct element in the list. An auxiliary array stores these occurrences and maps the values of the distinct elements with the indices of the array. Finally, the algorithm iterates over the auxiliary array while sorting the original array.
Let’s take a deep dive and learn how counting sort works.
How Does Counting Sort Algorithm Work?
Let’s look at an example of how counting sort works. We will use the following set of numbers:
int[] array = {7, 1, 2, 8, 9, 9, 4, 1, 5, 5};
We start by finding the largest element in the array (9).
Next, the counting sort algorithm initializes an array of size [getMax(array[ ])+1] , to store the occurrences of distinct elements.
The algorithm loops through the unsorted array while storing the number of occurrences of every distinct element in the occurrences array, which it achieves by mapping the distinct elements with the index of the occurrences array:
Value: 0, 2, 1, 0, 1, 2, 0, 1, 1, 2 Index: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Now that we have populated the occurrences array, we are going to iterate through the array as we retrieve the occurrences of each distinct element as we populate the sorted array:
1, 1, 2, 4, 5, 5, 7, 8, 9, 9
Let’s learn how to implement the counting sort algorithm in C#.
How to Implement Counting Sort in C#?
Let’s start by writing a GetMaxVal() method that takes an array and its size as inputs and returns the largest integer in that array:
public static int GetMaxVal(int[] array, int size)
{
var maxVal = array[0];
for (int i = 1; i < size; i++)
if (array[i] > maxVal)
maxVal = array[i];
return maxVal;
}
The GetMaxVal() method iterates through the array from the first element to the last one while updating the value of maxVal, which we are going to need as we implement the counting sort algorithm.
Next, we are going to write a CountingSort() method that takes an array as its sole input and returns a sorted array:
public int[] CountingSort(int[] array)
{
var size = array.Length;
var maxElement = GetMaxVal(array, size);
var occurrences = new int[maxElement + 1];
for (int i = 0; i < maxElement + 1; i++)
{
occurrences[i] = 0;
}
for (int i = 0; i < size; i++)
{
occurrences[array[i]]++;
}
for (int i = 0, j = 0; i <= maxElement; i++)
{
while (occurrences[i] > 0)
{
array[j] = i;
j++;
occurences[i]--;
}
}
return array;
}
How the Counting Sort Method Works
We can see that the process starts by getting the largest integer in the array by invoking GetMaxVal(). Once we get the largest integer in the array, we define an array of size maxElement + 1 and initialize all the values to zero.
At this point, we start populating the occurrences array by storing the occurrences of each unique element in the array:
for (int i = 0; i < size; i++)
{
occurrences[array[i]]++;
}
Next, the algorithm iterates through the occurrences array to sort the array elements by mapping the indexes and their values:
for (int i = 0, j = 0; i <= maxElement; i++)
{
while (occurrences[i] > 0)
{
array[j] = i;
j++;
array[i]--;
}
}
return array;
Finally, we can verify that the CountingSort() method sorts a given unsorted array accurately:
var array = new int[] { 73, 57, 49, 99, 133, 20, 1 };
var expected = new int[] { 1, 20, 49, 57, 73, 99, 133 };
var sortFunction = new CountingSortMethods();
var sortedArray = sortFunction.CountingSort(array);
Assert.IsNotNull(sortedArray);
CollectionAssert.AreEqual(sortedArray, expected);
Space and Time Complexity of Counting Sort Algorithm
The counting sort algorithm requires an auxiliary array of size k (max element + 1). Therefore, the space complexity of the counting sort algorithm is O(k).
Best-Case Time Complexity
The best-case time complexity occurs when the array elements have a range k which is equal to 1. In this case, the algorithm takes linear time as the time complexity becomes O(1 + n) or O(n).
Average-Case Time Complexity
Counting sort encounters the average-case time complexity scenario when we select random values e.g. from 1 to n. In this case, assuming we have an array of size n and the value of the largest element being k, the algorithm has O(n+k) as its average-case time complexity.
Worst-Case Time Complexity
This time complexity scenario occurs when the elements are skewed with the largest element k, being significantly larger than the rest of the elements in the array. This increases the time it takes for the algorithm to iterate through the occurrences array and worsens the algorithm’s space complexity.
Given the average time complexity of the counting sort algorithm is O(n+k), when the value of k grows for example to n^4, the total time it takes to sort the array is O(n + (n^4)).
Therefore, since the worst-case complexity scenario of the counting sort algorithm starts occurring when the maximum element is significantly larger than the rest of the elements, the time complexity of the algorithm is O(k).
Advantages of Counting Sort Algorithm
One advantage of the counting sort algorithm is that it is relatively simple to understand and implement.
Additionally, the algorithm is very efficient for collections with a small range of values. Finally, the algorithm is stable, meaning that items with equal values will retain their original order after being sorted unlike other sorting algorithms such as quicksort.
Disadvantages of Counting Sort Algorithm
First, the algorithm is not well-suited for collections with a large range of values because the algorithm’s efficiency decreases as the range of values increases.
Counting sort is a bit more complex to implement than other sorting algorithms such as selection and bubble sort.
Counting sort is not an in-place sorting algorithm since it requires additional space unlike algorithms such as quicksort, insertion sort, and bubble sort.
Finally, the algorithm can be slower than algorithms that use divide and conquer approaches such as merge sort and quicksort for large arrays.
Performance Tests
Let’s test how long the algorithm takes for it to sort three arrays that have 20,000 elements each. To help us complete these tests, we are going to implement two methods.
First, let’s write a method to generate a set of random array elements:
public static int[] CreateRandomArray(int size, int lower, int upper)
{
var array = new int[size];
var rand = new Random();
for (int i = 0; i < size; i++)
array[i] = rand.Next(lower, upper);
return array;
}
The CreateRandomArray() the method takes three integers size, lower and upper. Using the inbuilt Random class, we generate integer values between lower and upper that we’re going to put into the array.
To simulate the worst-case time complexity scenario, we are going to use the CreateRandomArray() we have but add an element that has a lot of digits at the end of the array such as Int32.MaxValue/2:
public static int[] CreateImbalancedArray(int[] array)
{
List<int> numbers = new List<int>();
numbers.AddRange(array);
numbers.Add(Int32.MaxValue/2);
return numbers.ToArray();
}
Next, we are going to create an object that holds different arrays that have random and sorted values:
public IEnumerable<object[]> SampleArrays()
{
yield return new object[] { CreateRandomArray(20000, 1, 2), "Best Case" };
yield return new object[] { CreateRandomArray(20000, 10000, 30000), "Average Case" };
yield return new object[] { CreateImbalancedArray(CreateRandomArray(19999, 10000, 30000)), "Worst Case" };
}
Each object entry has two values: an integer array e.g. CreateRandomArray(20000, 10000, 30000) and a string object storing the name of that array (“Average Case”). This object sorts random numbers between 10,000 and 30,000, which ensures that the array elements are distributed uniformly within the range.
On the other hand, the last object invokes the CreateImbalancedArray() which has elements whose values are distributed uniformly within the range except Int32.MaxValue/2.
Sample Test Results
Let’s assess the sample best, average, and worst-case complexity performance results of the algorithm:
| Method | array | arrayName | Mean | Error | StdDev | |------------- |------------- |------------- |----------------:|--------------:|---------------:| | CountingSort | Int32[20000] | Average Case | 366.03 μs | 7.284 μs | 18.803 μs | | CountingSort | Int32[20000] | Best Case | 92.46 μs | 1.823 μs | 3.846 μs | | CountingSort | Int32[20000] | Worst Case | 3,287,653.20 μs | 91,249.044 μs | 263,274.357 μs |
As we can see, despite the algorithm sorting 20,000 elements, they have different runtimes.
The counting sort algorithm encounters its best-case time complexity scenario as the range of elements is equal to 1. Additionally, we can see that counting sort’s average-case time complexity is achieved when we randomly select values within the range. On the other hand, when we introduce a large number such as Int32.MaxValue/2 when sorting elements distributed across a uniform range e.g. between 10,000 and 30,000, the algorithm encounters its worst-case time complexity.
The worst-case time complexity’s runtime is about 9,000 times longer than the average-case time complexity’s runtime. On the other hand, the average-case runtime is about 4 times slower than the best-case runtime. Please note that these runtimes may change depending on the number of elements and the computing resources available.
Conclusion
In this article, we have learned how counting sort in C# works and its time and space complexity.
