Counting Sort is a simple yet powerful sorting algorithm that works differently from comparison-based methods like Quick Sort or Merge Sort. Instead of comparing elements, it counts the number of occurrences of each element and uses this information to place elements in their correct position. This approach makes Counting Sort extremely fast for sorting integers or data that falls within a known, limited range. For beginners, it’s a great way to understand how algorithmic thinking can reduce complexity by taking advantage of data properties.
with hands-on learning.
get the skills and confidence to land your next move.
Counting Sort is widely used in situations where data has a limited range, such as sorting test scores, ages, or other integer-based datasets. Its efficiency comes from avoiding repeated comparisons and directly calculating the position of each element. Learning Counting Sort in Scala introduces beginners to concepts like array manipulation, frequency counting, and stable sorting. It also opens the door to understanding other non-comparison-based sorting algorithms, which are commonly used in real-world applications where speed matters.
Program 1: Basic Counting Sort for Integers
This program demonstrates a standard Counting Sort for positive integers. It counts the frequency of each element and reconstructs the sorted array.
object CountingSortBasic {
def countingSort(arr: Array[Int]): Array[Int] = {
val max = arr.max
val count = Array.fill(max + 1)(0)
for (num <- arr) count(num) += 1
var index = 0
for (i <- count.indices) {
for (_ <- 0 until count(i)) {
arr(index) = i
index += 1
}
}
arr
}
def main(args: Array[String]): Unit = {
val data = Array(4, 2, 2, 8, 3, 3, 1)
val sorted = countingSort(data)
println("Sorted Array: " + sorted.mkString(", "))
}
}In this version, the algorithm first finds the maximum value to create a counting array. Then it increments the frequency of each number and reconstructs the array by placing elements according to their count. Beginners can easily follow the logic, seeing how counting simplifies sorting without comparisons.
Program 2: Counting Sort with Stable Output
This version ensures stability, which means equal elements retain their original relative order, useful for complex data structures.
object CountingSortStable {
def countingSort(arr: Array[Int]): Array[Int] = {
val max = arr.max
val count = Array.fill(max + 1)(0)
for (num <- arr) count(num) += 1
for (i <- 1 until count.length) count(i) += count(i - 1)
val output = Array.fill(arr.length)(0)
for (i <- arr.indices.reverse) {
output(count(arr(i)) - 1) = arr(i)
count(arr(i)) -= 1
}
output
}
def main(args: Array[String]): Unit = {
val data = Array(4, 2, 2, 8, 3, 3, 1)
val sorted = countingSort(data)
println("Stable Sorted Array: " + sorted.mkString(", "))
}
}By computing cumulative counts, the algorithm ensures that elements are placed in order while keeping duplicates in their original sequence. This stability is useful when sorting more complex objects, like records with multiple fields, and helps beginners understand advanced sorting concepts.
Program 3: Counting Sort for Characters
This program extends Counting Sort to work with characters, such as sorting letters in a string.
object CountingSortChars {
def countingSort(chars: Array[Char]): Array[Char] = {
val count = Array.fill(256)(0)
for (ch <- chars) count(ch.toInt) += 1
for (i <- 1 until count.length) count(i) += count(i - 1)
val output = Array.fill(chars.length)(' ')
for (i <- chars.indices.reverse) {
output(count(chars(i).toInt) - 1) = chars(i)
count(chars(i).toInt) -= 1
}
output
}
def main(args: Array[String]): Unit = {
val text = Array('b', 'a', 'd', 'c', 'a', 'b')
val sorted = countingSort(text)
println("Sorted Characters: " + sorted.mkString(", "))
}
}Using Counting Sort for characters introduces beginners to ASCII-based counting. It works because each character has a numeric code, allowing the algorithm to count occurrences and sort efficiently without comparisons.
Program 4: Counting Sort with Negative Numbers
Counting Sort can be adapted for negative numbers by shifting the range. This program demonstrates that approach.
object CountingSortNegative {
def countingSort(arr: Array[Int]): Array[Int] = {
val min = arr.min
val max = arr.max
val range = max - min + 1
val count = Array.fill(range)(0)
for (num <- arr) count(num - min) += 1
var index = 0
for (i <- count.indices) {
for (_ <- 0 until count(i)) {
arr(index) = i + min
index += 1
}
}
arr
}
def main(args: Array[String]): Unit = {
val data = Array(-5, -10, 0, -3, 8, 5, -1)
val sorted = countingSort(data)
println("Sorted Array with Negatives: " + sorted.mkString(", "))
}
}By adjusting the array index to account for the minimum value, the algorithm can sort negative numbers efficiently. This adaptation teaches beginners how flexible Counting Sort can be and encourages thinking about data transformations.
Program 5: Counting Sort for Floating-Point Numbers (Scaled)
This example demonstrates sorting decimal numbers by scaling them to integers first.
object CountingSortFloat {
def countingSort(arr: Array[Double], scale: Int): Array[Double] = {
val scaled = arr.map(num => (num * scale).toInt)
val max = scaled.max
val count = Array.fill(max + 1)(0)
for (num <- scaled) count(num) += 1
var index = 0
for (i <- count.indices) {
for (_ <- 0 until count(i)) {
scaled(index) = i
index += 1
}
}
scaled.map(_.toDouble / scale)
}
def main(args: Array[String]): Unit = {
val data = Array(1.2, 3.5, 2.1, 0.7, 2.8)
val sorted = countingSort(data, 10)
println("Sorted Floating Numbers: " + sorted.mkString(", "))
}
}By scaling decimal numbers to integers, Counting Sort can be applied to floating-point data. This example shows beginners that the algorithm is adaptable beyond integers, as long as the data can be mapped to integers.
Frequently Asked Questions (FAQ)
This section answers common questions beginners have when learning Counting Sort in Scala.
Q1: Why is Counting Sort so fast for integers?
Because it counts occurrences instead of comparing each element, reducing the number of operations.
Q2: Can Counting Sort handle negative numbers?
Yes, by shifting the array indices to accommodate negative values.
Q3: Is Counting Sort stable?
Yes, when implemented with cumulative counts, it preserves the order of equal elements.
Q4: Can Counting Sort work with characters or strings?
Yes, characters can be sorted using their ASCII codes.
Q5: Is Counting Sort good for large datasets?
It is efficient for large datasets with a limited range of values, but not suitable for data with a very large range of integers.
Conclusion
Counting Sort is a powerful and beginner-friendly sorting algorithm that demonstrates how counting and indexing can replace comparisons for efficient sorting. By exploring multiple implementations in Scala—including stable sorting, characters, negative numbers, and floating-point numbers—beginners can understand the versatility of the algorithm.
Practicing Counting Sort helps reinforce array manipulation, frequency counting, and handling different types of data. The more you experiment with its variations, the easier it becomes to understand hybrid and non-comparison-based sorting techniques in real-world programming.
