Chapters
Chapters

Chapters

Hide chapters

Data Structures & Algorithms in Swift

Fifth Edition · iOS 18 · Swift 6.0 · Xcode 16.2

Before You Begin

Section 0: 6 chapters
Show chapters Hide chapters

Section I: Introduction

Section 1: 3 chapters
Show chapters Hide chapters

Section II: Elementary Data Structures

Section 2: 6 chapters
Show chapters Hide chapters

Section III: Trees

Section 3: 16 chapters
Show chapters Hide chapters

Section IV: Sorting Algorithms

Section 4: 10 chapters
Show chapters Hide chapters

Section V: Graphs

Section 5: 11 chapters
Show chapters Hide chapters

34. Quicksort
Written by Vincent Ngo

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now

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.

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:

Hoare’s partitioning

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

Step-by-step

Given the unsorted array below:

Effects of a bad pivot choice

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

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.

Step-by-step

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

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(n²).
  • 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.
33. Heapsort Challenges
35. Quicksort Challenges
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.
© 2026 Kodeco Inc.

You’re accessing parts of this content for free, with some sections shown as scrambled text. Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now