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 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 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(n²).
- 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)