Home iOS & Swift Books Data Structures & Algorithms in Swift

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 scrambled text.

You can unlock the rest of this book, and our entire catalogue of books and videos, with a raywenderlich.com Professional subscription.

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]

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.

Have feedback to share about the online reading experience? If you have feedback about the UI, UX, highlighting, or other features of our online readers, you can send them to the design team with the form below:

© 2021 Razeware LLC

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 raywenderlich.com Professional subscription.

Unlock Now

To highlight or take notes, you’ll need to own this book in a subscription or purchased by itself.