Chapters

Hide chapters

Data Structures & Algorithms in Kotlin

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

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 scrambled 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 String type.
Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.
© 2024 Kodeco Inc.

You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a Kodeco Personal Plan.

Unlock now