31. Radix Sort Challenges

Written by Kelvin Lau

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.

You’ll implement MSD radix sort piece-by-piece, starting with the components it depends on.

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
  }
}

digits is a computed property that returns the number of digits that the Int has. For example, the value 1024 has four digits.

digit(atPosition:) returns the digit at a given position. Like arrays, the leftmost position is zero. Thus, the digit for position zero of the value 1024 is 1. The digit for position 3 is 4. Since there are only four digits, the digit for position five will return nil.

The implementation of digit(atPosition:) works by repeatedly chopping a digit off the end of the number, until the requested digit is at the end. It is then extracted using the remainder operator.

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...
  }
}

lexicographicalSort is the user-facing API for MSD radix sort. msdRadixSorted is the meat of the algorithm, and will be used to recursively apply MSD radix sort to the array.

Update msdRadixSorted to the following:

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...
}

1. Similar to LSD radix sort, you instantiate a two dimensional array for the buckets.
2. The priorityBucket is a special bucket that stores values with fewer digits than the current position. Values that go in the priorityBucket will be sorted first.
3. For every number in the array, you find the digit of the current position and place the number in the appropriate bucket.

Next, you need to recursively apply MSD radix sort for each of the individual buckets. Write the following at the end of msdRadixSorted:

priorityBucket.append(contentsOf: buckets.reduce(into: []) {
  result, bucket in
  guard !bucket.isEmpty else {
    return
  }
  result.append(contentsOf: msdRadixSorted(bucket, position + 1)
})

return priorityBucket

This statement calls reduce(into:) to collect the results of the recursive sorts and appends them to the priorityBucket. That way, the elements in the priorityBucket always go first. You’re almost done!

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.

At the top of the Array extension, write the following:

private var maxDigits: Int {
  self.max()?.digits ?? 0
}

Next, add the following at the top of msdRadixSorted:

guard position < array.maxDigits else {
  return array
}

This ensures that if the position is equal or greater than the array’s maxDigits, you’ll terminate recursion.

Let’s take it out for a spin! Add the following at the bottom of the playground to test the code:

var array: [Int] = (0...10).map { _ in Int(arc4random()) }
array.lexicographicalSort()
print(array)

You should see an array of random numbers similar to this:

[1350975449, 1412970969, 1727253826, 2003696829, 2281464743, 2603566662, 3012182591, 3552993620, 3665442670, 4167824072, 465277276]

Since the numbers are random, you won’t get an identical array. The important thing to note is the lexicographical ordering of the values.