Объясните, почему приведённый ниже Python‑функция quicksort иногда возвращает неверно отсортированный список, укажите ошибки и оцените среднюю и худшую временные сложности исправленной версии:
def quicksort(a):
if len(a) <= 1:
return a
pivot = a[0]
left = [x for x in a if x pivot]
return quicksort(left) + [pivot] + quicksort(right)

14 Окт в 14:53
3 +1
0
Ответы
1

Проблема и почему результат неверен

В текущей реализации равные элементу опорного (pivot) значения теряются: используются только проверки (x < pivot) и (x > pivot). Элементы с (x == pivot) не попадают ни в левую, ни в правую часть, поэтому из ответа исчезают дубликаты. Пример: вход ([2,1,2]) даст выход ([1,2]) — один «2» потерян.

Исправление

Нужно явно обрабатывать элементы, равные pivot, например разделив на три группы: меньше, равно, больше. Корректная версия:

def quicksort(a):
if len(a) <= 1:
return a
pivot = a[0]
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 или медиану из нескольких элементов.

Временная сложность исправленной версии

Средняя: (\Theta(n \log n)).Худшая (плохой выбор pivot, например всегда крайний элемент на отсортированных данных): (O(n^2)).
14 Окт в 16:19
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Прямой эфир