# 35 Quicksort Challenges Written by Vincent Ngo

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

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: