Sorting is one of the most fundamental concepts in programming. Whether you are managing scores, organizing inventory, or arranging numbers for analysis, sorting algorithms help you structure data efficiently. Among various sorting techniques, Counting Sort is a special algorithm that works exceptionally well when dealing with integers within a known range. Unlike comparison-based sorting methods like Quick Sort or Merge Sort, Counting Sort directly counts the occurrences of each value, making it extremely fast for certain types of datasets.
with hands-on learning.
get the skills and confidence to land your next move.
Counting Sort is particularly useful in situations where the maximum value of the data is not very large. By counting the frequency of each number, the algorithm can quickly reconstruct a sorted array without repeatedly comparing elements. This makes it an ideal choice for beginners to understand alternative sorting approaches, and for programmers who need fast, simple sorting for integers or categorical data. In this article, we will explore multiple Kotlin implementations of Counting Sort, showing different approaches and practical applications.
Program 1: Basic Counting Sort Implementation
This program demonstrates the standard approach to Counting Sort for positive integers. It counts occurrences of each number and then reconstructs the sorted array.
fun countingSort(arr: IntArray) {
if (arr.isEmpty()) return
val maxValue = arr.max()!!
val count = IntArray(maxValue + 1)
for (num in arr) {
count[num]++
}
var index = 0
for (i in count.indices) {
while (count[i] > 0) {
arr[index++] = i
count[i]--
}
}
}
fun main() {
val numbers = intArrayOf(4, 2, 2, 8, 3, 3, 1)
println("Original Array: ${numbers.joinToString()}")
countingSort(numbers)
println("Sorted Array: ${numbers.joinToString()}")
}This version uses a count array to store how many times each integer appears. Then, it fills the original array in order, effectively sorting the data. Beginners can see how Counting Sort avoids direct comparisons, which is different from more familiar algorithms.
Program 2: Counting Sort for Descending Order
Sometimes, we want numbers sorted from largest to smallest. This version modifies the reconstruction step to achieve descending order.
fun countingSortDescending(arr: IntArray) {
if (arr.isEmpty()) return
val maxValue = arr.max()!!
val count = IntArray(maxValue + 1)
for (num in arr) {
count[num]++
}
var index = 0
for (i in count.size - 1 downTo 0) {
while (count[i] > 0) {
arr[index++] = i
count[i]--
}
}
}
fun main() {
val numbers = intArrayOf(4, 2, 2, 8, 3, 3, 1)
println("Original Array: ${numbers.joinToString()}")
countingSortDescending(numbers)
println("Sorted in Descending Order: ${numbers.joinToString()}")
}By iterating over the count array in reverse, the largest values are placed first. This minor change demonstrates how flexible Counting Sort can be without changing its core logic.
Program 3: Counting Sort Handling Negative Numbers
Counting Sort traditionally works with non-negative integers, but it can be adapted to handle negative numbers by offsetting the values.
fun countingSortWithNegatives(arr: IntArray) {
if (arr.isEmpty()) return
val minValue = arr.min()!!
val maxValue = arr.max()!!
val range = maxValue - minValue + 1
val count = IntArray(range)
for (num in arr) {
count[num - minValue]++
}
var index = 0
for (i in count.indices) {
while (count[i] > 0) {
arr[index++] = i + minValue
count[i]--
}
}
}
fun main() {
val numbers = intArrayOf(-5, -10, 0, -3, 8, 5, -1, 10)
println("Original Array: ${numbers.joinToString()}")
countingSortWithNegatives(numbers)
println("Sorted Array: ${numbers.joinToString()}")
}This approach calculates an offset using the minimum value so that negative numbers are handled properly. Beginners learn how minor adjustments allow Counting Sort to work with a wider range of integers.
Program 4: Counting Sort Using Kotlin Lists
Kotlin lists can be used instead of arrays for more flexibility. This version demonstrates how to sort a mutable list using Counting Sort.
fun countingSortList(list: MutableList<Int>) {
if (list.isEmpty()) return
val maxValue = list.max()!!
val count = IntArray(maxValue + 1)
for (num in list) {
count[num]++
}
list.clear()
for (i in count.indices) {
repeat(count[i]) {
list.add(i)
}
}
}
fun main() {
val numbers = mutableListOf(3, 6, 4, 1, 3, 4, 1, 4)
println("Original List: $numbers")
countingSortList(numbers)
println("Sorted List: $numbers")
}Using Kotlin lists shows the flexibility of Counting Sort. Beginners can see that the algorithm can be adapted for higher-level data structures without changing the core logic.
Frequently Asked Questions (FAQ)
Here are common questions beginners ask about Counting Sort in Kotlin.
Q1: What is Counting Sort?
Counting Sort is a non-comparison-based algorithm that sorts integers by counting the number of occurrences of each value and reconstructing the array.
Q2: When should I use Counting Sort?
It works best when integers fall within a limited range, and when performance is important.
Q3: Can Counting Sort sort in descending order?
Yes, by iterating the count array in reverse during reconstruction.
Q4: Can Counting Sort handle negative numbers?
Yes, by applying an offset based on the minimum value of the array.
Q5: What is the time complexity of Counting Sort?
Counting Sort has a time complexity of O(n + k), where n is the number of elements and k is the range of input values.
Conclusion
Counting Sort is a simple, efficient, and beginner-friendly algorithm for sorting integers, especially when the data falls within a known range. In Kotlin, it can handle positive and negative integers, work with arrays or lists, and even sort in descending order with minor modifications. By practicing these variations, beginners can understand the power of non-comparison-based sorting algorithms and improve their problem-solving skills with real-world data.
