Перейти к содержанию

11.5   Быстрая сортировка

Быстрая сортировка (quick sort) - это алгоритм сортировки, основанный на стратегии "разделяй и властвуй"; он работает эффективно и применяется очень широко.

Ключевая операция быстрой сортировки - это "разделение с опорным элементом". Ее цель такова: выбрать некоторый элемент массива в качестве "опорного" и переместить все элементы меньше опорного влево от него, а все элементы больше опорного - вправо. Конкретный процесс показан на рисунке 11-8.

  1. Выбрать самый левый элемент массива как опорный и инициализировать два указателя i и j , направленные на левую и правую границы массива.
  2. Запустить цикл, в котором i и j ищут соответственно первый элемент, больший опорного, и первый элемент, меньший опорного, после чего эти два элемента меняются местами.
  3. Повторять шаг 2. , пока указатели i и j не встретятся, а затем обменять опорный элемент с элементом на границе двух подмассивов.

Шаги разделения с опорным элементом

pivot_division_step2

pivot_division_step3

pivot_division_step4

pivot_division_step5

pivot_division_step6

pivot_division_step7

pivot_division_step8

pivot_division_step9

Рисунок 11-8   Шаги разделения с опорным элементом

После завершения разделения исходный массив разбивается на три части: левый подмассив, опорный элемент и правый подмассив; при этом выполняется условие "любой элемент левого подмассива \(\leq\) опорный элемент \(\leq\) любой элемент правого подмассива". Следовательно, далее нам нужно лишь отсортировать эти два подмассива.

Стратегия divide and conquer в быстрой сортировке

По сути, разделение с опорным элементом сводит задачу сортировки длинного массива к двум задачам сортировки более коротких массивов.

quick_sort.py
def partition(self, nums: list[int], left: int, right: int) -> int:
    """Разбиение с опорными указателями"""
    # Взять nums[left] в качестве опорного элемента
    i, j = left, right
    while i < j:
        while i < j and nums[j] >= nums[left]:
            j -= 1  # Идти справа налево в поисках первого элемента меньше опорного
        while i < j and nums[i] <= nums[left]:
            i += 1  # Идти слева направо в поисках первого элемента больше опорного
        # Обмен элементов
        nums[i], nums[j] = nums[j], nums[i]
    # Переместить опорный элемент на границу двух подмассивов
    nums[i], nums[left] = nums[left], nums[i]
    return i  # Вернуть индекс опорного элемента
quick_sort.cpp
/* Разбиение с опорными указателями */
int partition(vector<int> &nums, int left, int right) {
    // Взять nums[left] в качестве опорного элемента
    int i = left, j = right;
    while (i < j) {
        while (i < j && nums[j] >= nums[left])
            j--;                // Идти справа налево в поисках первого элемента меньше опорного
        while (i < j && nums[i] <= nums[left])
            i++;                // Идти слева направо в поисках первого элемента больше опорного
        swap(nums[i], nums[j]); // Поменять эти два элемента местами
    }
    swap(nums[i], nums[left]);  // Переместить опорный элемент на границу двух подмассивов
    return i;                   // Вернуть индекс опорного элемента
}
quick_sort.java
/* Обмен элементов */
void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

/* Разбиение с опорными указателями */
int partition(int[] nums, int left, int right) {
    // Взять nums[left] в качестве опорного элемента
    int i = left, j = right;
    while (i < j) {
        while (i < j && nums[j] >= nums[left])
            j--;          // Идти справа налево в поисках первого элемента меньше опорного
        while (i < j && nums[i] <= nums[left])
            i++;          // Идти слева направо в поисках первого элемента больше опорного
        swap(nums, i, j); // Поменять эти два элемента местами
    }
    swap(nums, i, left);  // Переместить опорный элемент на границу двух подмассивов
    return i;             // Вернуть индекс опорного элемента
}
quick_sort.cs
/* Обмен элементов */
void Swap(int[] nums, int i, int j) {
    (nums[j], nums[i]) = (nums[i], nums[j]);
}

/* Разбиение с опорными указателями */
int Partition(int[] nums, int left, int right) {
    // Взять nums[left] в качестве опорного элемента
    int i = left, j = right;
    while (i < j) {
        while (i < j && nums[j] >= nums[left])
            j--;          // Идти справа налево в поисках первого элемента меньше опорного
        while (i < j && nums[i] <= nums[left])
            i++;          // Идти слева направо в поисках первого элемента больше опорного
        Swap(nums, i, j); // Поменять эти два элемента местами
    }
    Swap(nums, i, left);  // Переместить опорный элемент на границу двух подмассивов
    return i;             // Вернуть индекс опорного элемента
}
quick_sort.go
/* Разбиение с опорными указателями */
func (q *quickSort) partition(nums []int, left, right int) int {
    // Взять nums[left] в качестве опорного элемента
    i, j := left, right
    for i < j {
        for i < j && nums[j] >= nums[left] {
            j-- // Идти справа налево в поисках первого элемента меньше опорного
        }
        for i < j && nums[i] <= nums[left] {
            i++ // Идти слева направо в поисках первого элемента больше опорного
        }
        // Обмен элементов
        nums[i], nums[j] = nums[j], nums[i]
    }
    // Переместить опорный элемент на границу двух подмассивов
    nums[i], nums[left] = nums[left], nums[i]
    return i // Вернуть индекс опорного элемента
}
quick_sort.swift
/* Разбиение с опорными указателями */
func partition(nums: inout [Int], left: Int, right: Int) -> Int {
    // Взять nums[left] в качестве опорного элемента
    var i = left
    var j = right
    while i < j {
        while i < j, nums[j] >= nums[left] {
            j -= 1 // Идти справа налево в поисках первого элемента меньше опорного
        }
        while i < j, nums[i] <= nums[left] {
            i += 1 // Идти слева направо в поисках первого элемента больше опорного
        }
        nums.swapAt(i, j) // Поменять эти два элемента местами
    }
    nums.swapAt(i, left) // Переместить опорный элемент на границу двух подмассивов
    return i // Вернуть индекс опорного элемента
}
quick_sort.js
/* Обмен элементов */
swap(nums, i, j) {
    let tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

/* Разбиение с опорными указателями */
partition(nums, left, right) {
    // Взять nums[left] в качестве опорного элемента
    let i = left,
        j = right;
    while (i < j) {
        while (i < j && nums[j] >= nums[left]) {
            j -= 1; // Идти справа налево в поисках первого элемента меньше опорного
        }
        while (i < j && nums[i] <= nums[left]) {
            i += 1; // Идти слева направо в поисках первого элемента больше опорного
        }
        // Обмен элементов
        this.swap(nums, i, j); // Поменять эти два элемента местами
    }
    this.swap(nums, i, left); // Переместить опорный элемент на границу двух подмассивов
    return i; // Вернуть индекс опорного элемента
}
quick_sort.ts
/* Обмен элементов */
swap(nums: number[], i: number, j: number): void {
    let tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

/* Разбиение с опорными указателями */
partition(nums: number[], left: number, right: number): number {
    // Взять nums[left] в качестве опорного элемента
    let i = left,
        j = right;
    while (i < j) {
        while (i < j && nums[j] >= nums[left]) {
            j -= 1; // Идти справа налево в поисках первого элемента меньше опорного
        }
        while (i < j && nums[i] <= nums[left]) {
            i += 1; // Идти слева направо в поисках первого элемента больше опорного
        }
        // Обмен элементов
        this.swap(nums, i, j); // Поменять эти два элемента местами
    }
    this.swap(nums, i, left); // Переместить опорный элемент на границу двух подмассивов
    return i; // Вернуть индекс опорного элемента
}
quick_sort.dart
/* Обмен элементов */
void _swap(List<int> nums, int i, int j) {
  int tmp = nums[i];
  nums[i] = nums[j];
  nums[j] = tmp;
}

/* Разбиение с опорными указателями */
int _partition(List<int> nums, int left, int right) {
  // Взять nums[left] в качестве опорного элемента
  int i = left, j = right;
  while (i < j) {
    while (i < j && nums[j] >= nums[left]) j--; // Идти справа налево в поисках первого элемента меньше опорного
    while (i < j && nums[i] <= nums[left]) i++; // Идти слева направо в поисках первого элемента больше опорного
    _swap(nums, i, j); // Поменять эти два элемента местами
  }
  _swap(nums, i, left); // Переместить опорный элемент на границу двух подмассивов
  return i; // Вернуть индекс опорного элемента
}
quick_sort.rs
/* Разбиение с опорными указателями */
fn partition(nums: &mut [i32], left: usize, right: usize) -> usize {
    // Взять nums[left] в качестве опорного элемента
    let (mut i, mut j) = (left, right);
    while i < j {
        while i < j && nums[j] >= nums[left] {
            j -= 1; // Идти справа налево в поисках первого элемента меньше опорного
        }
        while i < j && nums[i] <= nums[left] {
            i += 1; // Идти слева направо в поисках первого элемента больше опорного
        }
        nums.swap(i, j); // Поменять эти два элемента местами
    }
    nums.swap(i, left); // Переместить опорный элемент на границу двух подмассивов
    i // Вернуть индекс опорного элемента
}
quick_sort.c
/* Обмен элементов */
void swap(int nums[], int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

/* Разбиение с опорными указателями */
int partition(int nums[], int left, int right) {
    // Взять nums[left] в качестве опорного элемента
    int i = left, j = right;
    while (i < j) {
        while (i < j && nums[j] >= nums[left]) {
            j--; // Идти справа налево в поисках первого элемента меньше опорного
        }
        while (i < j && nums[i] <= nums[left]) {
            i++; // Идти слева направо в поисках первого элемента больше опорного
        }
        // Поменять эти два элемента местами
        swap(nums, i, j);
    }
    // Переместить опорный элемент на границу двух подмассивов
    swap(nums, i, left);
    // Вернуть индекс опорного элемента
    return i;
}
quick_sort.kt
/* Обмен элементов */
fun swap(nums: IntArray, i: Int, j: Int) {
    val temp = nums[i]
    nums[i] = nums[j]
    nums[j] = temp
}

/* Разбиение с опорными указателями */
fun partition(nums: IntArray, left: Int, right: Int): Int {
    // Взять nums[left] в качестве опорного элемента
    var i = left
    var j = right
    while (i < j) {
        while (i < j && nums[j] >= nums[left])
            j--           // Идти справа налево в поисках первого элемента меньше опорного
        while (i < j && nums[i] <= nums[left])
            i++           // Идти слева направо в поисках первого элемента больше опорного
        swap(nums, i, j)  // Поменять эти два элемента местами
    }
    swap(nums, i, left)   // Переместить опорный элемент на границу двух подмассивов
    return i              // Вернуть индекс опорного элемента
}
quick_sort.rb
### Разбиение с опорными указателями ###
def partition(nums, left, right)
  # Взять nums[left] в качестве опорного элемента
  i, j = left, right
  while i < j
    while i < j && nums[j] >= nums[left]
      j -= 1 # Идти справа налево в поисках первого элемента меньше опорного
    end
    while i < j && nums[i] <= nums[left]
      i += 1 # Идти слева направо в поисках первого элемента больше опорного
    end
    # Обмен элементов
    nums[i], nums[j] = nums[j], nums[i]
  end
  # Переместить опорный элемент на границу двух подмассивов
  nums[i], nums[left] = nums[left], nums[i]
  i # Вернуть индекс опорного элемента
end
Визуализация кода

11.5.1   Алгоритм

Общий процесс быстрой сортировки показан на рисунке 11-9.

  1. Сначала выполнить "разделение с опорным элементом" для исходного массива и получить неотсортированные левый и правый подмассивы.
  2. Затем рекурсивно выполнить "разделение с опорным элементом" для левого и правого подмассивов.
  3. Продолжать рекурсию до тех пор, пока длина подмассива не станет равной 1; после этого сортировка всего массива будет завершена.

Процесс быстрой сортировки

Рисунок 11-9   Процесс быстрой сортировки

quick_sort.py
def quick_sort(self, nums: list[int], left: int, right: int):
    """Быстрая сортировка"""
    # Завершить рекурсию, когда длина подмассива равна 1
    if left >= right:
        return
    # Разбиение с опорными указателями
    pivot = self.partition(nums, left, right)
    # Рекурсивно обработать левый и правый подмассивы
    self.quick_sort(nums, left, pivot - 1)
    self.quick_sort(nums, pivot + 1, right)
quick_sort.cpp
/* Быстрая сортировка */
void quickSort(vector<int> &nums, int left, int right) {
    // Завершить рекурсию, когда длина подмассива равна 1
    if (left >= right)
        return;
    // Разбиение с опорными указателями
    int pivot = partition(nums, left, right);
    // Рекурсивно обработать левый и правый подмассивы
    quickSort(nums, left, pivot - 1);
    quickSort(nums, pivot + 1, right);
}
quick_sort.java
/* Быстрая сортировка */
void quickSort(int[] nums, int left, int right) {
    // Завершить рекурсию, когда длина подмассива равна 1
    if (left >= right)
        return;
    // Разбиение с опорными указателями
    int pivot = partition(nums, left, right);
    // Рекурсивно обработать левый и правый подмассивы
    quickSort(nums, left, pivot - 1);
    quickSort(nums, pivot + 1, right);
}
quick_sort.cs
/* Быстрая сортировка */
void QuickSort(int[] nums, int left, int right) {
    // Завершить рекурсию, когда длина подмассива равна 1
    if (left >= right)
        return;
    // Разбиение с опорными указателями
    int pivot = Partition(nums, left, right);
    // Рекурсивно обработать левый и правый подмассивы
    QuickSort(nums, left, pivot - 1);
    QuickSort(nums, pivot + 1, right);
}
quick_sort.go
/* Быстрая сортировка */
func (q *quickSort) quickSort(nums []int, left, right int) {
    // Завершить рекурсию, когда длина подмассива равна 1
    if left >= right {
        return
    }
    // Разбиение с опорными указателями
    pivot := q.partition(nums, left, right)
    // Рекурсивно обработать левый и правый подмассивы
    q.quickSort(nums, left, pivot-1)
    q.quickSort(nums, pivot+1, right)
}
quick_sort.swift
/* Быстрая сортировка */
func quickSort(nums: inout [Int], left: Int, right: Int) {
    // Завершить рекурсию, когда длина подмассива равна 1
    if left >= right {
        return
    }
    // Разбиение с опорными указателями
    let pivot = partition(nums: &nums, left: left, right: right)
    // Рекурсивно обработать левый и правый подмассивы
    quickSort(nums: &nums, left: left, right: pivot - 1)
    quickSort(nums: &nums, left: pivot + 1, right: right)
}
quick_sort.js
/* Быстрая сортировка */
quickSort(nums, left, right) {
    // Завершить рекурсию, когда длина подмассива равна 1
    if (left >= right) return;
    // Разбиение с опорными указателями
    const pivot = this.partition(nums, left, right);
    // Рекурсивно обработать левый и правый подмассивы
    this.quickSort(nums, left, pivot - 1);
    this.quickSort(nums, pivot + 1, right);
}
quick_sort.ts
/* Быстрая сортировка */
quickSort(nums: number[], left: number, right: number): void {
    // Завершить рекурсию, когда длина подмассива равна 1
    if (left >= right) {
        return;
    }
    // Разбиение с опорными указателями
    const pivot = this.partition(nums, left, right);
    // Рекурсивно обработать левый и правый подмассивы
    this.quickSort(nums, left, pivot - 1);
    this.quickSort(nums, pivot + 1, right);
}
quick_sort.dart
/* Быстрая сортировка */
void quickSort(List<int> nums, int left, int right) {
  // Завершить рекурсию, когда длина подмассива равна 1
  if (left >= right) return;
  // Разбиение с опорными указателями
  int pivot = _partition(nums, left, right);
  // Рекурсивно обработать левый и правый подмассивы
  quickSort(nums, left, pivot - 1);
  quickSort(nums, pivot + 1, right);
}
quick_sort.rs
/* Быстрая сортировка */
pub fn quick_sort(left: i32, right: i32, nums: &mut [i32]) {
    // Завершить рекурсию, когда длина подмассива равна 1
    if left >= right {
        return;
    }
    // Разбиение с опорными указателями
    let pivot = Self::partition(nums, left as usize, right as usize) as i32;
    // Рекурсивно обработать левый и правый подмассивы
    Self::quick_sort(left, pivot - 1, nums);
    Self::quick_sort(pivot + 1, right, nums);
}
quick_sort.c
/* Быстрая сортировка */
void quickSort(int nums[], int left, int right) {
    // Завершить рекурсию, когда длина подмассива равна 1
    if (left >= right) {
        return;
    }
    // Разбиение с опорными указателями
    int pivot = partition(nums, left, right);
    // Рекурсивно обработать левый и правый подмассивы
    quickSort(nums, left, pivot - 1);
    quickSort(nums, pivot + 1, right);
}
quick_sort.kt
/* Быстрая сортировка */
fun quickSort(nums: IntArray, left: Int, right: Int) {
    // Завершить рекурсию, когда длина подмассива равна 1
    if (left >= right) return
    // Разбиение с опорными указателями
    val pivot = partition(nums, left, right)
    // Рекурсивно обработать левый и правый подмассивы
    quickSort(nums, left, pivot - 1)
    quickSort(nums, pivot + 1, right)
}
quick_sort.rb
### Класс быстрой сортировки ###
def quick_sort(nums, left, right)
  # Рекурсивно обрабатывать, пока длина подмассива не станет равной 1
  if left < right
    # Разбиение с опорными указателями
    pivot = partition(nums, left, right)
    # Рекурсивно обработать левый и правый подмассивы
    quick_sort(nums, left, pivot - 1)
    quick_sort(nums, pivot + 1, right)
  end
  nums
end
Визуализация кода

11.5.2   Характеристики алгоритма

  • Временная сложность равна \(O(n \log n)\), алгоритм не является адаптивным: в среднем глубина рекурсии при разделении равна \(\log n\) , а суммарное число циклов на каждом уровне равно \(n\) , поэтому общая сложность составляет \(O(n \log n)\) . В худшем случае каждое разделение делит массив длины \(n\) на подмассивы длины \(0\) и \(n - 1\) ; тогда глубина рекурсии достигает \(n\) , на каждом уровне выполняется \(n\) операций, и общая временная сложность вырождается в \(O(n^2)\) .
  • Пространственная сложность равна \(O(n)\), сортировка выполняется на месте: если входной массив полностью отсортирован в обратном порядке, глубина рекурсии достигает худшего случая \(n\) , что требует \(O(n)\) памяти под стек вызовов. При этом сама сортировка выполняется в исходном массиве без дополнительного массива.
  • Нестабильная сортировка: на последнем шаге разделения опорный элемент может быть обменян вправо от равного ему элемента.

11.5.3   Почему быстрая сортировка быстрая

Уже по названию понятно, что быстрая сортировка должна иметь преимущества по эффективности. Хотя ее средняя временная сложность совпадает со сложностью "сортировки слиянием" и "пирамидальной сортировки", на практике быстрая сортировка обычно работает быстрее. Основные причины таковы.

  • Вероятность худшего случая очень мала: хотя худшая временная сложность быстрой сортировки равна \(O(n^2)\) и она не так стабильна, как сортировка слиянием, в подавляющем большинстве случаев она работает за \(O(n \log n)\) .
  • Высокая эффективность использования кэша: при выполнении разделения система может загрузить весь подмассив в кэш, поэтому доступ к элементам оказывается быстрым. Алгоритмы вроде "пирамидальной сортировки" требуют скачкообразного доступа к элементам и таким свойством не обладают.
  • Небольшой константный множитель в сложности: среди трех перечисленных алгоритмов у быстрой сортировки обычно меньше всего сравнений, присваиваний и обменов. Это похоже на причину, по которой "сортировка вставками" часто быстрее "сортировки пузырьком".

11.5.4   Оптимизация выбора опорного элемента

На некоторых входных данных временная эффективность быстрой сортировки может ухудшаться. Рассмотрим крайний случай: входной массив полностью отсортирован в обратном порядке. Поскольку в качестве опорного мы выбираем самый левый элемент, после разделения он будет обменян в самый правый конец массива, из-за чего длина левого подмассива станет \(n - 1\) , а длина правого - \(0\) . Если рекурсия будет продолжаться таким образом, то после каждого разделения один из подмассивов будет иметь длину \(0\) , стратегия divide and conquer потеряет смысл, а быстрая сортировка выродится в нечто близкое к "сортировке пузырьком".

Чтобы по возможности избежать такого сценария, мы можем улучшить стратегию выбора опорного элемента в процедуре разделения. Например, можно выбирать случайный элемент массива как опорный. Однако если не повезет и каждый раз будет выбираться неудачный опорный элемент, производительность все равно останется неудовлетворительной.

Нужно учитывать, что языки программирования обычно генерируют "псевдослучайные числа". Если специально построить тестовый пример под такую последовательность, эффективность быстрой сортировки все равно может деградировать.

Чтобы улучшить ситуацию, можно взять три кандидата (обычно первый, последний и средний элементы массива) и использовать медиану этих трех значений как опорный элемент. Благодаря этому вероятность того, что опорный элемент окажется "не слишком маленьким и не слишком большим", заметно возрастает. Конечно, можно брать и большее число кандидатов, чтобы еще сильнее повысить устойчивость алгоритма. После этого вероятность деградации временной сложности до \(O(n^2)\) существенно уменьшается.

Пример кода:

quick_sort.py
def median_three(self, nums: list[int], left: int, mid: int, right: int) -> int:
    """Выбрать медиану из трех кандидатов"""
    l, m, r = nums[left], nums[mid], nums[right]
    if (l <= m <= r) or (r <= m <= l):
        return mid  # m находится между l и r
    if (m <= l <= r) or (r <= l <= m):
        return left  # l находится между m и r
    return right

def partition(self, nums: list[int], left: int, right: int) -> int:
    """Разбиение с опорными указателями (медиана трех)"""
    # Взять nums[left] в качестве опорного элемента
    med = self.median_three(nums, left, (left + right) // 2, right)
    # Переместить медиану в крайний левый элемент массива
    nums[left], nums[med] = nums[med], nums[left]
    # Взять nums[left] в качестве опорного элемента
    i, j = left, right
    while i < j:
        while i < j and nums[j] >= nums[left]:
            j -= 1  # Идти справа налево в поисках первого элемента меньше опорного
        while i < j and nums[i] <= nums[left]:
            i += 1  # Идти слева направо в поисках первого элемента больше опорного
        # Обмен элементов
        nums[i], nums[j] = nums[j], nums[i]
    # Переместить опорный элемент на границу двух подмассивов
    nums[i], nums[left] = nums[left], nums[i]
    return i  # Вернуть индекс опорного элемента
quick_sort.cpp
/* Выбрать медиану из трех кандидатов */
int medianThree(vector<int> &nums, int left, int mid, int right) {
    int l = nums[left], m = nums[mid], r = nums[right];
    if ((l <= m && m <= r) || (r <= m && m <= l))
        return mid; // m находится между l и r
    if ((m <= l && l <= r) || (r <= l && l <= m))
        return left; // l находится между m и r
    return right;
}

/* Разбиение с опорными указателями (медиана трех) */
int partition(vector<int> &nums, int left, int right) {
    // Выбрать медиану из трех кандидатов
    int med = medianThree(nums, left, (left + right) / 2, right);
    // Переместить медиану в крайний левый элемент массива
    swap(nums[left], nums[med]);
    // Взять nums[left] в качестве опорного элемента
    int i = left, j = right;
    while (i < j) {
        while (i < j && nums[j] >= nums[left])
            j--;                // Идти справа налево в поисках первого элемента меньше опорного
        while (i < j && nums[i] <= nums[left])
            i++;                // Идти слева направо в поисках первого элемента больше опорного
        swap(nums[i], nums[j]); // Поменять эти два элемента местами
    }
    swap(nums[i], nums[left]);  // Переместить опорный элемент на границу двух подмассивов
    return i;                   // Вернуть индекс опорного элемента
}
quick_sort.java
/* Выбрать медиану из трех кандидатов */
int medianThree(int[] nums, int left, int mid, int right) {
    int l = nums[left], m = nums[mid], r = nums[right];
    if ((l <= m && m <= r) || (r <= m && m <= l))
        return mid; // m находится между l и r
    if ((m <= l && l <= r) || (r <= l && l <= m))
        return left; // l находится между m и r
    return right;
}

/* Разбиение с опорными указателями (медиана трех) */
int partition(int[] nums, int left, int right) {
    // Выбрать медиану из трех кандидатов
    int med = medianThree(nums, left, (left + right) / 2, right);
    // Переместить медиану в крайний левый элемент массива
    swap(nums, left, med);
    // Взять nums[left] в качестве опорного элемента
    int i = left, j = right;
    while (i < j) {
        while (i < j && nums[j] >= nums[left])
            j--;          // Идти справа налево в поисках первого элемента меньше опорного
        while (i < j && nums[i] <= nums[left])
            i++;          // Идти слева направо в поисках первого элемента больше опорного
        swap(nums, i, j); // Поменять эти два элемента местами
    }
    swap(nums, i, left);  // Переместить опорный элемент на границу двух подмассивов
    return i;             // Вернуть индекс опорного элемента
}
quick_sort.cs
/* Выбрать медиану из трех кандидатов */
int MedianThree(int[] nums, int left, int mid, int right) {
    int l = nums[left], m = nums[mid], r = nums[right];
    if ((l <= m && m <= r) || (r <= m && m <= l))
        return mid; // m находится между l и r
    if ((m <= l && l <= r) || (r <= l && l <= m))
        return left; // l находится между m и r
    return right;
}

/* Разбиение с опорными указателями (медиана трех) */
int Partition(int[] nums, int left, int right) {
    // Выбрать медиану из трех кандидатов
    int med = MedianThree(nums, left, (left + right) / 2, right);
    // Переместить медиану в крайний левый элемент массива
    Swap(nums, left, med);
    // Взять nums[left] в качестве опорного элемента
    int i = left, j = right;
    while (i < j) {
        while (i < j && nums[j] >= nums[left])
            j--;          // Идти справа налево в поисках первого элемента меньше опорного
        while (i < j && nums[i] <= nums[left])
            i++;          // Идти слева направо в поисках первого элемента больше опорного
        Swap(nums, i, j); // Поменять эти два элемента местами
    }
    Swap(nums, i, left);  // Переместить опорный элемент на границу двух подмассивов
    return i;             // Вернуть индекс опорного элемента
}
quick_sort.go
/* Выбрать медиану из трех кандидатов */
func (q *quickSortMedian) medianThree(nums []int, left, mid, right int) int {
    l, m, r := nums[left], nums[mid], nums[right]
    if (l <= m && m <= r) || (r <= m && m <= l) {
        return mid // m находится между l и r
    }
    if (m <= l && l <= r) || (r <= l && l <= m) {
        return left // l находится между m и r
    }
    return right
}

/* Разбиение с опорными указателями (медиана трех) */
func (q *quickSortMedian) partition(nums []int, left, right int) int {
    // Взять nums[left] в качестве опорного элемента
    med := q.medianThree(nums, left, (left+right)/2, right)
    // Переместить медиану в крайний левый элемент массива
    nums[left], nums[med] = nums[med], nums[left]
    // Взять nums[left] в качестве опорного элемента
    i, j := left, right
    for i < j {
        for i < j && nums[j] >= nums[left] {
            j-- // Идти справа налево в поисках первого элемента меньше опорного
        }
        for i < j && nums[i] <= nums[left] {
            i++ // Идти слева направо в поисках первого элемента больше опорного
        }
        // Обмен элементов
        nums[i], nums[j] = nums[j], nums[i]
    }
    // Переместить опорный элемент на границу двух подмассивов
    nums[i], nums[left] = nums[left], nums[i]
    return i // Вернуть индекс опорного элемента
}
quick_sort.swift
/* Выбрать медиану из трех кандидатов */
func medianThree(nums: [Int], left: Int, mid: Int, right: Int) -> Int {
    let l = nums[left]
    let m = nums[mid]
    let r = nums[right]
    if (l <= m && m <= r) || (r <= m && m <= l) {
        return mid // m находится между l и r
    }
    if (m <= l && l <= r) || (r <= l && l <= m) {
        return left // l находится между m и r
    }
    return right
}

/* Разбиение с опорными указателями (медиана трех) */
func partitionMedian(nums: inout [Int], left: Int, right: Int) -> Int {
    // Выбрать медиану из трех кандидатов
    let med = medianThree(nums: nums, left: left, mid: left + (right - left) / 2, right: right)
    // Переместить медиану в крайний левый элемент массива
    nums.swapAt(left, med)
    return partition(nums: &nums, left: left, right: right)
}
quick_sort.js
/* Выбрать медиану из трех кандидатов */
medianThree(nums, left, mid, right) {
    let l = nums[left],
        m = nums[mid],
        r = nums[right];
    // m находится между l и r
    if ((l <= m && m <= r) || (r <= m && m <= l)) return mid;
    // l находится между m и r
    if ((m <= l && l <= r) || (r <= l && l <= m)) return left;
    return right;
}

/* Разбиение с опорными указателями (медиана трех) */
partition(nums, left, right) {
    // Выбрать медиану из трех кандидатов
    let med = this.medianThree(
        nums,
        left,
        Math.floor((left + right) / 2),
        right
    );
    // Переместить медиану в крайний левый элемент массива
    this.swap(nums, left, med);
    // Взять nums[left] в качестве опорного элемента
    let i = left,
        j = right;
    while (i < j) {
        while (i < j && nums[j] >= nums[left]) j--; // Идти справа налево в поисках первого элемента меньше опорного
        while (i < j && nums[i] <= nums[left]) i++; // Идти слева направо в поисках первого элемента больше опорного
        this.swap(nums, i, j); // Поменять эти два элемента местами
    }
    this.swap(nums, i, left); // Переместить опорный элемент на границу двух подмассивов
    return i; // Вернуть индекс опорного элемента
}
quick_sort.ts
/* Выбрать медиану из трех кандидатов */
medianThree(
    nums: number[],
    left: number,
    mid: number,
    right: number
): number {
    let l = nums[left],
        m = nums[mid],
        r = nums[right];
    // m находится между l и r
    if ((l <= m && m <= r) || (r <= m && m <= l)) return mid;
    // l находится между m и r
    if ((m <= l && l <= r) || (r <= l && l <= m)) return left;
    return right;
}

/* Разбиение с опорными указателями (медиана трех) */
partition(nums: number[], left: number, right: number): number {
    // Выбрать медиану из трех кандидатов
    let med = this.medianThree(
        nums,
        left,
        Math.floor((left + right) / 2),
        right
    );
    // Переместить медиану в крайний левый элемент массива
    this.swap(nums, left, med);
    // Взять nums[left] в качестве опорного элемента
    let i = left,
        j = right;
    while (i < j) {
        while (i < j && nums[j] >= nums[left]) {
            j--; // Идти справа налево в поисках первого элемента меньше опорного
        }
        while (i < j && nums[i] <= nums[left]) {
            i++; // Идти слева направо в поисках первого элемента больше опорного
        }
        this.swap(nums, i, j); // Поменять эти два элемента местами
    }
    this.swap(nums, i, left); // Переместить опорный элемент на границу двух подмассивов
    return i; // Вернуть индекс опорного элемента
}
quick_sort.dart
/* Выбрать медиану из трех кандидатов */
int _medianThree(List<int> nums, int left, int mid, int right) {
  int l = nums[left], m = nums[mid], r = nums[right];
  if ((l <= m && m <= r) || (r <= m && m <= l))
    return mid; // m находится между l и r
  if ((m <= l && l <= r) || (r <= l && l <= m))
    return left; // l находится между m и r
  return right;
}

/* Разбиение с опорными указателями (медиана трех) */
int _partition(List<int> nums, int left, int right) {
  // Выбрать медиану из трех кандидатов
  int med = _medianThree(nums, left, (left + right) ~/ 2, right);
  // Переместить медиану в крайний левый элемент массива
  _swap(nums, left, med);
  // Взять nums[left] в качестве опорного элемента
  int i = left, j = right;
  while (i < j) {
    while (i < j && nums[j] >= nums[left]) j--; // Идти справа налево в поисках первого элемента меньше опорного
    while (i < j && nums[i] <= nums[left]) i++; // Идти слева направо в поисках первого элемента больше опорного
    _swap(nums, i, j); // Поменять эти два элемента местами
  }
  _swap(nums, i, left); // Переместить опорный элемент на границу двух подмассивов
  return i; // Вернуть индекс опорного элемента
}
quick_sort.rs
/* Выбрать медиану из трех кандидатов */
fn median_three(nums: &mut [i32], left: usize, mid: usize, right: usize) -> usize {
    let (l, m, r) = (nums[left], nums[mid], nums[right]);
    if (l <= m && m <= r) || (r <= m && m <= l) {
        return mid; // m находится между l и r
    }
    if (m <= l && l <= r) || (r <= l && l <= m) {
        return left; // l находится между m и r
    }
    right
}

/* Разбиение с опорными указателями (медиана трех) */
fn partition(nums: &mut [i32], left: usize, right: usize) -> usize {
    // Выбрать медиану из трех кандидатов
    let med = Self::median_three(nums, left, (left + right) / 2, right);
    // Переместить медиану в крайний левый элемент массива
    nums.swap(left, med);
    // Взять nums[left] в качестве опорного элемента
    let (mut i, mut j) = (left, right);
    while i < j {
        while i < j && nums[j] >= nums[left] {
            j -= 1; // Идти справа налево в поисках первого элемента меньше опорного
        }
        while i < j && nums[i] <= nums[left] {
            i += 1; // Идти слева направо в поисках первого элемента больше опорного
        }
        nums.swap(i, j); // Поменять эти два элемента местами
    }
    nums.swap(i, left); // Переместить опорный элемент на границу двух подмассивов
    i // Вернуть индекс опорного элемента
}
quick_sort.c
/* Выбрать медиану из трех кандидатов */
int medianThree(int nums[], int left, int mid, int right) {
    int l = nums[left], m = nums[mid], r = nums[right];
    if ((l <= m && m <= r) || (r <= m && m <= l))
        return mid; // m находится между l и r
    if ((m <= l && l <= r) || (r <= l && l <= m))
        return left; // l находится между m и r
    return right;
}

/* Разбиение с опорными указателями (медиана трех) */
int partitionMedian(int nums[], int left, int right) {
    // Выбрать медиану из трех кандидатов
    int med = medianThree(nums, left, (left + right) / 2, right);
    // Переместить медиану в крайний левый элемент массива
    swap(nums, left, med);
    // Взять nums[left] в качестве опорного элемента
    int i = left, j = right;
    while (i < j) {
        while (i < j && nums[j] >= nums[left])
            j--; // Идти справа налево в поисках первого элемента меньше опорного
        while (i < j && nums[i] <= nums[left])
            i++;          // Идти слева направо в поисках первого элемента больше опорного
        swap(nums, i, j); // Поменять эти два элемента местами
    }
    swap(nums, i, left); // Переместить опорный элемент на границу двух подмассивов
    return i;            // Вернуть индекс опорного элемента
}
quick_sort.kt
/* Выбрать медиану из трех кандидатов */
fun medianThree(nums: IntArray, left: Int, mid: Int, right: Int): Int {
    val l = nums[left]
    val m = nums[mid]
    val r = nums[right]
    if ((m in l..r) || (m in r..l))
        return mid  // m находится между l и r
    if ((l in m..r) || (l in r..m))
        return left // l находится между m и r
    return right
}

/* Разбиение с опорными указателями (медиана трех) */
fun partitionMedian(nums: IntArray, left: Int, right: Int): Int {
    // Выбрать медиану из трех кандидатов
    val med = medianThree(nums, left, (left + right) / 2, right)
    // Переместить медиану в крайний левый элемент массива
    swap(nums, left, med)
    // Взять nums[left] в качестве опорного элемента
    var i = left
    var j = right
    while (i < j) {
        while (i < j && nums[j] >= nums[left])
            j--                      // Идти справа налево в поисках первого элемента меньше опорного
        while (i < j && nums[i] <= nums[left])
            i++                      // Идти слева направо в поисках первого элемента больше опорного
        swap(nums, i, j)             // Поменять эти два элемента местами
    }
    swap(nums, i, left)              // Переместить опорный элемент на границу двух подмассивов
    return i                         // Вернуть индекс опорного элемента
}
quick_sort.rb
### Выбрать медиану из трех кандидатов ###
def median_three(nums, left, mid, right)
  # Выбрать медиану из трех кандидатов
  _l, _m, _r = nums[left], nums[mid], nums[right]
  # m находится между l и r
  return mid if (_l <= _m && _m <= _r) || (_r <= _m && _m <= _l)
  # l находится между m и r
  return left if (_m <= _l && _l <= _r) || (_r <= _l && _l <= _m)
  return right
end

### Выбрать медиану из трех кандидатов ###
def median_three(nums, left, mid, right)
  # Выбрать медиану из трех кандидатов
  _l, _m, _r = nums[left], nums[mid], nums[right]
  # m находится между l и r
  return mid if (_l <= _m && _m <= _r) || (_r <= _m && _m <= _l)
  # l находится между m и r
  return left if (_m <= _l && _l <= _r) || (_r <= _l && _l <= _m)
  return right
end

# ## Разбиение с опорными указателями (медиана трех) ###
def partition(nums, left, right)
  # ## Использовать nums[left] как опорный элемент
  med = median_three(nums, left, (left + right) / 2, right)
  # Переместить медиану в крайний левый элемент массива
  nums[left], nums[med] = nums[med], nums[left]
  i, j = left, right
  while i < j
    while i < j && nums[j] >= nums[left]
      j -= 1 # Идти справа налево в поисках первого элемента меньше опорного
    end
    while i < j && nums[i] <= nums[left]
      i += 1 # Идти слева направо в поисках первого элемента больше опорного
    end
    # Обмен элементов
    nums[i], nums[j] = nums[j], nums[i]
  end
  # Переместить опорный элемент на границу двух подмассивов
  nums[i], nums[left] = nums[left], nums[i]
  i # Вернуть индекс опорного элемента
end
Визуализация кода

11.5.5   Оптимизация глубины рекурсии

На некоторых входных данных быстрая сортировка может занимать слишком много памяти. Рассмотрим полностью отсортированный входной массив. Пусть длина текущего подмассива в рекурсии равна \(m\) ; тогда после каждого разделения будут получаться левый подмассив длины \(0\) и правый подмассив длины \(m - 1\) . Это означает, что на каждом уровне размер задачи уменьшается совсем немного (лишь на один элемент), а высота дерева рекурсии достигает \(n - 1\) , поэтому требуется \(O(n)\) памяти под стек вызовов.

Чтобы избежать накопления стековых кадров, после каждого разделения можно сравнивать длины двух подмассивов и рекурсивно обрабатывать только более короткий из них. Поскольку длина короткого подмассива не превысит \(n / 2\) , такой подход гарантирует, что глубина рекурсии не превысит \(\log n\) , а худшая пространственная сложность будет оптимизирована до \(O(\log n)\) . Код приведен ниже:

quick_sort.py
def quick_sort(self, nums: list[int], left: int, right: int):
    """Быстрая сортировка (оптимизация глубины рекурсии)"""
    # Завершить, когда длина подмассива равна 1
    while left < right:
        # Операция разбиения с опорными указателями
        pivot = self.partition(nums, left, right)
        # Выполнить быструю сортировку для более короткого из двух подмассивов
        if pivot - left < right - pivot:
            self.quick_sort(nums, left, pivot - 1)  # Рекурсивно отсортировать левый подмассив
            left = pivot + 1  # Оставшийся неотсортированный диапазон: [pivot + 1, right]
        else:
            self.quick_sort(nums, pivot + 1, right)  # Рекурсивно отсортировать правый подмассив
            right = pivot - 1  # Оставшийся неотсортированный диапазон: [left, pivot - 1]
quick_sort.cpp
/* Быстрая сортировка (оптимизация глубины рекурсии) */
void quickSort(vector<int> &nums, int left, int right) {
    // Завершить, когда длина подмассива равна 1
    while (left < right) {
        // Операция разбиения с опорными указателями
        int pivot = partition(nums, left, right);
        // Выполнить быструю сортировку для более короткого из двух подмассивов
        if (pivot - left < right - pivot) {
            quickSort(nums, left, pivot - 1); // Рекурсивно отсортировать левый подмассив
            left = pivot + 1;                 // Оставшийся неотсортированный диапазон: [pivot + 1, right]
        } else {
            quickSort(nums, pivot + 1, right); // Рекурсивно отсортировать правый подмассив
            right = pivot - 1;                 // Оставшийся неотсортированный диапазон: [left, pivot - 1]
        }
    }
}
quick_sort.java
/* Быстрая сортировка (оптимизация глубины рекурсии) */
void quickSort(int[] nums, int left, int right) {
    // Завершить, когда длина подмассива равна 1
    while (left < right) {
        // Операция разбиения с опорными указателями
        int pivot = partition(nums, left, right);
        // Выполнить быструю сортировку для более короткого из двух подмассивов
        if (pivot - left < right - pivot) {
            quickSort(nums, left, pivot - 1); // Рекурсивно отсортировать левый подмассив
            left = pivot + 1; // Оставшийся неотсортированный диапазон: [pivot + 1, right]
        } else {
            quickSort(nums, pivot + 1, right); // Рекурсивно отсортировать правый подмассив
            right = pivot - 1; // Оставшийся неотсортированный диапазон: [left, pivot - 1]
        }
    }
}
quick_sort.cs
/* Быстрая сортировка (оптимизация глубины рекурсии) */
void QuickSort(int[] nums, int left, int right) {
    // Завершить, когда длина подмассива равна 1
    while (left < right) {
        // Операция разбиения с опорными указателями
        int pivot = Partition(nums, left, right);
        // Выполнить быструю сортировку для более короткого из двух подмассивов
        if (pivot - left < right - pivot) {
            QuickSort(nums, left, pivot - 1);  // Рекурсивно отсортировать левый подмассив
            left = pivot + 1;  // Оставшийся неотсортированный диапазон: [pivot + 1, right]
        } else {
            QuickSort(nums, pivot + 1, right); // Рекурсивно отсортировать правый подмассив
            right = pivot - 1; // Оставшийся неотсортированный диапазон: [left, pivot - 1]
        }
    }
}
quick_sort.go
/* Быстрая сортировка (оптимизация глубины рекурсии) */
func (q *quickSortTailCall) quickSort(nums []int, left, right int) {
    // Завершить, когда длина подмассива равна 1
    for left < right {
        // Операция разбиения с опорными указателями
        pivot := q.partition(nums, left, right)
        // Выполнить быструю сортировку для более короткого из двух подмассивов
        if pivot-left < right-pivot {
            q.quickSort(nums, left, pivot-1) // Рекурсивно отсортировать левый подмассив
            left = pivot + 1                 // Оставшийся неотсортированный диапазон: [pivot + 1, right]
        } else {
            q.quickSort(nums, pivot+1, right) // Рекурсивно отсортировать правый подмассив
            right = pivot - 1                 // Оставшийся неотсортированный диапазон: [left, pivot - 1]
        }
    }
}
quick_sort.swift
/* Быстрая сортировка (оптимизация глубины рекурсии) */
func quickSortTailCall(nums: inout [Int], left: Int, right: Int) {
    var left = left
    var right = right
    // Завершить, когда длина подмассива равна 1
    while left < right {
        // Операция разбиения с опорными указателями
        let pivot = partition(nums: &nums, left: left, right: right)
        // Выполнить быструю сортировку для более короткого из двух подмассивов
        if (pivot - left) < (right - pivot) {
            quickSortTailCall(nums: &nums, left: left, right: pivot - 1) // Рекурсивно отсортировать левый подмассив
            left = pivot + 1 // Оставшийся неотсортированный диапазон: [pivot + 1, right]
        } else {
            quickSortTailCall(nums: &nums, left: pivot + 1, right: right) // Рекурсивно отсортировать правый подмассив
            right = pivot - 1 // Оставшийся неотсортированный диапазон: [left, pivot - 1]
        }
    }
}
quick_sort.js
/* Быстрая сортировка (оптимизация глубины рекурсии) */
quickSort(nums, left, right) {
    // Завершить, когда длина подмассива равна 1
    while (left < right) {
        // Операция разбиения с опорными указателями
        let pivot = this.partition(nums, left, right);
        // Выполнить быструю сортировку для более короткого из двух подмассивов
        if (pivot - left < right - pivot) {
            this.quickSort(nums, left, pivot - 1); // Рекурсивно отсортировать левый подмассив
            left = pivot + 1; // Оставшийся неотсортированный диапазон: [pivot + 1, right]
        } else {
            this.quickSort(nums, pivot + 1, right); // Рекурсивно отсортировать правый подмассив
            right = pivot - 1; // Оставшийся неотсортированный диапазон: [left, pivot - 1]
        }
    }
}
quick_sort.ts
/* Быстрая сортировка (оптимизация глубины рекурсии) */
quickSort(nums: number[], left: number, right: number): void {
    // Завершить, когда длина подмассива равна 1
    while (left < right) {
        // Операция разбиения с опорными указателями
        let pivot = this.partition(nums, left, right);
        // Выполнить быструю сортировку для более короткого из двух подмассивов
        if (pivot - left < right - pivot) {
            this.quickSort(nums, left, pivot - 1); // Рекурсивно отсортировать левый подмассив
            left = pivot + 1; // Оставшийся неотсортированный диапазон: [pivot + 1, right]
        } else {
            this.quickSort(nums, pivot + 1, right); // Рекурсивно отсортировать правый подмассив
            right = pivot - 1; // Оставшийся неотсортированный диапазон: [left, pivot - 1]
        }
    }
}
quick_sort.dart
/* Быстрая сортировка (оптимизация глубины рекурсии) */
void quickSort(List<int> nums, int left, int right) {
  // Завершить, когда длина подмассива равна 1
  while (left < right) {
    // Операция разбиения с опорными указателями
    int pivot = _partition(nums, left, right);
    // Выполнить быструю сортировку для более короткого из двух подмассивов
    if (pivot - left < right - pivot) {
      quickSort(nums, left, pivot - 1); // Рекурсивно отсортировать левый подмассив
      left = pivot + 1; // Оставшийся неотсортированный диапазон: [pivot + 1, right]
    } else {
      quickSort(nums, pivot + 1, right); // Рекурсивно отсортировать правый подмассив
      right = pivot - 1; // Оставшийся неотсортированный диапазон: [left, pivot - 1]
    }
  }
}
quick_sort.rs
/* Быстрая сортировка (оптимизация глубины рекурсии) */
pub fn quick_sort(mut left: i32, mut right: i32, nums: &mut [i32]) {
    // Завершить, когда длина подмассива равна 1
    while left < right {
        // Операция разбиения с опорными указателями
        let pivot = Self::partition(nums, left as usize, right as usize) as i32;
        // Выполнить быструю сортировку для более короткого из двух подмассивов
        if pivot - left < right - pivot {
            Self::quick_sort(left, pivot - 1, nums); // Рекурсивно отсортировать левый подмассив
            left = pivot + 1; // Оставшийся неотсортированный диапазон: [pivot + 1, right]
        } else {
            Self::quick_sort(pivot + 1, right, nums); // Рекурсивно отсортировать правый подмассив
            right = pivot - 1; // Оставшийся неотсортированный диапазон: [left, pivot - 1]
        }
    }
}
quick_sort.c
/* Быстрая сортировка (оптимизация глубины рекурсии) */
void quickSortTailCall(int nums[], int left, int right) {
    // Завершить, когда длина подмассива равна 1
    while (left < right) {
        // Операция разбиения с опорными указателями
        int pivot = partition(nums, left, right);
        // Выполнить быструю сортировку для более короткого из двух подмассивов
        if (pivot - left < right - pivot) {
            // Рекурсивно отсортировать левый подмассив
            quickSortTailCall(nums, left, pivot - 1);
            // Оставшийся неотсортированный диапазон: [pivot + 1, right]
            left = pivot + 1;
        } else {
            // Рекурсивно отсортировать правый подмассив
            quickSortTailCall(nums, pivot + 1, right);
            // Оставшийся неотсортированный диапазон: [left, pivot - 1]
            right = pivot - 1;
        }
    }
}
quick_sort.kt
/* Быстрая сортировка (оптимизация глубины рекурсии) */
fun quickSortTailCall(nums: IntArray, left: Int, right: Int) {
    // Завершить, когда длина подмассива равна 1
    var l = left
    var r = right
    while (l < r) {
        // Операция разбиения с опорными указателями
        val pivot = partition(nums, l, r)
        // Выполнить быструю сортировку для более короткого из двух подмассивов
        if (pivot - l < r - pivot) {
            quickSort(nums, l, pivot - 1) // Рекурсивно отсортировать левый подмассив
            l = pivot + 1 // Оставшийся неотсортированный диапазон: [pivot + 1, right]
        } else {
            quickSort(nums, pivot + 1, r) // Рекурсивно отсортировать правый подмассив
            r = pivot - 1 // Оставшийся неотсортированный диапазон: [left, pivot - 1]
        }
    }
}
quick_sort.rb
### Разбиение с опорными указателями ###
def partition(nums, left, right)
  # Использовать nums[left] как опорный элемент
  i = left
  j = right
  while i < j
    while i < j && nums[j] >= nums[left]
      j -= 1 # Идти справа налево в поисках первого элемента меньше опорного
    end
    while i < j && nums[i] <= nums[left]
      i += 1 # Идти слева направо в поисках первого элемента больше опорного
    end
    # Обмен элементов
    nums[i], nums[j] = nums[j], nums[i]
  end
  # Переместить опорный элемент на границу двух подмассивов
  nums[i], nums[left] = nums[left], nums[i]
  i # Вернуть индекс опорного элемента
end

# ## Быстрая сортировка (оптимизация глубины рекурсии) ###
def quick_sort(nums, left, right)
  # Рекурсивно обрабатывать, пока длина подмассива не станет равной 1
  while left < right
    # Разбиение с опорными указателями
    pivot = partition(nums, left, right)
    # Выполнить быструю сортировку для более короткого из двух подмассивов
    if pivot - left < right - pivot
      quick_sort(nums, left, pivot - 1)
      left = pivot + 1 # Оставшийся неотсортированный диапазон: [pivot + 1, right]
    else
      quick_sort(nums, pivot + 1, right)
      right = pivot - 1 # Оставшийся неотсортированный диапазон: [left, pivot - 1]
    end
  end
end
Визуализация кода

Оставляйте свои идеи, вопросы и предложения в комментариях