Chapters

Hide chapters

Data Structures & Algorithms in Swift

Third Edition · iOS 13 · Swift 5.1 · Xcode 11

Before You Begin

Section 0: 3 chapters
Show chapters Hide chapters

35. Quicksort Challenges
Written by Vincent Ngo

Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as scrambled text.

Here are a couple of quicksort challenges to make sure you have the topic down. Make sure to try them out yourself before looking at the solutions.

Challenge 1: Iterative quicksort

In this chapter, you learned how to implement quicksort recursively. Your challenge here is to implement it iteratively. Choose any partition strategy you learned in this chapter.

Challenge 2: Merge sort or quicksort

Explain when and why you would use merge sort over quicksort.

Challenge 3: Partitioning with Swift standard library

Implement Quicksort using the partition(by:) function that is part of the Swift Standard Library.

Solutions

Solution to Challenge 1

In Chapter 34, you implemented quicksort recursively. Let’s look at how you might do it iteratively. This solution uses Lomuto’s partition strategy.

public func quicksortIterativeLomuto<T: Comparable>(_ a: inout [T],
                                                    low: Int,
                                                    high: Int) {
  var stack = Stack<Int>() // 1
  stack.push(low) // 2
  stack.push(high)

  while !stack.isEmpty { // 3
    // 4
    guard let end = stack.pop(),
          let start = stack.pop() else {
      continue
    }

    let p = partitionLomuto(&a, low: start, high: end) // 5

    // 6
    if (p - 1) > start {
      stack.push(start)
      stack.push(p - 1)
    }

    // 7
    if (p + 1) < end {
      stack.push(p + 1)
      stack.push(end)
    }
  }

}
var list = [12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8]
quicksortIterativeLomuto(&list, low: 0, high: list.count - 1)
print(list)

Solution to Challenge 2

  • Merge sort is preferable over quicksort when you need stability. Merge sort is a stable sort and guarantees O(n log n). This is not the case with quicksort, which isn’t stable and can perform as bad as O().
  • Merge sort works better for larger data structures or data structures where elements are scattered throughout memory. Quicksort works best when elements are stored in a contiguous block.

Solution to Challenge 3

To perform quicksort on a Collection, the following must hold true:

extension MutableCollection where Self: BidirectionalCollection,
                                  Element: Comparable {
  mutating func quicksort() {
    quicksortLumuto(low: startIndex, high: index(before: endIndex))
  }

  private mutating func quicksortLumuto(low: Index, high: Index) {

  }
}
private mutating func quicksortLumuto(low: Index, high: Index) {
  if low <= high { // 1
    let pivotValue = self[high] // 2
    var p = self.partition { $0 > pivotValue } // 3

    if p == endIndex { // 4
      p = index(before: p)
    }
    // 5
    self[..<p].quicksortLumuto(low: low, high: index(before: p))
    // 6
    self[p...].quicksortLumuto(low: index(after: p), high: high)
  }
}
[8 3 2 8]
       p
var numbers = [12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8]
print(numbers)
numbers.quicksort()
print(numbers)
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