31.
Radix Sort Challenges
Written by Kelvin Lau
Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as text.
Challenge 1: Most significant digit
Open the starter playground for this chapter to begin.
The implementation discussed in the chapter used a least significant digit radix sort. Your task is to implement a most significant digit radix sort.
This sorting behavior is called lexicographical sorting and is also used for String sorting.
For example:
var array = [500, 1345, 13, 459, 44, 999]
array.lexicographicalSort()
print(array) // outputs [13, 1345, 44, 459, 500, 999]
Solution to Challenge 1
MSD radix sort is closely related to LSD radix sort, in that both utilize bucket sort. The difference is that MSD radix sort needs to carefully curate subsequent passes of the bucket sort. In LSD radix sort, bucket sort ran repeatedly using the whole array for every pass. In MSD radix sort, you run bucket sort with the whole array only once. Subsequent passes will sort each bucket recursively.
Digits
Add the following inside your playground page:
extension Int {
var digits: Int {
var count = 0
var num = self
while num != 0 {
count += 1
num /= 10
}
return count
}
func digit(atPosition position: Int) -> Int? {
guard position < digits else {
return nil
}
var num = self
let correctedPosition = Double(position + 1)
while num / Int(pow(10.0, correctedPosition)) != 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 playground:
extension Array where Element == Int {
mutating func lexicographicalSort() {
self = msdRadixSorted(self, 0)
}
private func msdRadixSorted(_ array: [Int], _ position: Int) -> [Int] {
// more to come...
}
}
private func msdRadixSorted(_ array: [Int], _ position: Int) -> [Int] {
// 1
var buckets: [[Int]] = .init(repeating: [], count: 10)
// 2
var priorityBucket: [Int] = []
// 3
array.forEach { number in
guard let digit = number.digit(atPosition: position) else {
priorityBucket.append(number)
return
}
buckets[digit].append(number)
}
// more to come...
}
priorityBucket.append(contentsOf: buckets.reduce(into: []) {
result, bucket in
guard !bucket.isEmpty else {
return
}
result.append(contentsOf: msdRadixSorted(bucket, position + 1)
})
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 array.
private var maxDigits: Int {
self.max()?.digits ?? 0
}
guard position < array.maxDigits else {
return array
}
var array: [Int] = (0...10).map { _ in Int(arc4random()) }
array.lexicographicalSort()
print(array)
[1350975449, 1412970969, 1727253826, 2003696829, 2281464743, 2603566662, 3012182591, 3552993620, 3665442670, 4167824072, 465277276]