Chapters

Hide chapters

Data Structures & Algorithms in Swift

Fourth Edition · iOS 15 · Swift 5.5 · Xcode 13

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

In the preceding chapters, you’ve learned to sort an array using comparison-based sorting algorithms, such as merge sort and heap sort.

Quicksort is another comparison-based sorting algorithm. Much like merge sort, it uses the same strategy of divide and conquer. One important feature of quicksort is choosing a pivot point. The pivot divides the array into three partitions:

[ elements < pivot | pivot | elements > pivot ]

In this chapter, you will implement quicksort and look at various partitioning strategies to get the most out of this sorting algorithm.

Example

Open up the starter playground. A naïve implementation of quicksort is provided in quicksortNaive.swift:

public func quicksortNaive<T: Comparable>(_ a: [T]) -> [T] {
  guard a.count > 1 else { // 1
    return a
  }
  let pivot = a[a.count / 2] // 2
  let less = a.filter { $0 < pivot } // 3
  let equal = a.filter { $0 == pivot }
  let greater = a.filter { $0 > pivot }
  return quicksortNaive(less) + equal + quicksortNaive(greater) // 4
}

The implementation above recursively filters the array into three partitions. Let’s look at how it works:

  1. There must be more than one element in the array. If not, the array is considered sorted.
  2. Pick the middle element of the array as your pivot.
  3. Using the pivot, split the original array into three partitions. Elements less than, equal to or greater than the pivot go into different buckets.
  4. Recursively sort the partitions and then combine them.

Let’s now visualize the code above. Given the unsorted array below:

[12, 0, 3, 9, 2, 18, 8, 27, 1, 5, 8, -1, 21]
                     *

Your partition strategy in this implementation is to always select the middle element as the pivot. In this case, the element is 8. Partitioning the array using this pivot results in the following partitions:

less: [0, 3, 2, 1, 5, -1]
equal: [8, 8]
greater: [12, 9, 18, 27, 21]

Notice that the three partitions aren’t completely sorted yet. Quicksort will recursively divide these partitions into even smaller ones. The recursion will only halt when all partitions have either zero or one element.

Here’s an overview of all the partitioning steps:

12, 0, 3, 9, 2, 18, 8, 27, 1, 5, 8, -1, 21 0, 3, 2, 1, 5, -1 3, 2, 5 27, 21 0, -1 12, 9 12, 9, 27, 21 18, less greater 1 18 equal 8, 8 -1 0 2 3, 5 5 3 9 12 21 27

Each level corresponds with a recursive call to quicksort. Once recursion stops, the leafs are combined again, resulting in a fully sorted array:

[-1, 1, 2, 3, 5, 8, 8, 9, 12, 18, 21, 27]

While this naïve implementation is easy to understand, it raises some issues and questions:

  • Calling filter three times on the same array is not efficient.
  • Creating a new array for every partition isn’t space-efficient. Could you possibly sort in place?
  • Is picking the middle element the best pivot strategy? What pivot strategy should you adopt?

Partitioning strategies

In this section, you will look at partitioning strategies and ways to make this quicksort implementation more efficient. The first partitioning algorithm you will look at is Lomuto’s algorithm.

Lomuto’s partitioning

Lomuto’s partitioning algorithm always chooses the last element as the pivot. Let’s look at how this works in code.

public func partitionLomuto<T: Comparable>(_ a: inout [T],
                                           low: Int,
                                           high: Int) -> Int {
}
let pivot = a[high] // 1

var i = low // 2
for j in low..<high { // 3
  if a[j] <= pivot { // 4
    a.swapAt(i, j) // 5
    i += 1
  }
}

a.swapAt(i, high) // 6
return i // 7
[ values <= pivot | values > pivot | not compared yet | pivot ]
  low         i-1   i          j-1   j         high-1   high

Step-by-step

Look at a few steps of the algorithm to get a clear understanding of how it works. Given the unsorted array below:

[12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8]
  0   1  2  3  4  5   6   7   8  9  10  11    12
[ 12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, |  8  ]
  low                                        high
  i
  j
   0  1  2  3  4  5   6   7   8  9  10  11   12
[ 12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, |  8  ]
  low                                        high
  i
      j
  0   1  2  3  4  5   6   7   8  9  10  11   12
[ 0, 12, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, |  8  ]
 low                                         high
      i
         j
  0   1  2  3  4  5   6   7   8  9  10  11   12
[ 0, 3, 12, 9, 2, 21, 18, 27, 1, 5, 8, -1, |  8  ]
 low                                         high
         i
            j
  0   1  2  3  4  5   6   7   8  9  10  11   12
[ 0, 3, 2, 1, 5, 8, -1, 27, 9, 12, 21, 18, |  8  ]
 low                                         high
                         i

  0   1  2  3  4  5   6   7   8  9  10  11     12
[ 0, 3, 2, 1, 5, 8, -1 | 8 | 9, 12, 21, 18, |  27  ]
 low                                          high
                         i

public func quicksortLomuto<T: Comparable>(_ a: inout [T],
                                           low: Int, high: Int) {
  if low < high {
    let pivot = partitionLomuto(&a, low: low, high: high)
    quicksortLomuto(&a, low: low, high: pivot - 1)
    quicksortLomuto(&a, low: pivot + 1, high: high)
  }
}
var list = [12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8]
quicksortLomuto(&list, low: 0, high: list.count - 1)
print(list)

Hoare’s partitioning

Hoare’s partitioning algorithm always chooses the first element as the pivot. Let’s look at how this works in code.

public func partitionHoare<T: Comparable>(_ a: inout [T],
                                          low: Int, high: Int) -> Int {
  let pivot = a[low] // 1
  var i = low - 1 // 2
  var j = high + 1

  while true {
    repeat { j -= 1 } while a[j] > pivot // 3
    repeat { i += 1 } while a[i] < pivot // 4

    if i < j { // 5
      a.swapAt(i, j)
    } else {
      return j // 6
    }
  }
}

Step-by-step

Given the unsorted array below:

[  12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8   ]
[  12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1,  8  ]
   p
   i                                         j
[  8, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 12 ]
   i                                       j

[  8, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 12 ]
                   i                    j
[  8, 0, 3, 9, 2, -1, 18, 27, 1, 5, 8, 21, 12 ]
                   i                    j
[  8, 0, 3, 9, 2, -1, 8, 5, 1, 27, 18, 21, 12 ]
                         i      j
[  8, 0, 3, 9, 2, -1, 8, 5, 1, 27, 18, 21, 12 ]
                            j   i
public func quicksortHoare<T: Comparable>(_ a: inout [T],
                                          low: Int, high: Int) {
  if low < high {
    let p = partitionHoare(&a, low: low, high: high)
    quicksortHoare(&a, low: low, high: p)
    quicksortHoare(&a, low: p + 1, high: high)
  }
}
var list2 = [12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8]
quicksortHoare(&list2, low: 0, high: list.count - 1)
print(list2)

Effects of a bad pivot choice

The most crucial part of implementing quicksort is choosing the right partitioning strategy.

[8, 7, 6, 5, 4, 3, 2, 1]
less: [ ]
equal: [1]
greater: [8, 7, 6, 5, 4, 3, 2]
public func medianOfThree<T: Comparable>(_ a: inout [T],
                                         low: Int, high: Int) -> Int {
  let center = (low + high) / 2
  if a[low] > a[center] {
    a.swapAt(low, center)
  }
  if a[low] > a[high] {
    a.swapAt(low, high)
  }
  if a[center] > a[high] {
    a.swapAt(center, high)
  }
  return center
}
public func quickSortMedian<T: Comparable>(_ a: inout [T],
                                           low: Int, high: Int) {
  if low < high {
    let pivotIndex = medianOfThree(&a, low: low, high: high)
    a.swapAt(pivotIndex, high)
    let pivot = partitionLomuto(&a, low: low, high: high)
    quicksortLomuto(&a, low: low, high: pivot - 1)
    quicksortLomuto(&a, low: pivot + 1, high: high)
  }
}
var list3 = [12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8]
quickSortMedian(&list3, low: 0, high: list3.count - 1)
print(list3)

Dutch national flag partitioning

A problem with Lomuto’s and Hoare’s algorithms is that they don’t handle duplicates well. With Lomuto’s algorithm, duplicates end up in the less than partition and aren’t grouped together. With Hoare’s algorithm, the situation is even worse as duplicates can be all over the place.

public func partitionDutchFlag<T: Comparable>(_ a: inout [T],
                                              low: Int, high: Int,
                                              pivotIndex: Int)
                                              -> (Int, Int) {
  let pivot = a[pivotIndex]
  var smaller = low // 1
  var equal = low // 2
  var larger = high // 3
  while equal <= larger { // 4
    if a[equal] < pivot {
      a.swapAt(smaller, equal)
      smaller += 1
      equal += 1
    } else if a[equal] == pivot {
      equal += 1
    } else {
      a.swapAt(equal, larger)
      larger -= 1
    }
  }
  return (smaller, larger) // 5
}

Step-by-step

Let’s go over an example using the unsorted array below:

[ 12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8 ]
[12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8]
  s
  e
                                          l
[8, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 12]
 s
 e
                                      l
[8, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 12]
 s
    e
                                      l
[0, 8, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 12]
    s
       e
                                      l
[0, 3, -1, 2, 5, 8, 8, 27, 1, 18, 21, 9, 12]
                 s
                        e
                           l
[0, 3, -1, 2, 5, 8, 8, 1, 27, 18, 21, 9, 12]
                 s
                       e
                       l
[0, 3, -1, 2, 5, 1, 8, 8, 27, 18, 21, 9, 12]
                    s
                          e
                       l
public func quicksortDutchFlag<T: Comparable>(_ a: inout [T],
                                              low: Int, high: Int) {
  if low < high {
    let (middleFirst, middleLast) =
      partitionDutchFlag(&a, low: low, high: high, pivotIndex: high)
    quicksortDutchFlag(&a, low: low, high: middleFirst - 1)
    quicksortDutchFlag(&a, low: middleLast + 1, high: high)
  }
}
var list4 = [12, 0, 3, 9, 2, 21, 18, 27, 1, 5, 8, -1, 8]
quicksortDutchFlag(&list4, low: 0, high: list4.count - 1)
print(list4)

Key points

  • The naïve partitioning creates a new array on every filter function; this is inefficient. All other strategies sort in place.
  • Lomuto’s partitioning chooses the last element as the pivot.
  • Hoare’s partitioning chooses the first element as its pivot.
  • An ideal pivot would split the elements evenly between partitions.
  • Choosing a bad pivot can cause quicksort to perform in O().
  • Median of three finds the pivot by taking the median of the first, middle and last element.
  • Dutch national flag partitioning strategy helps to organize duplicate elements more efficiently.
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