Ошибка
- В строке возврата используется рекурсивный вызов для `middle` вместо `right`. Из-за этого при наличии более одного элемента, равного опорному, алгоритм рекурсивно вызывает `quicksort(middle)` бесконечно. Пример: $a=[2,2,2]$, опорный элемент $pivot=2$, тогда $left=[]$, $middle=[2,2,2]$, $right=[]$. Условие $len(a)\le 1$ не выполняется, и вызов `quicksort(middle)` повторяет ту же ситуацию бесконечно.
Сложность
- Средняя временная: $O(n\log n)$.
- Худшая временная (плохой выбор опорного): $O(n^2)$.
- Дополнительная память: $O(n)$ (создаются новые списки).
- Глубина рекурсии: в среднем $O(\log n)$, в худшем случае $O(n)$.
Исправленный вариант (минимальное исправление)
def quicksort(a):
if len(a) <= 1:
return a
pivot = a[len(a)//2]
left = [x for x in a if x < pivot]
middle = [x for x in a if x == pivot]
right = [x for x in a if x > pivot]
return quicksort(left) + middle + quicksort(right)
Замечания и улучшения
- Для устойчивого избежания худшего случая выбирайте случайный или медианный по трём пунктов pivot.
- Для экономии памяти можно реализовать быструю сортировку in-place (разбиение Хоара).