Quicksort

This page briefly introduces quicksort.

Definition

Quicksort (English: Quicksort), also known as partition-exchange sort (English: partition-exchange sort), commonly abbreviated as “quicksort,” is a widely used sorting algorithm.

Basic principles and implementation

Process

Quicksort works by sorting an array using the divide-and-conquer approach.

Quicksort consists of three steps:

1. Partition the sequence into two parts (while preserving their relative ordering);
2. Recursively perform quicksort on the two subsequences;
3. No merging is needed, because the sequence is already completely sorted at this point.

Unlike merge sort, the first step does not directly split the sequence into a prefix and a suffix; instead, it must preserve the relative ordering during the partition. Specifically, the first step divides the sequence into two parts and ensures that every element in the first subsequence is smaller than every element in the second subsequence. To ensure the average time complexity, a number $m$ is generally chosen at random as the dividing value between the two subsequences.

Next, maintain two pointers, $p$ and $q$, one at the front and one at the back, and consider in turn whether the current number is in its proper position (front or back). If the current number is misplaced—for example, if the rear pointer $q$ encounters a number smaller than $m$—we can swap the numbers at positions $p$ and $q$, then move $p$ one position forward. Once the current numbers are all in their proper positions, move the pointers and continue processing until they meet.

In fact, quicksort does not prescribe how the first step must be implemented. There is more than one way to implement both the process of choosing $m$ and the partition process.

After the third step, the two sequences are separately sorted, and every number in the first sequence is smaller than every number in the second, so we only need to concatenate them.

C++

Non-recursive implementation¹

struct Range {
  int start, end;

  Range(int s = 0, int e = 0) { start = s, end = e; }
};

template <typename T>
void quick_sort(T arr[], const int len) {
  if (len <= 0) return;
  Range r[len];
  int p = 0;
  r[p++] = Range(0, len - 1);
  while (p) {
    Range range = r[--p];
    if (range.start >= range.end) continue;
    T mid = arr[range.end];
    int left = range.start, right = range.end - 1;
    while (left < right) {
      while (arr[left] < mid && left < right) left++;
      while (arr[right] >= mid && left < right) right--;
      std::swap(arr[left], arr[right]);
    }
    if (arr[left] >= arr[range.end])
      std::swap(arr[left], arr[range.end]);
    else
      left++;
    r[p++] = Range(range.start, left - 1);
    r[p++] = Range(left + 1, range.end);
  }
}

Recursive implementation

template <typename T>
int Partition(T A[], int low, int high) {
  int pivot = A[low];
  while (low < high) {
    while (low < high && pivot <= A[high]) --high;
    A[low] = A[high];
    while (low < high && A[low] <= pivot) ++low;
    A[high] = A[low];
  }
  A[low] = pivot;
  return low;
}

template <typename T>
void QuickSort(T A[], int low, int high) {
  if (low < high) {
    int pivot = Partition(A, low, high);
    QuickSort(A, low, pivot - 1);
    QuickSort(A, pivot + 1, high);
  }
}

template <typename T>
void QuickSort(T A[], int len) {
  QuickSort(A, 0, len - 1);
}

Python¹

def quick_sort(alist, first, last):
    if first >= last:
        return
    mid_value = alist[first]
    low = first
    high = last
    while low < high:
        while low < high and alist[high] >= mid_value:
            high -= 1
        alist[low] = alist[high]
        while low < high and alist[low] < mid_value:
            low += 1
        alist[high] = alist[low]
    alist[low] = mid_value
    quick_sort(alist, first, low - 1)
    quick_sort(alist, low + 1, last)

Properties

Stability

Quicksort is an unstable sorting algorithm.

Time complexity

The best-case and average-case time complexities of quicksort are $O(n\log n)$, while the worst-case time complexity is $O(n^2)$.

In the best case, every selected dividing value is the median of the sequence. The recurrence for the algorithm's time complexity is then $T(n) = 2T(\dfrac{n}{2}) + \Theta(n)$, and by the master theorem, $T(n) = \Theta(n\log n)$.

In the worst case, every selected dividing value is an extreme value of the sequence. The recurrence for the algorithm's time complexity is then $T(n) = T(n - 1) + \Theta(n)$, and summing the terms gives $T(n) = \Theta(n^2)$.

In the average case, each selected dividing value can be regarded as uniformly random.

Proof

We now prove that the time complexity of the algorithm in this case is $O(n\log n)$.

Lemma 1: When quicksort is performed on an array of $n$ elements, suppose the total number of comparisons during partitioning is $X$. Then the time complexity of quicksort is $O(n + X)$.

During each partitioning step, one element is selected as the dividing value, so the partitioning process occurs at most $n$ times. Moreover, the number of comparisons during partitioning and the number of other basic operations are of the same order, so the total time complexity is $O(n + X)$.

Let $a_i$ be the $i$-th smallest number in the original array. Define $A_{i,j}$ as $\{ a_i, a_{i+1}, \dots, a_j \}$, and let $X_{i,j}$ be a discrete random variable taking the value $0$ or $1$, indicating whether $a_i$ and $a_j$ are compared during sorting.

Clearly, each selected dividing value is different, and each element is compared only with dividing values. Thus, the total number of comparisons is

$$\begin{aligned} X = \sum \limits _ {i = 1} ^ {n - 1} \sum \limits _ {j = i + 1} ^ n X_{i,j} \end{aligned}$$

By linearity of expectation,

$$\begin{aligned} E[X] & = E \left[ \sum \limits _ {i = 1} ^ {n - 1} \sum \limits _ {j = i + 1} ^ n X_{i,j} \right] \\ & = \sum \limits _ {i = 1} ^ {n - 1} \sum \limits _ {j = i + 1} ^ n E[X_{i,j}] \\ & = \sum \limits _ {i = 1} ^ {n - 1} \sum \limits _ {j = i + 1} ^ n P(a_i\ \text{和}\ a_j\ \text{比较}) \end{aligned}$$

Lemma 2: The necessary and sufficient condition for $a_i$ and $a_j$ to be compared is that either $a_i$ or $a_j$ is the first selected dividing value in the set $A_{i,j}$.

First prove necessity: if neither $a_i$ nor $a_j$ is the first selected dividing value in the set $A_{i,j}$, then $a_i$ and $a_j$ are not compared.

If neither $a_i$ nor $a_j$ is the first selected dividing value in the set $A_{i,j}$, then there must be an $x$ satisfying $i < x < j$ such that $a_x$ is the first selected dividing value in $A_{i,j}$. In the partition using $a_x$ as the dividing value, $a_i$ and $a_j$ are placed into two different subsequences of the array, so $a_i$ and $a_j$ will never be compared afterward. Since elements are compared only with dividing values, $a_i$ and $a_j$ were not compared before or during this partition either. Therefore, $a_i$ and $a_j$ are not compared.

Now prove sufficiency: if either $a_i$ or $a_j$ is the first selected dividing value in the set $A_{i,j}$, then $a_i$ and $a_j$ are compared.

Without loss of generality, assume that $a_i$ is the first selected dividing value in the set $A_{i,j}$. Since no other number in $A_{i,j}$ is selected as a dividing value, all elements of $A_{i,j}$ are in the same subsequence of the array. In the partition using $a_i$ as the dividing value, $a_i$ is compared with every element in the current subsequence, so $a_i$ and $a_j$ are compared.

Consider computing $P(a_i\ \text{和}\ a_j\ \text{比较})$. Before an element of $A_{i,j}$ is selected as the dividing value, all elements of $A_{i,j}$ are in the same subsequence of the array. Therefore, every element of $A_{i,j}$ is equally likely to be selected first as the dividing value. Since $A_{i,j}$ contains $j - i + 1$ elements, by Lemma 2,

$$P(a_i \text{和} a_j \text{比较}) = P(a_i \text{或} a_j \text{是集合} A_{i,j} \text{中第一个被选中的分界值}) = \dfrac{2}{j-i+1}$$

Therefore,

$$\begin{aligned} E[X] & = \sum \limits _ {i = 1} ^ {n - 1} \sum \limits _ {j = i + 1} ^ n P(a_i\ \text{和}\ a_j\ \text{比较}) \\ & = \sum \limits _ {i = 1} ^ {n - 1} \sum \limits _ {j = i + 1} ^ n \dfrac{2}{j - i + 1} \\ & = \sum \limits _ {i = 1} ^ {n - 1} \sum \limits _ {k = 2} ^ {n - i + 1} \dfrac{2}{k} \\ & = \sum \limits _ {i = 1} ^ {n - 1} O(\log n) \\ & = O(n \log n) \end{aligned}$$

Thus, the expected time complexity of quicksort is $O(n \log n)$.

In practice, the worst case is nearly impossible to reach, and quicksort's memory accesses follow the principle of locality. Therefore, in most cases, quicksort performs substantially better than other sorting algorithms with complexity $O(n \log n)$, such as heapsort.²

Optimizations

Naive optimization ideas

If quicksort is implemented only according to the basic idea described above (or by directly copying a template), it will most likely fail on the P1177 (Template) Quicksort template problem. This is because adversarial data can force naive quicksort to take $O(n^2)$ time.

Therefore, we need to optimize the naive quicksort approach. There are three relatively common optimization ideas.³

• Select the dividing element (that is, the pivot) of the two subsequences using the median-of-three method (choosing the median among the first, last, and middle elements). This avoids degradation caused by extreme data, such as an ascending or descending sequence;
• When the sequence is short, insertion sort is more efficient;
• After each pass, group elements equal to the dividing element around the dividing element, avoiding degradation caused by extreme data, such as a sequence in which most elements are equal.

The following are several relatively mature ways to optimize quicksort.

Three-way quicksort

Definition

Three-way quicksort (English: 3-way Radix Quicksort) is a hybrid of quicksort and radix sort. Its algorithmic idea is based on the solution to the Dutch national flag problem.

Process

Unlike the original quicksort, after randomly selecting the dividing point $m$, three-way quicksort partitions the sequence to be sorted into three parts: less than $m$, equal to $m$, and greater than $m$. This achieves the effect of grouping elements equal to the dividing element around that element.

Properties

Three-way quicksort is much more efficient than the original quicksort when processing arrays containing many duplicate values. Its best-case time complexity is $O(n)$.

Implementation

Three-way quicksort is very simple to implement. An implementation in C++ is given below.

C++

// The template parameter T denotes the element type; this type must define the less-than (<) operator
template <typename T>
// arr is the array to be sorted, and len is its length
void quick_sort(T arr[], const int len) {
  if (len <= 1) return;
  // Choose the pivot randomly
  const T pivot = arr[rand() % len];
  // i: index of the element currently being processed
  // arr[0, j): stores elements less than pivot
  // arr[k, len): stores elements greater than pivot
  int i = 0, j = 0, k = len;
  // Perform one pass of three-way quicksort, partitioning the sequence into:
  // elements less than pivot | elements equal to pivot | elements greater than pivot
  while (i < k) {
    if (arr[i] < pivot)
      swap(arr[i++], arr[j++]);
    else if (pivot < arr[i])
      swap(arr[i], arr[--k]);
    else
      i++;
  }
  // Recursively quicksort the two subsequences
  quick_sort(arr, j);
  quick_sort(arr + k, len - k);
}

Python¹

def quick_sort(arr, l, r):
    if l >= r:
        return
    random_index = random.randint(l, r)
    pivot = arr[random_index]
    arr[l], arr[random_index] = arr[random_index], arr[l]
    i = l + 1
    j = l
    k = r + 1
    while i < k:
        if arr[i] < pivot:
            arr[i], arr[j + 1] = arr[j + 1], arr[i]
            j += 1
            i += 1
        elif arr[i] > pivot:
            arr[i], arr[k - 1] = arr[k - 1], arr[i]
            k -= 1
        else:
            i += 1
    arr[l], arr[j] = arr[j], arr[l]
    quick_sort(arr, l, j - 1)
    quick_sort(arr, k, r)

Introsort

Definition

Introsort (English: Introsort or Introspective sort)⁴ is a combination of quicksort and heapsort, invented by David Musser in 1997. Introsort is actually an optimization of quicksort that guarantees a worst-case time complexity of $O(n\log n)$.

Properties

Introsort limits the maximum recursion depth of quicksort to $\lfloor \log_2n \rfloor$ and switches to heapsort when the limit is exceeded. This preserves the locality of quicksort's memory accesses while preventing quicksort from degrading to $O(n^2)$ in some cases.

Implementation

Starting in June 2000, the implementation of the stl_algo.h sort() function in the SGI C++ STL adopted the introsort algorithm.

Linear-time selection of the k-th largest element

In the following code example, the $k$-th largest element is defined as the element at position $k$ when the sequence is sorted in ascending order (with indices starting from 0).

To find the $k$-th largest element (K-th order statistic), the simplest method is to sort the sequence first and then directly find the element at the $k$-th largest position. This takes $O(n\log n)$ time, which is inefficient for this problem.

We can solve this problem using the idea behind quicksort. Consider the partition process of quicksort. After the “partition” is complete, the sequence $A_{p} \cdots A_{r}$ is divided into $A_{p} \cdots A_{q}$ and $A_{q+1} \cdots A_{r}$. We can then decide whether to recursively solve the problem only on the left or only on the right according to the relationship between the number of elements on the left, $q - p + 1$, and the size of $k$.

As with quicksort, the time complexity of this method depends on the dividing value selected at each partition. If the dividing value is selected randomly, it can be shown that the time complexity is $O(n)$ in expectation.

Implementation (C++)

// The template parameter T denotes the element type; this type must define the less-than (<) operator
template <typename T>
// arr is the array within the search range, rk is the rank to find (starting from 0), and len is the array length
T find_kth_element(T arr[], int rk, const int len) {
  if (len <= 1) return arr[0];
  // Choose the pivot randomly
  const T pivot = arr[rand() % len];
  // i: index of the element currently being processed
  // arr[0, j): stores elements less than pivot
  // arr[k, len): stores elements greater than pivot
  int i = 0, j = 0, k = len;
  // Perform one pass of three-way quicksort, partitioning the sequence into:
  // elements less than pivot | elements equal to pivot | elements greater than pivot
  while (i < k) {
    if (arr[i] < pivot)
      swap(arr[i++], arr[j++]);
    else if (pivot < arr[i])
      swap(arr[i], arr[--k]);
    else
      i++;
  }
  // Recursively search different intervals for the k-th largest element according to the target rank and the positions of the two boundaries
  // If the number of elements less than pivot is greater than k, the k-th largest element must be less than pivot
  if (rk < j) return find_kth_element(arr, rk, j);
  // Otherwise, if the number of elements less than or equal to pivot is still not greater than k,
  // the k-th largest element must be greater than pivot
  else if (rk >= k)
    return find_kth_element(arr + k, rk - k, len - k);
  // Otherwise, pivot is the k-th largest element
  return pivot;
}

Improvement: median of medians

Median of medians provides a deterministic way to choose the dividing value during partitioning, allowing the $k$-th largest element algorithm to achieve linear time even in the worst case.

The algorithm proceeds as follows:

1. Divide the entire sequence into $\left \lfloor \dfrac{n}{5} \right \rfloor$ groups, with no more than 5 elements in each group;
2. Find the median of each group (because the number of elements is small, algorithms such as insertion sort can be used directly).
3. Find the median of the medians of these $\left \lfloor \dfrac{n}{5} \right \rfloor$ groups. Use this element as the dividing value in each partition of the algorithm described above.

Proof of time complexity

We now prove that the worst-case time complexity of this algorithm is $O(n)$. Let $T(n)$ be the amount of computation needed to solve a problem of size $n$.

First analyze the first two steps—partitioning and finding medians. Since each group contains very few elements after partitioning, we can regard the time complexity of finding the median of one group as $O(1)$. Therefore, the time complexity of finding the medians of all $\left \lfloor \dfrac{n}{5} \right \rfloor$ groups is $O(n)$.

Next analyze the third step—the recursive process. This step makes two recursive calls: the first finds the median of the group medians, with an obvious cost of $T(\dfrac{n}{5})$; the second enters either the left or right part of the dividing value. For the selected dividing element, $\dfrac{1}{2} \times \left \lfloor \dfrac{n}{5} \right \rfloor = \left \lfloor \dfrac{n}{10} \right \rfloor$ group medians are smaller than the dividing value. In each of these groups, the elements smaller than the median are also necessarily smaller than the dividing value, so the entire sequence contains at least $3 \times \left \lfloor \dfrac{n}{10} \right \rfloor = \left \lfloor \dfrac{3n}{10} \right \rfloor$ elements smaller than the dividing value. Similarly, the entire sequence contains at least $\left \lfloor \dfrac{3n}{10} \right \rfloor$ elements greater than the dividing value. Therefore, either side of the dividing value contains at most $\dfrac{7n}{10}$ elements, and the upper bound on the time cost of this recursive call is $T(\dfrac{7n}{10})$.

In summary, we can write the following inequality:

$$T(n) \leq T(\dfrac{n}{5}) + T(\dfrac{7n}{10}) + O(n)$$

Assume that $T(n) = O(n)$ holds when the problem size is sufficiently small. By definition, we then have $T(n) \leq cn$, where $c$ is a positive constant. Substitute this bound for every $T(n)$ on the right-hand side of the inequality:

$$\begin{aligned} T(n) & \leq T(\dfrac{n}{5}) + T(\dfrac{7n}{10}) + O(n)\\ & \leq \dfrac{cn}{5} + \dfrac{7cn}{10} + O(n)\\ & \leq \dfrac{9cn}{10} + O(n)\\ & = O(n) \end{aligned}$$

We have now proved that this algorithm has time complexity $O(n)$ even in the worst case.

References and notes

Footnotes

1. Algorithm implementation/Sorting/Quicksort - Wikibooks, the free textbook ↩ ↩² ↩³

2. C++ Performance Juicer: The Principle of Locality - I'm Root lee ! ↩

3. Three quicksort variants and quicksort optimizations ↩

4. introsort ↩