Sorting is a fundamental concept in programming, and it helps organize data in a meaningful order. Whether you are working with scores, sales figures, or any kind of numerical data, sorting makes it easier to analyze and search through information. Counting Sort is a unique sorting algorithm that works best when the range of input numbers is not too large. Unlike other sorting algorithms, Counting Sort doesn’t compare elements directly but instead counts the number of occurrences of each value and uses that to build a sorted array.
with hands-on learning.
get the skills and confidence to land your next move.
This approach makes Counting Sort extremely fast for certain types of datasets, especially when the numbers are integers within a known range. It is commonly used in applications like exam grading systems, frequency analysis, or any scenario where you need stable and quick sorting. For beginners, learning Counting Sort introduces the idea of using auxiliary arrays and counting techniques, which is an important concept in algorithm design.
Program 1: Basic Counting Sort for Positive Numbers
This first program demonstrates the standard Counting Sort algorithm for positive integers. It uses loops to count the frequency of each number and rebuilds the sorted array.
Module Module1
Sub CountingSort(arr() As Integer)
Dim max As Integer = arr.Max()
Dim count(max) As Integer
For Each num In arr
count(num) += 1
Next
Dim index As Integer = 0
For i As Integer = 0 To max
While count(i) > 0
arr(index) = i
index += 1
count(i) -= 1
End While
Next
End Sub
Sub Main()
Dim data() As Integer = {4, 2, 2, 8, 3, 3, 1}
CountingSort(data)
Console.WriteLine("Sorted Array:")
For Each num In data
Console.Write(num & " ")
Next
Console.ReadLine()
End Sub
End ModuleIn this program, we first find the maximum number to define the size of the count array. Then we count how many times each number appears and reconstruct the sorted array. Beginners will see how Counting Sort avoids direct comparisons and uses counting to sort efficiently.
Program 2: Counting Sort With User Input
This version allows the user to enter their own numbers, making it more interactive and flexible for learning.
Module Module1
Sub CountingSort(arr() As Integer)
Dim max As Integer = arr.Max()
Dim count(max) As Integer
For Each num In arr
count(num) += 1
Next
Dim index As Integer = 0
For i As Integer = 0 To max
While count(i) > 0
arr(index) = i
index += 1
count(i) -= 1
End While
Next
End Sub
Sub Main()
Console.WriteLine("Enter numbers separated by spaces:")
Dim input As String = Console.ReadLine()
Dim data() As Integer = Array.ConvertAll(input.Split(" "c), AddressOf Integer.Parse)
CountingSort(data)
Console.WriteLine("Sorted Array:")
For Each num In data
Console.Write(num & " ")
Next
Console.ReadLine()
End Sub
End ModuleBeginners can experiment with different sets of numbers to understand how Counting Sort adapts to any positive integer dataset.
Program 3: Counting Sort That Handles Negative Numbers
The standard Counting Sort works only with non-negative numbers. This version shows how to handle negative numbers as well by shifting the values to start from zero.
Module Module1
Sub CountingSortNegative(arr() As Integer)
Dim minVal As Integer = arr.Min()
Dim maxVal As Integer = arr.Max()
Dim range As Integer = maxVal - minVal + 1
Dim count(range - 1) As Integer
For Each num In arr
count(num - minVal) += 1
Next
Dim index As Integer = 0
For i As Integer = 0 To range - 1
While count(i) > 0
arr(index) = i + minVal
index += 1
count(i) -= 1
End While
Next
End Sub
Sub Main()
Dim data() As Integer = {4, -2, -5, 0, 3, -1}
CountingSortNegative(data)
Console.WriteLine("Sorted Array:")
For Each num In data
Console.Write(num & " ")
Next
Console.ReadLine()
End Sub
End ModuleThis approach ensures that negative numbers are shifted to a positive index in the count array. Beginners will learn how a small adjustment allows Counting Sort to handle a wider range of data.
Program 4: Stable Counting Sort
This program demonstrates a stable version of Counting Sort, which preserves the relative order of equal elements. Stability is important when sorting objects with multiple properties.
Module Module1
Sub StableCountingSort(arr() As Integer)
Dim maxVal As Integer = arr.Max()
Dim count(maxVal) As Integer
For Each num In arr
count(num) += 1
Next
For i As Integer = 1 To maxVal
count(i) += count(i - 1)
Next
Dim output(arr.Length - 1) As Integer
For i As Integer = arr.Length - 1 To 0 Step -1
output(count(arr(i)) - 1) = arr(i)
count(arr(i)) -= 1
Next
Array.Copy(output, arr, arr.Length)
End Sub
Sub Main()
Dim data() As Integer = {4, 2, 2, 8, 3, 3, 1}
StableCountingSort(data)
Console.WriteLine("Sorted Array:")
For Each num In data
Console.Write(num & " ")
Next
Console.ReadLine()
End Sub
End ModuleThis stable version calculates cumulative counts and places elements in the output array accordingly. Beginners can see the importance of stability in sorting algorithms.
Program 5: Counting Sort With Mixed Range
Here, we handle both positive and negative numbers using a single unified approach.
Module Module1
Sub CountingSortNegative(arr() As Integer)
Dim minVal As Integer = arr.Min()
Dim maxVal As Integer = arr.Max()
Dim range As Integer = maxVal - minVal + 1
Dim count(range - 1) As Integer
For Each num In arr
count(num - minVal) += 1
Next
Dim index As Integer = 0
For i As Integer = 0 To range - 1
While count(i) > 0
arr(index) = i + minVal
index += 1
count(i) -= 1
End While
Next
End Sub
Sub Main()
Dim data() As Integer = {3, -1, 4, -2, 0, 5}
CountingSortNegative(data)
Console.WriteLine("Sorted Array:")
For Each num In data
Console.Write(num & " ")
Next
Console.ReadLine()
End Sub
End ModuleThis demonstrates how versatile Counting Sort can be with a simple modification, making it suitable for real-world data that may include negative numbers.
Program 6: Counting Sort for Floating-Point Numbers
This program demonstrates how to sort floating-point numbers using a variation of Counting Sort. Since Counting Sort is naturally designed for integers, we scale the floating-point numbers to integers by multiplying them with a precision factor, sort them using Counting Sort, and then scale them back. This approach is very useful when you need to sort decimal numbers efficiently without losing precision.
Module Module1
Sub CountingSortFloats(arr() As Double, precision As Integer)
' Scale numbers to integers
Dim scaled(arr.Length - 1) As Integer
For i As Integer = 0 To arr.Length - 1
scaled(i) = CInt(Math.Round(arr(i) * precision))
Next
' Find min and max to handle negative floats
Dim minVal As Integer = scaled.Min()
Dim maxVal As Integer = scaled.Max()
Dim range As Integer = maxVal - minVal + 1
Dim count(range - 1) As Integer
' Count occurrences, shifted by minVal
For Each num In scaled
count(num - minVal) += 1
Next
' Rebuild the sorted scaled array
Dim index As Integer = 0
For i As Integer = 0 To range - 1
While count(i) > 0
scaled(index) = i + minVal
index += 1
count(i) -= 1
End While
Next
' Scale back to floating-point numbers
For i As Integer = 0 To arr.Length - 1
arr(i) = scaled(i) / precision
Next
End Sub
Sub Main()
Dim data() As Double = {-2.5, 3.1, -1.2, 0.5, 4.8, -0.7}
CountingSortFloats(data, 10) ' Multiply by 10 for 1 decimal precision
Console.WriteLine("Sorted Array:")
For Each num In data
Console.Write(num & " ")
Next
Console.ReadLine()
End Sub
End ModuleThe program first scales the floating-point numbers to integers by multiplying them with a precision factor. This allows us to use the classic Counting Sort algorithm. By adjusting the minimum value, we handle negative numbers as well. After sorting, we scale back to floating-point numbers, restoring their decimal values.
This method is very useful for beginners because it teaches how to adapt a simple integer-based algorithm to work with decimal numbers, maintaining both efficiency and accuracy. It also shows how to handle negative floating-point values, which is a common requirement in real-world data.
Program 7: Counting Sort for Floating-Point Numbers (Handles Both Positive and Negative)
This program shows how to sort floating-point numbers, including both negative and positive values, using an adapted Counting Sort. By scaling numbers to integers based on the desired decimal precision, we can apply the standard Counting Sort logic to real-world datasets with decimals.
Module Module1
Sub CountingSortFloatsNegPos(arr() As Double, Optional decimals As Integer = 2)
' Scale factor for decimal precision
Dim factor As Integer = CInt(Math.Pow(10, decimals))
' Scale numbers to integers
Dim intArr(arr.Length - 1) As Integer
For i As Integer = 0 To arr.Length - 1
intArr(i) = CInt(arr(i) * factor)
Next
' Find minimum and maximum to handle negative numbers
Dim minVal As Integer = intArr.Min()
Dim maxVal As Integer = intArr.Max()
Dim range As Integer = maxVal - minVal + 1
Dim count(range - 1) As Integer
' Count occurrences
For Each num In intArr
count(num - minVal) += 1
Next
' Rebuild sorted array
Dim index As Integer = 0
For i As Integer = 0 To range - 1
While count(i) > 0
arr(index) = (i + minVal) / factor
index += 1
count(i) -= 1
End While
Next
End Sub
Sub Main()
Dim data() As Double = {2.34, -1.25, 3.12, 0.5, -0.75, 1.99, -2.5}
CountingSortFloatsNegPos(data, 2)
Console.WriteLine("Sorted Array:")
For Each num In data
Console.Write(num & " ")
Next
Console.ReadLine()
End Sub
End ModuleFirst, each floating-point number is scaled into an integer according to the number of decimal places we want to keep. This allows Counting Sort, which normally only works on integers, to be applied. We then calculate the minimum and maximum values to handle negative numbers, ensuring the count array covers the entire range. After counting and rebuilding the array, we scale the integers back to floating-point numbers, giving a sorted array that includes both negative and positive decimals.
This version is useful for beginners because it demonstrates a practical way to adapt integer-based algorithms for real-world data, showing how a simple modification can extend Counting Sort to handle negative and decimal values efficiently.
Frequently Asked Questions (FAQ)
Counting Sort is a common topic for beginners, so here are some questions you may have:
Q1: Can Counting Sort handle negative numbers?
Yes, with a small adjustment, we can shift all numbers so that negative values are converted to positive indices in the count array.
Q2: What is the time complexity of Counting Sort?
Counting Sort runs in O(n + k) time, where n is the number of elements and k is the range of input values.
Q3: Is Counting Sort a stable sorting algorithm?
Yes, if implemented correctly with cumulative counts, it can be stable, preserving the order of equal elements.
Q4: When is Counting Sort most useful?
It is ideal for integer datasets with a limited range, such as exam scores, small numbers, or frequency counts.
Q5: Can Counting Sort be used for floating-point numbers?
Not directly. It works best with integers, but floating-point numbers can be scaled and converted to integers for sorting.
Conclusion
Counting Sort is a fast, efficient, and beginner-friendly algorithm for sorting integers. By counting occurrences instead of comparing elements, it can handle large arrays quickly, especially when the range of numbers is small. With slight modifications, it can also handle negative numbers and maintain stability, which is essential in many applications. Beginners practicing Counting Sort in VB .NET will gain insights into counting-based algorithms, stable sorting, and handling data ranges effectively. Experimenting with user input, negative numbers, and stability considerations will strengthen understanding and prepare learners for more advanced sorting techniques.
