## Data Structures & Algorithms in Kotlin

Second Edition · Android 11 · Kotlin 1.5 · IntelliJ IDEA Community Edition 2021.1

#### Section I: Introduction to Data Structures & Algorithms

Section 1: 2 chapters

#### Section II: Elementary Data Structures

Section 2: 3 chapters

#### Section IV: Sorting Algorithms

Section 4: 5 chapters

# 16. Radix Sort Written by Márton Braun

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now

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.

// ...
}
// 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
}
// 3
digits *= base

this.clear()

### 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
}
val list = arrayListOf(88, 410, 1772, 20)
println("Original: \$list")
}
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

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()
}

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) {
return@forEach
}
}
}
val newValues = buckets.reduce { result, bucket ->
if (bucket.isEmpty()) return@reduce result
result
}

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
val list = (0..10).map { (Math.random() * 10000).toInt() }.toMutableList()
println("Original: \$list")
list.lexicographicalSort()
}