16.
Radix Sort
Written by Márton Braun
Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as text.
So far, you’ve been relying on comparisons to determine the sorting order. In this chapter, you’ll look at a completely different model of sorting known as radix sort.
Radix sort is a non-comparative algorithm for sorting integers in linear time. There are many implementations of radix sort that focus on different problems. To keep things simple, you’ll focus on sorting base 10 integers while investigating the least significant digit (LSD) variant of radix sort.
Example
To show how radix sort works, you’ll sort the following list:
var list = arrayListOf(88, 410, 1772, 20)
Radix sort relies on the positional notation of integers, as shown here:
First, the list is divided into buckets based on the value of the least significant digit, the ones digit.
These buckets are then emptied in order, resulting in the following partially sorted list:
list = arrayListOf(410, 20, 1772, 88)
Next, repeat this procedure for the tens digit:
The relative order of the elements didn’t change this time, but you’ve still got more digits to inspect.
The next digit to consider is the hundreds digit:
Note: For values that have no hundreds position or any other position, the digit is assumed to be zero.
Reassembling the list based on these buckets gives the following:
list = arrayListOf(20, 88, 410, 1772)
Finally, you need to consider the thousands digit:
Reassembling the list from these buckets leads to the final sorted list:
list = arrayListOf(20, 88, 410, 1772)
When many numbers end up in the same bucket, their relative ordering doesn’t change. For example, in the zero bucket for the hundreds position, 20 comes before 88. This is because the previous step put 20 in a lower bucket than 80, so 20 ended up before 88 in the list.
Implementation
Open the starter project for this chapter. In src ▸ radixsort, create a new file named RadixSort.kt.
fun MutableList<Int>.radixSort() {
// ...
}
fun MutableList<Int>.radixSort() {
// 1
val base = 10
// 2
var done = false
var digits = 1
while (!done) {
// ...
}
}
Bucket sort
Write the following inside the while loop:
// 1
val buckets = MutableList<MutableList<Int>>(base) { mutableListOf() }
// 2
this.forEach { number ->
val remainingPart = number / digits
val digit = remainingPart % base
buckets[digit].add(number)
}
// 3
digits *= base
this.clear()
this.addAll(buckets.flatten())
When do you stop?
Your while loop currently runs forever, so you’ll need a terminating condition somewhere. You’ll do that as follows:
if (remainingPart > 0) {
done = false
}
"radix sort" example {
val list = arrayListOf(88, 410, 1772, 20)
println("Original: $list")
list.radixSort()
println("Radix sorted: $list")
}
---Example of radix sort---
Original: [88, 410, 1772, 20]
Radix sorted: [20, 88, 410, 1772]
Challenges
Challenge 1: Most significant sort
The implementation discussed in the chapter used a least significant digit radix sort. Your task is to implement a most significant digit (MSD) radix sort.
var list = arrayListOf(500, 1345, 13, 459, 44, 999)
list.lexicographicalSort()
println(list) // outputs [13, 1345, 44, 459, 500, 999]
Solution 1
MSD radix sort is closely related to LSD radix sort, in that both use bucket sort. The difference is that MSD radix sort needs to curate subsequent passes of the bucket sort carefully. In LSD radix sort, bucket sort ran repeatedly using the whole list for every pass. In MSD radix sort, you run bucket sort with the entire list only once. Subsequent passes will sort each bucket recursively.
Digits
Add the following inside Challenge1.kt:
fun Int.digits(): Int {
var count = 0
var num = this
while (num != 0) {
count += 1
num /= 10
}
return count
}
fun Int.digit(atPosition: Int): Int? {
val correctedPosition = (atPosition + 1).toDouble()
if (correctedPosition > digits()) return null
var num = this
while (num / (pow(10.0, correctedPosition).toInt()) != 0) {
num /= 10
}
return num % 10
}
Lexicographical sort
With the helper methods, you’re now equipped to deal with MSD radix sort. Write the following at the bottom of the file:
fun MutableList<Int>.lexicographicalSort() {
this.clear()
this.addAll(msdRadixSorted(this, 0))
}
private fun msdRadixSorted(list: MutableList<Int>, position: Int): MutableList<Int> {
}
private fun msdRadixSorted(list: MutableList<Int>, position: Int): MutableList<Int> {
// 1
val buckets = MutableList<MutableList<Int>>(10) { mutableListOf() }
// 2
val priorityBucket = arrayListOf<Int>()
// 3
list.forEach { number ->
val digit = number.digit(position)
if (digit == null) {
priorityBucket.add(number)
return@forEach
}
buckets[digit].add(number)
}
}
val newValues = buckets.reduce { result, bucket ->
if (bucket.isEmpty()) return@reduce result
result.addAll(msdRadixSorted(bucket, position + 1))
result
}
priorityBucket.addAll(newValues)
return priorityBucket
Base case
As with all recursive operations, you need to set a terminating condition that stops the recursion. Recursion should halt if the current position you’re inspecting is greater than the number of significant digits of the largest value inside the list.
private fun List<Int>.maxDigits(): Int {
return this.maxOrNull()?.digits() ?: 0
}
if (position >= list.maxDigits()) return list
"MSD radix sort" example {
val list = (0..10).map { (Math.random() * 10000).toInt() }.toMutableList()
println("Original: $list")
list.lexicographicalSort()
println("Radix sorted: $list")
}
---Example of MSD radix sort---
Original: [448, 3168, 6217, 7117, 1256, 3887, 3900, 3444, 4976, 6891, 4682]
Radix sorted: [1256, 3168, 3444, 3887, 3900, 448, 4682, 4976, 6217, 6891, 7117]
Key points
- Radix sort is a non-comparative sort that doesn’t rely on comparing two values. Instead, it leverages bucket sort, which is like a sieve for filtering values. A helpful analogy is how some of the vending machines accept coins — the coins are distinguished by size.
- This chapter covered the least significant digit radix sort. Another way to implement radix sort is the most significant digit form. This form sorts by prioritizing the most significant digits over the lesser ones and is best illustrated by the sorting behavior of the
Stringtype.