Chapters

Hide chapters

Data Structures & Algorithms in Swift

Fourth Edition · iOS 15 · Swift 5.5 · Xcode 13

31. Radix Sort Challenges
Written by Kelvin Lau

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

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.
© 2024 Kodeco Inc.

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