Home iOS & Swift Books Data Structures & Algorithms in Swift

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.

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

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 stable and guarantees O(n log n). These characteristics are 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:

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.

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.