Sorting is one of the most common operations in computer programming. From arranging numbers in ascending order to organizing large datasets, sorting plays a key role in improving the efficiency and readability of data. Among all sorting techniques, Radix Sort stands out because it doesn’t rely on comparisons like Bubble Sort or Quick Sort. Instead, it sorts data digit by digit, making it an efficient and clever algorithm, especially when dealing with numbers.
with hands-on learning.
get the skills and confidence to land your next move.
Radix Sort is particularly useful when sorting integers or strings with a fixed length. It works by sorting the numbers starting from the least significant digit (the rightmost digit) to the most significant digit (the leftmost one). This method ensures that the numbers end up in the correct order after a few passes. What makes Radix Sort special is its ability to handle large data efficiently in linear time, which can outperform other algorithms in specific cases. In this article, we will explore multiple ways to implement Radix Sort in Kotlin, each designed to help beginners understand it from different angles.
Program 1: Basic Radix Sort Using Counting Sort as a Helper Function
This is the most common and straightforward way to implement Radix Sort. It uses the Counting Sort algorithm internally to sort numbers based on each digit.
fun getMax(arr: IntArray): Int {
var max = arr[0]
for (num in arr) {
if (num > max) max = num
}
return max
}
fun countingSort(arr: IntArray, exp: Int) {
val n = arr.size
val output = IntArray(n)
val count = IntArray(10)
for (i in 0 until n) {
val index = (arr[i] / exp) % 10
count[index]++
}
for (i in 1 until 10) {
count[i] += count[i - 1]
}
for (i in n - 1 downTo 0) {
val index = (arr[i] / exp) % 10
output[count[index] - 1] = arr[i]
count[index]--
}
for (i in 0 until n) {
arr[i] = output[i]
}
}
fun radixSort(arr: IntArray) {
val max = getMax(arr)
var exp = 1
while (max / exp > 0) {
countingSort(arr, exp)
exp *= 10
}
}
fun main() {
val numbers = intArrayOf(170, 45, 75, 90, 802, 24, 2, 66)
println("Original Array: ${numbers.joinToString()}")
radixSort(numbers)
println("Sorted Array: ${numbers.joinToString()}")
}This version of Radix Sort finds the maximum value to know how many digits it needs to process. Then, for each digit position, it calls the Counting Sort to arrange numbers based on that digit. The process continues until all digits have been sorted. For beginners, this version provides a great way to understand how sorting can be done by examining each digit rather than comparing entire numbers.
Program 2: Radix Sort for Descending Order
While the first version sorts numbers in ascending order, sometimes we need them in descending order. This modified version does just that, using the same concept but reversing the order of elements.
fun getMax(arr: IntArray): Int {
var max = arr[0]
for (num in arr) {
if (num > max) max = num
}
return max
}
fun countingSortDescending(arr: IntArray, exp: Int) {
val n = arr.size
val output = IntArray(n)
val count = IntArray(10)
for (i in 0 until n) {
val index = (arr[i] / exp) % 10
count[index]++
}
for (i in 8 downTo 0) {
count[i] += count[i + 1]
}
for (i in n - 1 downTo 0) {
val index = (arr[i] / exp) % 10
output[count[index] - 1] = arr[i]
count[index]--
}
for (i in 0 until n) {
arr[i] = output[i]
}
}
fun radixSortDescending(arr: IntArray) {
val max = getMax(arr)
var exp = 1
while (max / exp > 0) {
countingSortDescending(arr, exp)
exp *= 10
}
}
fun main() {
val numbers = intArrayOf(123, 456, 789, 101, 212, 313)
println("Original Array: ${numbers.joinToString()}")
radixSortDescending(numbers)
println("Sorted in Descending Order: ${numbers.joinToString()}")
}In this version, the Counting Sort is adjusted so that higher digits are placed first. This helps the algorithm produce results in descending order. It’s a simple yet practical change that helps beginners see how minor tweaks can completely reverse the sorting order without changing the core logic of the algorithm.
Program 3: Radix Sort Using Kotlin Collections (Lists)
Kotlin’s collection framework makes coding more expressive and easier to understand. This version uses MutableList to perform Radix Sort, showcasing a more Kotlin-style implementation.
fun radixSortList(list: MutableList<Int>) {
val max = list.max() ?: return
var exp = 1
while (max / exp > 0) {
val buckets = Array(10) { mutableListOf<Int>() }
for (num in list) {
val index = (num / exp) % 10
buckets[index].add(num)
}
list.clear()
for (bucket in buckets) {
list.addAll(bucket)
}
exp *= 10
}
}
fun main() {
val numbers = mutableListOf(329, 457, 657, 839, 436, 720, 355)
println("Original List: $numbers")
radixSortList(numbers)
println("Sorted List: $numbers")
}This implementation uses buckets represented by a list of lists. Each bucket holds numbers that share the same digit in the current position. After each pass, the buckets are combined to form the partially sorted list. This version is great for beginners who are comfortable with Kotlin’s collection types and want to see how Radix Sort can be expressed in a more functional way.
Program 4: Radix Sort for Strings (Sorting by Characters)
Radix Sort isn’t just for numbers. It can also be used to sort strings alphabetically, especially when they all have the same length. This version demonstrates how to apply the same logic to text.
fun radixSortStrings(arr: Array<String>) {
if (arr.isEmpty()) return
val maxLength = arr.map { it.length }.max() ?: 0
for (pos in maxLength - 1 downTo 0) {
val buckets = Array(257) { mutableListOf<String>() } // 256 + 1 for padding
for (str in arr) {
val index = if (pos < str.length) str[pos].toInt() + 1 else 0
buckets[index].add(str)
}
var i = 0
for (bucket in buckets) {
for (s in bucket) {
arr[i++] = s
}
}
}
}
fun main() {
val words = arrayOf("dog", "cat", "bat", "apple", "ball")
println("Original Array: ${words.joinToString()}")
radixSortStrings(words)
println("Sorted Array: ${words.joinToString()}")
}This program works from the rightmost character of each string to the leftmost one, using buckets based on ASCII values. Each pass sorts the strings based on one character position until all positions are processed. It’s a fun example that shows how flexible Radix Sort can be — not just limited to numbers but also useful for textual data.
Frequently Asked Questions (FAQ)
Here are some common questions programmers often ask about Radix Sort in Kotlin.
Q1: What is Radix Sort in Kotlin?
Radix Sort is a non-comparative sorting algorithm that sorts numbers digit by digit, starting from the least significant digit to the most significant one.
Q2: How is Radix Sort different from other sorting algorithms?
Unlike comparison-based algorithms such as Quick Sort or Merge Sort, Radix Sort organizes elements based on individual digits or characters.
Q3: Does Radix Sort work with negative numbers?
The standard version of Radix Sort doesn’t handle negative numbers directly, but it can be modified to handle them by separating positive and negative values.
Q4: Is Radix Sort faster than Quick Sort?
In some cases, especially with integers of similar length, Radix Sort can be faster because it runs in linear time, O(nk), where k is the number of digits.
Q5: Can Radix Sort be used for strings?
Yes, Radix Sort can be used to sort strings alphabetically by processing them character by character.
Conclusion
Radix Sort is a fascinating algorithm that demonstrates the power of sorting without comparisons. It efficiently organizes data by processing digits or characters in a systematic way, making it an excellent choice for numbers and strings alike. With its stable and predictable performance, it’s especially useful for datasets where elements have similar sizes or fixed-length representations.
Whether you choose to use recursion, loops, or Kotlin’s modern collection features, understanding how Radix Sort works will make you a stronger programmer. Practice these examples, tweak the logic, and explore how different data types behave with this algorithm. Once you get the hang of it, you’ll find that Radix Sort is not only efficient but also quite fun to implement in Kotlin.
