Когда алгоритм делает выбор опорного элемента как первый элемент списка (как в вашем коде), он работает за квадратичное время на входах, где опорный элемент даёт крайне неравные разбиения: например, на уже упорядоченных массивах (возрастающем или убывающем) с различными элементами. Формально: при таких входах рекуррентное соотношение превращается в $T(n)=T(n-1)+\Theta (n)$, что даёт худшее время $\Theta (n^2)$.
Примеры входов, вызывающих худший случай
- отсортированный по возрастанию массив, e.g. $[1,2,3,\dots ]$;
- отсортированный по убыванию массив;
- любой массив, где выбранный (первый) элемент постоянно оказывается минимальным или максимальным.
Практические последствия
- Время выполнения возрастает до $\Theta (n^2)$ — для больших $n$ это делает алгоритм непригодным.
- Глубина рекурсии может достигать $\Theta (n)$, что приводит к переполнению стека (RecursionError в Python).
- Текущая реализация копирует списки на каждом уровне (списки left/equal/right), поэтому при глубокой рекурсии суммарно выделяется много памяти и выполняется много копирований — дополнительные накладные расходы (в худшем случае суммарные выделения могут быть квадратичными по объёму).
Как модифицировать код для надёжности
1) Самый простой и эффективный при практической работе — перемешать вход перед сортировкой:
- делать `random.shuffle(a)` перед вызовом quicksort; тогда ожидаемое время становится $O(n\log n)$ для любого входа (вредоносные паттерны уничтожаются).
2) Выбирать случайный опорный элемент в каждой рекурсии:
- `pivot = random.choice(a)` (или выбрать случайный индекс и сделать swap с первым). Это даёт ожидаемое время $O(n\log n)$ и низкую вероятность квадратичного поведения.
3) Улучшенный детерминированный выбор опоры:
- median-of-three: брать медиану из `a[0]`, `a[len(a)//2]`, `a[-1]` — снижает шанс плохого разбиения на «почти упорядоченных» данных.
4) Избежать множества копирований и глубокой рекурсии — реализовать in-place partition (Lomuto или Hoare) и делать хвостовую рекурсию/итеративный контроль стека; это уменьшит потребление памяти и риск переполнения стека.
5) Гарантированный худший случай — Introsort: выполнять quicksort (со случайным/median-of-three опорным) и при превышении глубины рекурсии (обычно порог около $2{\log }_{2}n$) переключиться на heapsort. Introsort даёт гарантированное время $O(n\log n)$ в худшем случае и практическую скорость quicksort в среднем.
Короткие примеры (идеи реализации)
- Перемешивание:
def quicksort(a):
import random
random.shuffle(a)
# тут можно использовать ваш рекурсивный код или in-place вариант
...
- Рандомный опорный:
def quicksort(a):
import random
if len(a) <= 1: return a
pivot = random.choice(a)
left = [x for x in a if x < pivot]
equal = [x for x in a if x == pivot]
right = [x for x in a if x > pivot]
return quicksort(left) + equal + quicksort(right)
- Интроспективный подход (схема): запускать quicksort с подсчётом глубины, если глубина > $2{\log }_{2}n$ — вызвать heapsort для оставшегося подмассива.
Резюме:
- Причина квадратичного поведения — плохий детерминистический выбор опорного (первый элемент) на упорядоченных или специально подобранных входах → $\Theta (n^2)$.
- Практические проблемы: резкое замедление, глубокая рекурсия, много копирований/памяти.
- Простые надёжные исправления: перемешивание входа или выбор случайного опорного; для строгих гарантий — Introsort (переключение на heapsort при глубокой рекурсии) и/или in-place partitioning.