DSA Interview Prep · Урок

Быстрая сортировка и выбор опорного элемента

Создайте быструю сортировку со схемами разбиения Ломуто и Хоара, обсудите худшую сложность O(n²) и то, как рандомизированный выбор опорного элемента её уменьшает

«Быстрая сортировка и выбор опорного элемента» — бесплатный урок DSA Interview Prep на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения DSA Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс DSA Interview Prep содержит 4 уроков всего.

Быстрая сортировка: стратегия «разделяй и властвуй» на месте

Быстрая сортировка — наиболее широко используемый на практике алгоритм сортировки. В отличие от сортировки слиянием, она выполняется на месте, не выделяя дополнительные массивы. Основная идея: выбрать опорный элемент, разделить массив так, чтобы все элементы, меньшие опорного, оказались перед ним, а большие — после него, затем рекурсивно отсортировать каждую часть. Этап разбиения занимает O(n), а при удачном выборе опорного элемента глубина рекурсии составляет O(log n).

def quick_sort(arr, lo=0, hi=None):
    if hi is None: hi = len(arr) - 1
    if lo < hi:
        pivot_idx = partition(arr, lo, hi)
        quick_sort(arr, lo, pivot_idx - 1)  # sort left
        quick_sort(arr, pivot_idx + 1, hi)  # sort right

def partition(arr, lo, hi):
    pivot = arr[hi]  # Lomuto: choose last element as pivot
    i = lo - 1
    for j in range(lo, hi):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[hi] = arr[hi], arr[i+1]
    return i + 1

arr = [3, 6, 8, 10, 1, 2, 1]
quick_sort(arr)
print(arr)  # [1, 1, 2, 3, 6, 8, 10]

Схема разбиения Ломуто

Разбиение Ломуто использует последний элемент как опорный. Медленный указатель i отслеживает границу области элементов, меньших опорного, а быстрый указатель j сканирует массив слева направо. Когда выполняется условие arr[j] <= pivot, увеличьте i и обменяйте местами arr[i] и arr[j], расширив область маленьких элементов. После сканирования поместите опорный элемент на позицию i+1, обменяв его с arr[hi]. Реализовать этот вариант просто, но он выполняет в 3 раза больше перестановок, чем схема Хоара.

def lomuto_partition_traced(arr, lo, hi):
    pivot = arr[hi]
    i = lo - 1
    print(f'Pivot: {pivot}, array: {arr[lo:hi+1]}')
    for j in range(lo, hi):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[hi] = arr[hi], arr[i+1]
    print(f'After partition: {arr[lo:hi+1]}')
    return i + 1

arr = [3, 1, 4, 1, 5, 9, 2, 6]
lomuto_partition_traced(arr, 0, len(arr)-1)

Схема разбиения Хоара

Разбиение Хоара использует два указателя, начинающихся с обоих концов и движущихся навстречу друг другу, пока не пересекутся. Оно выбирает опорный элемент (обычно первый) и перемещает элементы, меньшие опорного, влево, а большие — вправо. Схема Хоара выполняет в 3 раза меньше перестановок, чем схема Ломуто, и лучше работает с одинаковыми элементами, но после разбиения опорный элемент не оказывается на своей окончательной позиции — поэтому требуются немного другие рекурсивные вызовы.

def hoare_partition(arr, lo, hi):
    pivot = arr[lo]  # first element as pivot
    i, j = lo - 1, hi + 1
    while True:
        i += 1
        while arr[i] < pivot: i += 1
        j -= 1
        while arr[j] > pivot: j -= 1
        if i >= j: return j
        arr[i], arr[j] = arr[j], arr[i]

def quick_sort_hoare(arr, lo=0, hi=None):
    if hi is None: hi = len(arr) - 1
    if lo < hi:
        p = hoare_partition(arr, lo, hi)
        quick_sort_hoare(arr, lo, p)      # note: p not p-1
        quick_sort_hoare(arr, p+1, hi)

arr = [3, 6, 8, 10, 1, 2, 1]
quick_sort_hoare(arr)
print(arr)  # [1, 1, 2, 3, 6, 8, 10]

Худший случай O(n²): уже отсортированные входные данные

Худший случай быстрой сортировки возникает, когда опорным элементом постоянно оказывается наименьший или наибольший элемент части массива. При использовании последнего элемента в качестве опорного в схеме Ломуто для уже отсортированного массива разбиение всегда оставляет слева 0 элементов, а справа — n-1: дерево рекурсии вырождается в цепочку глубины n, что даёт O(n²) сравнений. Поэтому выбор опорного элемента критически важен, а промышленные реализации используют случайный выбор опорного элемента.

import sys
sys.setrecursionlimit(5000)

def quick_sort_naive(arr, lo=0, hi=None):
    if hi is None: hi = len(arr) - 1
    comparisons = [0]
    def _qs(lo, hi):
        if lo >= hi: return
        pivot = arr[hi]  # last element pivot
        i = lo - 1
        for j in range(lo, hi):
            comparisons[0] += 1
            if arr[j] <= pivot:
                i += 1; arr[i], arr[j] = arr[j], arr[i]
        arr[i+1], arr[hi] = arr[hi], arr[i+1]
        p = i + 1
        _qs(lo, p-1); _qs(p+1, hi)
    _qs(lo, hi)
    return comparisons[0]

import math
n = 100
sorted_arr = list(range(n))
ops = quick_sort_naive(sorted_arr)
print(f'n={n}, ops={ops}, n^2={n**2}')  # ops close to n*(n-1)/2

Случайный опорный элемент: ожидаемое O(n log n)

Если выбирать опорный элемент равновероятно случайным образом (перед разбиением обменивать случайный элемент с arr[hi]), вероятность постоянно выбирать неудачные опорные элементы экспоненциально снижается. Ожидаемое число сравнений равно 2n ln(n) ≈ 1.39 n log₂(n), что даёт ожидаемое время O(n log n) с подавляющей вероятностью. Поэтому на практике используется быстрая сортировка со случайным выбором опорного элемента: она позволяет избежать патологических худших случаев, которые противник мог бы создать для стратегий с фиксированным опорным элементом.

import random

def quick_sort_random(arr, lo=0, hi=None):
    if hi is None: hi = len(arr) - 1
    if lo < hi:
        # Randomise pivot
        rand_i = random.randint(lo, hi)
        arr[rand_i], arr[hi] = arr[hi], arr[rand_i]
        # Lomuto partition with last element as pivot
        pivot = arr[hi]
        i = lo - 1
        for j in range(lo, hi):
            if arr[j] <= pivot:
                i += 1; arr[i], arr[j] = arr[j], arr[i]
        arr[i+1], arr[hi] = arr[hi], arr[i+1]
        p = i + 1
        quick_sort_random(arr, lo, p - 1)
        quick_sort_random(arr, p + 1, hi)

arr = list(range(100, 0, -1))  # worst case for naive
quick_sort_random(arr)
print(arr[:10])  # [1,2,3,4,5,6,7,8,9,10]

Опорный элемент — медиана трёх

Другая стратегия выбора опорного элемента — взять медиану первого, среднего и последнего элементов. Это позволяет избежать худшего поведения на отсортированных или отсортированных в обратном порядке входных данных (наиболее распространённых входных данных для атак), не создавая затрат на генерацию случайных чисел. Многие промышленные реализации используют медиану трёх или медиану трёх медиан для больших массивов и переходят к сортировке вставками для маленьких подмассивов размером менее порога примерно в 10 элементов.

def median_of_three(arr, lo, hi):
    mid = (lo + hi) // 2
    # Sort lo, mid, hi values in place
    if arr[lo] > arr[mid]:  arr[lo], arr[mid] = arr[mid], arr[lo]
    if arr[lo] > arr[hi]:   arr[lo], arr[hi]  = arr[hi],  arr[lo]
    if arr[mid] > arr[hi]:  arr[mid], arr[hi] = arr[hi],  arr[mid]
    # Median is now at arr[mid]; swap to arr[hi-1] as pivot
    arr[mid], arr[hi] = arr[hi], arr[mid]
    return arr[hi]  # pivot value

arr = [3, 9, 1]
print(median_of_three(arr, 0, 2), arr)  # 3, [1,3,9] (sorted)

Голландский национальный флаг: трёхстороннее разбиение

Обычное разбиение помещает элементы, меньшие опорного, слева, а большие — справа, но элементы, равные опорному, оказываются распределены по разным местам. Трёхстороннее разбиение (метод голландского национального флага) создаёт три области: <pivot, ==pivot, >pivot. Это особенно важно для массивов с большим количеством повторяющихся элементов: обычная быстрая сортировка на них вырождается до O(n²), тогда как трёхсторонняя быстрая сортировка работает за O(n) для входных данных, состоящих из одинаковых значений.

def three_way_partition(arr, lo, hi):
    pivot = arr[lo]
    lt = lo      # arr[lo..lt-1] < pivot
    gt = hi      # arr[gt+1..hi] > pivot
    i = lo       # current
    while i <= gt:
        if arr[i] < pivot:
            arr[lt], arr[i] = arr[i], arr[lt]
            lt += 1; i += 1
        elif arr[i] > pivot:
            arr[i], arr[gt] = arr[gt], arr[i]
            gt -= 1  # don't advance i
        else:
            i += 1
    return lt, gt  # pivot occupies arr[lt..gt]

arr = [3, 1, 4, 1, 5, 9, 2, 6, 3, 3]
lt, gt = three_way_partition(arr, 0, len(arr)-1)
print(arr, '| pivot region:', lt, 'to', gt)

Быстрый выбор: k-й наименьший элемент за O(n)

quickselect использует этап разбиения быстрой сортировки, чтобы найти k-й наименьший элемент в среднем за O(n), не выполняя полную сортировку. После разбиения опорный элемент находится на своей окончательной позиции p. Если p == k, верните arr[p]. Если k < p, рекурсивно обработайте левую часть; если k > p — правую. В среднем каждый рекурсивный вызов вдвое уменьшает задачу: O(n) + O(n/2) + O(n/4) + ... = O(2n) = O(n).

import random

def quickselect(nums, k):
    '''Find kth smallest (0-indexed) in O(n) average.'''
    def _select(lo, hi):
        if lo == hi: return nums[lo]
        rand_i = random.randint(lo, hi)
        nums[rand_i], nums[hi] = nums[hi], nums[rand_i]
        pivot = nums[hi]
        i = lo - 1
        for j in range(lo, hi):
            if nums[j] <= pivot:
                i += 1; nums[i], nums[j] = nums[j], nums[i]
        p = i + 1
        nums[p], nums[hi] = nums[hi], nums[p]
        if p == k:    return nums[p]
        elif k < p:   return _select(lo, p - 1)
        else:         return _select(p + 1, hi)
    return _select(0, len(nums) - 1)

print(quickselect([3,2,1,5,6,4], 1))  # 2  (2nd smallest)

Сложность быстрой сортировки по памяти

Быструю сортировку называют выполняемой «на месте», но для рекурсии она использует в среднем O(log n) памяти стека (по одной записи на каждом уровне дерева рекурсии). В худшем случае глубина стека составляет O(n). Чтобы гарантировать в худшем случае O(log n) памяти стека, всегда рекурсивно обрабатывайте сначала меньшую часть и применяйте оптимизацию хвостовых вызовов для большей части. Ограничение глубины рекурсии Python делает очень глубокую рекурсию быстрой сортировки рискованной — об этом стоит упомянуть на собеседовании.

def quick_sort_optimised(arr, lo=0, hi=None):
    if hi is None: hi = len(arr) - 1
    while lo < hi:
        p = lomuto_partition_qs(arr, lo, hi)
        # Recurse on smaller partition; iterate on larger
        if p - lo < hi - p:
            quick_sort_optimised(arr, lo, p - 1)
            lo = p + 1  # tail-call elimination
        else:
            quick_sort_optimised(arr, p + 1, hi)
            hi = p - 1

def lomuto_partition_qs(arr, lo, hi):
    pivot = arr[hi]; i = lo - 1
    for j in range(lo, hi):
        if arr[j] <= pivot: i += 1; arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[hi] = arr[hi], arr[i+1]
    return i + 1

Сравнение алгоритмов сортировки

Обобщите свои знания:

Быстрая сортировка: ожидаемое O(n log n), O(n²) в худшем случае, память O(log n), нестабильна, быстрее всего работает на практике со случайными данными
Сортировка слиянием: гарантированное O(n log n), память O(n), стабильна, лучше всего подходит для связанных списков и внешней сортировки
Сортировка кучей: гарантированное O(n log n), память O(1), нестабильна, на практике медленнее из-за промахов кэша
Сортировка вставками: O(n) в лучшем случае, идеальна для небольших n или почти отсортированных данных

На собеседованиях обоснуйте свой выбор с учётом этих компромиссов.

# Python's sorted() uses Timsort:
# - Hybrid: merge sort for large runs, insertion sort for small (< 64 elements)
# - Stable, O(n log n) worst case
# - O(n) best case for sorted/reverse-sorted/nearly-sorted
# - O(n) extra space

import random
arr = random.sample(range(10000), 1000)
sorted_arr = sorted(arr)  # Timsort
print(sorted_arr[:5], '...')  # first 5 elements

Интросорт: объединение трёх алгоритмов

Интросорт (используется в C++ STL std::sort) сочетает быструю сортировку, сортировку кучей и сортировку вставками: начинается со случайной быстрой сортировки; если глубина рекурсии превышает 2 log n (что указывает на последовательность неудачных опорных элементов), выполняется переключение на сортировку кучей, гарантирующую O(n log n); для подмассивов размером менее 16 элементов используется сортировка вставками. В результате обеспечивается O(n log n) в худшем случае, средняя скорость быстрой сортировки и эффективность сортировки вставками на небольших подмассивах.

# Introsort hybrid (simplified)
def introsort(arr, depth_limit=None):
    if depth_limit is None:
        import math
        depth_limit = 2 * int(math.log2(len(arr) + 1)) if arr else 0
    if len(arr) <= 16:
        # insertion sort for small arrays
        for i in range(1, len(arr)):
            key = arr[i]; j = i - 1
            while j >= 0 and arr[j] > key:
                arr[j+1] = arr[j]; j -= 1
            arr[j+1] = key
        return arr
    if depth_limit == 0:
        arr.sort()  # fall back to heapsort equivalent
        return arr
    # Otherwise quick sort
    pivot = arr[-1]
    small = [x for x in arr[:-1] if x <= pivot]
    large = [x for x in arr[:-1] if x > pivot]
    return introsort(small, depth_limit-1) + [pivot] + introsort(large, depth_limit-1)

print(introsort([5,3,8,1,9,2,7]))

Быстрая проверка

Проверьте своё понимание концепций структур данных и алгоритмов — подготовки к собеседованию по программированию, рассмотренных в этом уроке.

Итоги урока

В этом уроке Вы узнали, что быстрая сортировка выполняет разбиение на месте относительно опорного элемента и рекурсивно обрабатывает обе стороны, достигая ожидаемого времени O(n log n) при использовании O(log n) памяти стека — и на случайных данных работает на практике быстрее сортировки слиянием, худший случай O(n²) возникает на отсортированных входных данных при фиксированном опорном элементе и предотвращается случайным выбором опорного элемента или использованием медианы трёх, а также что трёхстороннее разбиение эффективно обрабатывает повторяющиеся элементы, а quickselect расширяет идею разбиения и позволяет найти k-й наименьший элемент в среднем за O(n) без полной сортировки. Далее мы изучим сортировки, не основанные на сравнениях, и встроенную сортировку Python.

Часто задаваемые вопросы

Урок «Быстрая сортировка и выбор опорного элемента» бесплатный?

Да — полный текст урока «Быстрая сортировка и выбор опорного элемента» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс DSA Interview Prep, подпишись на CoddyKit PRO. Курс DSA Interview Prep содержит 4 уроков всего.

Чему я научусь в уроке «Быстрая сортировка и выбор опорного элемента»?

Создайте быструю сортировку со схемами разбиения Ломуто и Хоара, обсудите худшую сложность O(n²) и то, как рандомизированный выбор опорного элемента её уменьшает Ты практикуешь DSA Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать DSA Interview Prep?

Предыдущий опыт не требуется. DSA Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.

Сколько времени занимает урок «Быстрая сортировка и выбор опорного элемента»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке DSA Interview Prep?

Да. Каждый урок DSA Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

Сортировка пузырьком и сортировка вставками
Сортировка слиянием: разделить, отсортировать, объединить
Быстрая сортировка и выбор опорного элемента
Сортировки без сравнений и sort() в Python

← Назад к DSA Interview Prep