Quick Sort

This page provides a brief introduction to quicksort.

Definition

Quicksort, also known as partition-exchange sort, often referred to as "quicksort," is a widely used sorting algorithm.

Basic Principles and Implementation

Process

Quicksort works by sorting an array through a divide-and-conquer approach.

Quicksort consists of three steps:

Partition the array into two parts (ensuring relative order is maintained);
Recursively apply quicksort to the two subsequences;
No merging is needed because the array is already fully sorted at this point.

Unlike merge sort, the first step does not directly split the array into two sequences. Instead, during partitioning, the relative order must be maintained. Specifically, the first step is to divide the array into two parts, ensuring that all elements in the first subsequence are smaller than those in the second subsequence. To guarantee average time complexity, a random element \(m\) is typically chosen as the pivot to separate the two subsequences.

After that, maintain two pointers, \(p\) and \(q\), one at the front and one at the back, and check whether the current element is in the correct position (front or back). If the current element is misplaced—for example, if the back pointer \(q\) encounters an element smaller than \(m\)—then swap the elements at positions \(p\) and \(q\), and move \(p\) one step forward. Once all current elements are correctly placed, move the pointers and continue processing until the two pointers meet.

In fact, quicksort does not specify how to implement the first step concretely. Both the process of selecting \(m\) and the partitioning process can be implemented in more than one way.

In the third step, the sequences are already sorted individually, and all elements in the first sequence are smaller than those in the second, so they can simply be concatenated.

C++Python⁴

Non-recursive Implementation⁴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);
  }
}

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

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 optimal and average time complexity of quicksort is \(O(n\log n)\), while the worst-case time complexity is \(O(n^2)\).

In the optimal case, each chosen pivot is the median of the sequence. The recurrence relation for the time complexity is \(T(n) = 2T(\dfrac{n}{2}) + \Theta(n)\). By the master theorem, \(T(n) = \Theta(n\log n)\).

In the worst case, each chosen pivot is an extreme value (minimum or maximum) of the sequence. The recurrence relation is \(T(n) = T(n - 1) + \Theta(n)\), which sums to \(T(n) = \Theta(n^2)\).

In the average case, the pivot can be considered as chosen uniformly at random.

Proof

Below we prove that the time complexity in this case is \(O(n\log n)\).

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

Since an element is selected as the pivot during each partitioning step, partitioning occurs at most \(n\) times. Moreover, the number of comparisons during partitioning is on the same order as other basic operations, so the total time complexity is \(O(n + X)\).

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

Clearly, each chosen pivot is distinct, and elements are only compared with the pivot. 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{and}\ a_j\ \text{are compared}) \end{aligned} \]

Lemma 2: \(a_i\) and \(a_j\) are compared if and only if \(a_i\) or \(a_j\) is the first pivot selected from the set \(A_{i,j}\).

First, necessity: if neither \(a_i\) nor \(a_j\) is the first pivot selected from \(A_{i,j}\), then \(a_i\) and \(a_j\) are not compared.

If neither \(a_i\) nor \(a_j\) is the first pivot selected from \(A_{i,j}\), then there exists an \(x\) with \(i < x < j\) such that \(a_x\) is the first pivot selected from \(A_{i,j}\). In the partition with \(a_x\) as the pivot, \(a_i\) and \(a_j\) are placed into two different subsequences of the array, so they will definitely not be compared afterward. Since elements are only compared with the pivot, \(a_i\) and \(a_j\) are not compared before or during this partition. Thus, \(a_i\) and \(a_j\) are not compared.

Next, sufficiency: if \(a_i\) or \(a_j\) is the first pivot selected from \(A_{i,j}\), then \(a_i\) and \(a_j\) are compared.

Without loss of generality, assume \(a_i\) is the first pivot selected from \(A_{i,j}\). Since no other element in \(A_{i,j}\) is selected as a pivot, all elements in \(A_{i,j}\) remain in the same subsequence of the array. In the partition with \(a_i\) as the pivot, \(a_i\) is compared with all elements in the current subsequence, so \(a_i\) and \(a_j\) are compared.

Consider computing \(P(a_i\ \text{and}\ a_j\ \text{are compared})\). Before any element in \(A_{i,j}\) is selected as a pivot, all elements in \(A_{i,j}\) are in the same subsequence of the array. Thus, each element in \(A_{i,j}\) is equally likely to be the first selected as a pivot. Since \(A_{i,j}\) has \(j - i + 1\) elements, by Lemma 2,

\[ P(a_i \text{and} a_j \text{are compared}) = P(a_i \text{or} a_j \text{is the first pivot selected from } A_{i,j}) = \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{and}\ a_j\ \text{are compared}) \\ & = \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 almost never reached. Moreover, quicksort's memory access follows the principle of locality, so in most cases, quicksort performs significantly better than other \(O(n \log n)\) sorting algorithms like heapsort.¹

Optimization

Naive Optimization Ideas

If quicksort is implemented solely based on the basic idea described above (or by directly copying a template), it will likely fail to pass the template problem P1177【Template】Quicksort. This is because malicious data can degrade naive quicksort to \(O(n^2)\).

Therefore, we need to optimize the naive quicksort approach. Common optimization ideas include the following²:

Use the median-of-three method (i.e., select the median of the first, last, and middle elements) to choose the pivot for partitioning the two subsequences. This avoids degradation caused by extreme data (such as ascending or descending sequences);
When the sequence is short, use insertion sort for better efficiency;
After each partitioning step, gather elements equal to the pivot around the pivot. This avoids degradation caused by extreme data (such as sequences where most elements are equal).

Below are several more mature optimization methods for quicksort.

Three-way Quicksort

Definition

Three-way quicksort (also known as 3-way radix quicksort) is a hybrid of quicksort and radix sort. Its algorithm is based on the solution to the Dutch national flag problem.

Process

Unlike the original quicksort, after randomly selecting a pivot \(m\), three-way quicksort partitions the array into three parts: elements less than \(m\), equal to \(m\), and greater than \(m\). This achieves the effect of gathering elements equal to the pivot around it.

Properties

Three-way quicksort is far more efficient than the original quicksort when dealing with arrays containing many duplicate values. Its best-case time complexity is \(O(n)\).

Implementation

Three-way quicksort is straightforward to implement. Below is a C++ implementation of three-way quicksort.

C++Python⁴

// The template parameter T represents the element type, which must define the less-than (<) operation.
template <typename T>
// arr is the array to be sorted, len is the array length.
void quick_sort(T arr[], const int len) {
  if (len <= 1) return;
  // Randomly select the pivot.
  const T pivot = arr[rand() % len];
  // i: index of the current element 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 partitioning, dividing 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 apply quicksort to the two subsequences.
  quick_sort(arr, j);
  quick_sort(arr + k, len - k);
}

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 (short for introspective sort)³ is a hybrid of quicksort and heapsort, invented by David Musser in 1997. Introsort is essentially an optimization of quicksort, guaranteeing a worst-case time complexity of \(O(n\log n)\).

Properties

Introsort limits the maximum recursion depth of quicksort to \(\lfloor \log_2n \rfloor\). When this depth is exceeded, it switches to heapsort. This preserves the locality of memory access in quicksort while preventing performance degradation to \(O(n^2)\) in certain scenarios.

Implementation

Since June 2000, the sort() function in SGI C++ STL's stl_algo.h has been implemented using the introsort algorithm.

Finding the k-th Largest Element in Linear Time

In the code examples below, the \(k\)-th largest element is defined as the element at the \(k\)-th position (0-indexed) when the sequence is sorted in ascending order.

The simplest method to find the \(k\)-th largest element (K-th order statistic) is to sort the sequence first and then directly access the element at the \(k\)-th position. This approach has a time complexity of \(O(n\log n)\), which is inefficient for this problem.

We can solve this problem using the idea of quicksort. Consider the partitioning step of quicksort. After partitioning, the array \(A_{p} \cdots A_{r}\) is divided into \(A_{p} \cdots A_{q}\) and \(A_{q+1} \cdots A_{r}\). At this point, we can decide whether to recursively search in the left or right part based on the number of elements on the left (\(q - p + 1\)) and the value of \(k\).

Like quicksort, the time complexity of this method depends on the pivot chosen during each partitioning step. If the pivot is selected randomly, it can be proven that the expected time complexity is \(O(n)\).

Implementation (C++)

// The template parameter T represents the element type, which must define the less-than (<) operation.
template <typename T>
// arr is the array to search, rk is the desired rank (0-indexed), len is the array length.
T find_kth_element(T arr[], int rk, const int len) {
  if (len <= 1) return arr[0];
  // Randomly select the pivot.
  const T pivot = arr[rand() % len];
  // i: index of the current element 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 partitioning, dividing 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++;
  }
  // Based on the desired rank and the positions of the partition boundaries,
  // recursively search for the k-th largest element in the appropriate interval.
  // If there are more elements less than pivot than k, the k-th largest element must be in the less-than-pivot part.
  if (rk < j) return find_kth_element(arr, rk, j);
  // Otherwise, if the combined count of elements less than and equal to pivot is less than k,
  // the k-th largest element must be in the greater-than-pivot part.
  else if (rk >= k)
    return find_kth_element(arr + k, rk - k, len - k);
  // Otherwise, the pivot itself is the k-th largest element.
  return pivot;
}

Improvement: Median of Medians

The median of medians method provides a deterministic way to select the pivot during partitioning, enabling the algorithm to find the \(k\)-th largest element with linear time complexity even in the worst case.

The algorithm proceeds as follows:

Divide the entire sequence into \(\left \lfloor \dfrac{n}{5} \right \rfloor\) groups, each containing at most 5 elements;
Find the median of each group (since the groups are small, algorithms like insertion sort can be used directly).
Find the median of these \(\left \lfloor \dfrac{n}{5} \right \rfloor\) medians. Use this element as the pivot in the partitioning step of the algorithm described above.

Time Complexity Proof

We now prove that the worst-case time complexity of this algorithm is \(O(n)\). Let \(T(n)\) be the computational cost required to solve a problem of size \(n\).

First, analyze the first two steps—partitioning and finding medians. Since each group is very small, finding the median of a group can be considered \(O(1)\). Thus, finding all \(\left \lfloor \dfrac{n}{5} \right \rfloor\) medians takes \(O(n)\) time.

Next, analyze the third step—the recursive process. This step involves two recursive calls: the first is to find the median of medians, which clearly costs \(T(\dfrac{n}{5})\). The second is to enter either the left or right side of the pivot. Based on the chosen pivot, at least \(\dfrac{1}{2} \times \left \lfloor \dfrac{n}{5} \right \rfloor = \left \lfloor \dfrac{n}{10} \right \rfloor\) groups have medians smaller than the pivot. In these groups, elements smaller than the median are also smaller than the pivot. Thus, at least \(3 \times \left \lfloor \dfrac{n}{10} \right \rfloor = \left \lfloor \dfrac{3n}{10} \right \rfloor\) elements in the entire sequence are smaller than the pivot. Similarly, at least \(\left \lfloor \dfrac{3n}{10} \right \rfloor\) elements are greater than the pivot. Therefore, each side of the pivot has at most \(\dfrac{7n}{10}\) elements, so the upper bound for the time cost of this recursive call is \(T(\dfrac{7n}{10})\).

In summary, we can write the inequality:

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

Assume \(T(n) = O(n)\) holds for sufficiently small problem sizes. By definition, \(T(n) \leq cn\) for some constant \(c\). Substitute all \(T(n)\) on the right side:

\[ \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} \]

Thus, we have proven that the algorithm has a worst-case time complexity of \(O(n)\).

References and Notes

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用