30.
Radix Sort
Written by Kelvin Lau
Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as text.
In this chapter, you’ll look at a completely different model of sorting. So far, you’ve been relying on comparisons to determine the sorting order.
Radix sort is a non-comparative algorithm for sorting integers in linear time. There are multiple implementations of radix sort that focus on different problems.
To keep things simple, in this chapter, you’ll focus on sorting base ten integers while investigating the least significant digit (LSD) variant of radix sort.
Example
To show how radix sort works, you’ll sort the following array:
var array = [88, 410, 1772, 20]
Radix sort relies on the positional notation of integers, as shown here:
First, the array 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 array:
array = [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:
For values with no hundreds position (or any other position without a value), the digit will be assumed to be zero.
Reassembling the array based on these buckets gives the following:
array = [20, 88, 410, 1772]
Finally, you need to consider the thousands digit:
Reassembling the array from these buckets leads to the final sorted array:
array = [20, 88, 410, 1772]
When multiple 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 array.
Implementation
Open up the starter project for this chapter. In the Sources directory, create a new file named RadixSort.swift.
extension Array where Element == Int {
public mutating func radixSort() {
}
}
public mutating func radixSort() {
// 1
let base = 10
// 2
var done = false
var digits = 1
while !done {
}
}
Bucket Sort
Write the following inside the while loop:
// 1
var buckets: [[Int]] = .init(repeating: [], count: base)
// 2
forEach {
number in
let remainingPart = number / digits
let digit = remainingPart % base
buckets[digit].append(number)
}
// 3
digits *= base
self = buckets.flatMap { $0 }
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
}
example(of: "radix sort") {
var array = [88, 410, 1772, 20]
print("Original array: \(array)")
array.radixSort()
print("Radix sorted: \(array)")
}
---Example of: radix sort---
Original: [88, 410, 1772, 20]
Radix sorted: [20, 88, 410, 1772]
Key points
- Unlike other searches you’ve been working on in the previous chapter, radix sort is non-comparative and doesn’t rely on comparing two values. Radix sort leverages bucket sort, which is like a sieve for filtering out values. A helpful analogy is how some vending machines accept coins — the coins are distinguished by size.
- Radix sort can be one of the fastest sorting algorithms for sorting values with positional notation.
- 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.