Chapters

Hide chapters

Data Structures & Algorithms in Swift

Fourth Edition · iOS 15 · Swift 5.5 · Xcode 13

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 scrambled 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:

1 thousands 0 hundreds 2 tens 4 ones

First, the array is divided into buckets based on the value of the least significant digit: the ones digit.

- 410, 20 - 1772 - 88 0 2 8

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:

- 410 - 20 - 1772 - 88 1 2 7 8

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:

- 20, 88 - 410 - 1772 0 4 7

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:

- 20, 88, 410 - 1772 0 1

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 String type.
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 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 Kodeco Personal Plan.

Unlock now