35. Quicksort Challenges

Written by Vincent Ngo

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.

For more information refer to Apple’s documentation here: https://developer.apple.com/documentation/swift/array/3017524-partition

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.

This function takes in an array, and the range between low and high. You are going to leverage the stack to store pairs of start and end values.

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)
    }
  }

}

Let’s go over the solution:

1. Create a stack that stores indices.
2. Push the starting low and high boundaries on the stack to initiate the algorithm.
3. As long as the stack is not empty, quicksort is not complete.
4. Get the pair of start and end indices from the stack.
5. Perform Lomuto’s partitioning with the current start and end index. Recall that Lomuto picks the last element as the pivot, and splits the partitions into three parts: elements that are less than the pivot, the pivot, and finally elements that are greater than the pivot.
6. Once the partitioning is complete, check and add the lower bound’s start and end indices to later partition the lower half.
7. Similarly check and add the upper bound’s start and end indices to later partition the upper half.

You are simply using the stack to store a pair of start and end indices to perform the partitions.

Let’s check to see if your iterative version of quicksort works:

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(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 true:

• The collection must be a MutableCollection. This gives you the ability to change the value of elements in a collection.
• The collection must be a BidirectionalCollection. This gives you the ability to traverse the collection forwards and backwards. Quicksort depends on the first and last index of a collection.
• The elements in the collection must be Comparable.

First add the following extension:

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) {

  }
}

Here you define a function called quicksort(). This internally calls a quicksortLumuto(_:) that takes in the low and high indexes to start the sorting algorithm.

Next add the following in quicksortLumuto(_:):

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)
  }
}

1. Continue to perform quicksort on the collection till the start and end indexes overlap each other.
2. Lumuto’s partition always takes the last element in the collection to perform the partition.
3. partition the elements in the collection and return the first index p satisfying the condition where, elements are greater than the pivotValue. Elements before index p represents elements that don’t satisfy the predicate, and elements after p represents elements that do satisfy the condition.
4. Handle the base case. If p is the last index, move to the index before. Consider the following case:

[8 3 2 8]
       p

If p was the last index, and you perform a partition, the partition would still be the same!

Remember that elements before p do not satisfy the partition. You would go in a recursive loop till you run out of memory! The first partition you perform in step 5 would have the same number of elements as the previous partition.

5. Perform quicksort on the first partition that is made up of elements not greater than the pivotValue.
6. Perform quicksort on the second partition that is made up of elements greater than the pivotValue.

To test it out, add the following:

var numbers = [12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8]
print(numbers)
numbers.quicksort()
print(numbers)

Fun Fact: If you look at the implementation of partition(by:), you’ll notice _partitionImpl(by:) adopts a similar strategy as Hoare’s partition. Check it out here: http://bit.ly/partitionimpl