Проблема
- В коде удаляются все элементы, равные опорному, кроме самого опорного:
left = [x for x in a if x pivot] — элементы с x == pivot пропускаются и теряются (например, при всех элементах равных возвращается один элемент).
Исправления (коротко)
1) Трёхчастная версиия (простая, стабильная, использует доп. память):
```python
def quicksort(a):
if len(a) <= 1:
return a
pivot = a[0]
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)
```
- Эта версия сохраняет порядок равных элементов (стабильна при использовании list-comprehensions).
2) Быстрая in-place версия для множественных одинаковых элементов (Dutch National Flag, эффективна по памяти):
```python
import random
def quicksort_inplace(a, lo=0, hi=None):
if hi is None:
hi = len(a) - 1
if lo >= hi:
return
# случайный опорный элемент для защиты от худшего случая
p = random.randint(lo, hi)
pivot = a[p]
# 3-way partition: pivot
i, lt, gt = lo, lo, hi
while i <= gt:
if a[i] < pivot:
a[lt], a[i] = a[i], a[lt]; lt += 1; i += 1
elif a[i] > pivot:
a[i], a[gt] = a[gt], a[i]; gt -= 1
else:
i += 1
quicksort_inplace(a, lo, lt-1)
quicksort_inplace(a, gt+1, hi)
```
- Эта версия не стабильна, но работает in-place и очень хорошо с большим числом повторов.
Устойчивость (stability)
- Стандартный in-place quicksort — неустойчив (порядок равных элементов может изменяться).
- Версия с list-comprehensions и явно выделенной equal-частью — стабильна (поскольку относительный порядок равных элементов сохраняется при фильтрации и конкатенации).
Вычислительная сложность
- Обозначим размер входа $n$.
- Лучший случай (хорошо сбалансированные разбиения): $O(n\log n)$.
- Средний (ожидаемый) случай для разумного выбора опорного (например, случайный или медиана из трёх): $O(n\log n)$.
- Худший случай (например, уже отсортированный массив и выбор опорного как первого/последнего): $O(n^2)$.
- Спец. случай при большом числе одинаковых элементов с 3-way partition: можно получить $O(n)$ для случая всех элементов равны (поскольку рекурсий почти нет).
- Память: версия с дополнительными списками использует $O(n)$ доп. памяти; in-place версия требует $O(\log n)$ стековой памяти в среднем (в худшем — $O(n)$ при плохой балансировке рекурсий).
Рекомендации
- Для общих случаев: использовать либо случайный выбор опорного, либо медиану из трёх + 3-way partition, чтобы избежать худшего случая и эффективно обрабатывать дубликаты.
- Если нужна стабильность — используйте версию с дополнительными списками или другой стабильный алгоритм сортировки (merge sort).