Быстрая сортировка и выбор опорного элемента
Создайте быструю сортировку со схемами разбиения Ломуто и Хоара, обсудите худшую сложность O(n²) и то, как рандомизированный выбор опорного элемента её уменьшает
«Быстрая сортировка и выбор опорного элемента» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding 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) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Быстрая сортировка и выбор опорного элемента»?
Создайте быструю сортировку со схемами разбиения Ломуто и Хоара, обсудите худшую сложность O(n²) и то, как рандомизированный выбор опорного элемента её уменьшает Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.
Сколько времени занимает урок «Быстрая сортировка и выбор опорного элемента»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Сортировка пузырьком и сортировка вставками
- Сортировка слиянием: разделить, отсортировать, объединить
- Быстрая сортировка и выбор опорного элемента
- Сортировки без сравнений и sort() в Python