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

12 Окт в 08:16
2 +2
0
Ответы
1

Код, который вы привели:

def quicksortaaa:
if lenaaa < 2:
return a
pivot = alen(a)//2len(a)//2len(a)//2 left = [x for x in a if x < pivot]
middle = xforxinaifx==pivotx for x in a if x == pivotxforxinaifx==pivot right = [x for x in a if x > pivot]
return quicksortleftleftleft + middle + quicksortrightrightright

— это лаконичная «functional» реализация quicksort на Python. Разберём её по пунктам: сложность, недостатки и практические улучшения.

1) Временная сложность

В среднем: Onlognn log nnlogn. При «хорошем» приблизительноравныхприблизительно равныхприблизительноравных разбиении рекурсия идет по дереву высотой Olognlog nlogn, на каждом уровне мы просматриваем массивыыы — суммарно Onnn на уровень → Onlognn log nnlogn.В худшем случае: On2n^2n2. Это происходит, когда разбиение очень неравномерно однаизчастейпочтиразмераn,другая≈0одна из частей почти размера n, другая ≈0однаизчастейпочтиразмераn,другая0, тогда рекурсия превращается в линейную глубину и суммарные затраты ≈ n + n−1n-1n1 + ... = On2n^2n2.

Замечание: в вашей конкретной реализации одном проходе вы делаете три list-comprehensions — фактическая стоимость одной итерации уровня ≈ 3n трипроходапомассивутри прохода по массивутрипроходапомассиву. Это константный множитель, но важный в практике.

2) Пространственная сложность и стек

Дополнительная память: эта реализация породит новые списки left/middle/right на каждом уровне. В лучшем сбалансированномсбалансированномсбалансированном случае суммарный объём временных списков, находящихся одновременно в памяти, ~Onnn n+n/2+n/4+...=O(n)n + n/2 + n/4 + ... = O(n)n+n/2+n/4+...=O(n). В худшем случае оченьнеравномерныеразбиенияочень неравномерные разбиенияоченьнеравномерныеразбиения сумма размеров списков по уровням может стать On2n^2n2 оченьплохоочень плохооченьплохо.Рекурсивная глубина стека: в худшем случае Onnn, что в CPython приведёт к RecursionError для больших n поумолчаниюrecursionlimit≈1000по умолчанию recursion limit ≈ 1000поумолчаниюrecursionlimit1000. Даже в среднем глубина Olognlog nlogn — лучше, но рекурсия всё равно есть.

3) Возможные «ошибки» / слабые места этой реализации

Многократные проходы по массиву: три прохода left/middle/rightleft/middle/rightleft/middle/right вместо одного для разделения — лишние затраты времени и аллокаций.Большое количество аллокаций/копирований: создаются новые списки на каждом уровне → дорого по памяти и по времени.Рекурсия: потенциальный стековый переполнение для больших n / невезучих входных данных.Выбор опорного элемента pivot=a[len(a)//2]pivot = a[len(a)//2]pivot=a[len(a)//2]: индексный «мид» может давать хорошие разбиения для уже отсортированных массивов, но не гарантирует их для произвольных данных; может существовать вход, дающий плохие разбиения. Нет случайности или устойчивого правила выбора, поэтому возможен On2n^2n2.При специфических типах/значениях NaN,сравнениямеждуразнымитипамиNaN, сравнения между разными типамиNaN,сравнениямеждуразнымитипами поведение сравнения может быть неожиданным — это общий момент для любых реализаций, использующих <, ==, >.

4) Улучшения для практического использования особеннонабольшихданныхособенно на больших данныхособеннонабольшихданных

Использовать in-place partition HoareилиLomutoHoare или LomutoHoareилиLomuto вместо трёх новых списков — уменьшит количество аллокаций и память. Тогда дополнительная память Olognlog nlogn стекстекстек в среднем.Улучшить выбор опорного элемента:
случайный pivot random.choicerandom.choicerandom.choice — даёт в среднем хорошую производительность и с высокой вероятностью избегает худшего слоя;median-of-three первый,средний,последнийпервый, средний, последнийпервый,средний,последний — простая эвристика, часто помогает;median-of-medians — гарантирует Onlognn log nnlogn для сортировки? median−of−mediansиспользуетсядлявыборамедианызаO(n),нодлягарантированнойO(nlogn)quicksortнужнокомбинироватьвыбор;обычноприменяютэторедкоиз‑законстантныхмножителейmedian-of-medians используется для выбора медианы за O(n), но для гарантированной O(n log n) quicksort нужно комбинировать выбор; обычно применяют это редко из‑за константных множителейmedianofmediansиспользуетсядлявыборамедианызаO(n),нодлягарантированнойO(nlogn)quicksortнужнокомбинироватьвыбор;обычноприменяютэторедкоиззаконстантныхмножителей.Рекурсивную реализацию заменить на итеративную с явным стеком или использовать «рекурсию на меньшей части + цикл на большей» tailrecursioneliminationвручнуюtail recursion elimination вручнуюtailrecursioneliminationвручную — это ограничит максимум глубины стека до Olognlog nlogn в среднем.Для малых подмассивов обычноthreshold10–50обычно threshold 10–50обычноthreshold10–50 переключаться на insertion sort — это даёт заметный выигрыш на маленьких блоках.Для больших наборов данных в продакшене лучше использовать встроенный сортировщик Python: list.sort / sorted, который реализует Timsort — устойчивый, оптимизированный для частично отсортированных данных, гарантированная сложность Onlognn log nnlogn в худшем случае и низкие накладные константы.Если данные не помещаются в память: применять внешние алгоритмы сортировки externalmergesortexternal merge sortexternalmergesort, распределённые/параллельные решения Hadoop,SparkHadoop, SparkHadoop,Spark, или сортировку на базе диска/блоков.Если тип данных и требования позволяют, использовать numpy.sort C−реализацияC-реализацияCреализация или специализированные библиотеки.

5) Пример улучшённой реализации in−place,median−of−three,итеративныйстек,переходнаinsertionsortдлямалыхсегментовin-place, median-of-three, итеративный стек, переход на insertion sort для малых сегментовinplace,medianofthree,итеративныйстек,переходнаinsertionsortдлямалыхсегментов

Ниже — пример шаблона краткократкократко, который в практических задачах работает гораздо лучше, чем исходная функциональная версия:

def quicksort_inplaceaaa:
import random
def insertion_sorta,lo,hia, lo, hia,lo,hi:
for i in rangelo+1,hi+1lo+1, hi+1lo+1,hi+1:
key = aiii j = i-1
while j >= lo and ajjj > key:
aj+1j+1j+1 = ajjj j -= 1
aj+1j+1j+1 = key

def median_of_threea,lo,hia, lo, hia,lo,hi:
mid = lo+hilo + hilo+hi // 2
# упрощённо: переставим медиану в alololo if amidmidmid < alololo:
alololo, amidmidmid = amidmidmid, alololo if ahihihi < alololo:
alololo, ahihihi = ahihihi, alololo if ahihihi < amidmidmid:
amidmidmid, ahihihi = ahihihi, amidmidmid alololo, amidmidmid = amidmidmid, alololo # медиана в alololo return alololo
def hoare_partitiona,lo,hia, lo, hia,lo,hi:
pivot = median_of_threea,lo,hia, lo, hia,lo,hi i = lo - 1
j = hi + 1
while True:
i += 1
while aiii < pivot:
i += 1
j -= 1
while ajjj > pivot:
j -= 1
if i >= j:
return j
aiii, ajjj = ajjj, aiii
n = lenaaa if n < 2:
return
stack = (0,n−1)(0, n-1)(0,n1) while stack:
lo, hi = stack.pop if hi - lo <= 16:
insertion_sorta,lo,hia, lo, hia,lo,hi continue
p = hoare_partitiona,lo,hia, lo, hia,lo,hi # обрабатывать меньшую часть рекурсивно — чтобы лимит стека был Olognlog nlogn if p - lo < hi - p+1p+1p+1:
if lo < p:
stack.append(p+1,hi)(p+1, hi)(p+1,hi) stack.append(lo,p)(lo, p)(lo,p) else:
if p+1 < hi:
stack.append(lo,p)(lo, p)(lo,p) stack.append(p+1,hi)(p+1, hi)(p+1,hi)

Эта версия:

работает in-place неткопированиявсегомассиванет копирования всего массиванеткопированиявсегомассива,использует median-of-three лучшеустойчивостьлучше устойчивостьлучшеустойчивость,использует явный стек и переключается на insertion sort для маленьких сегментов.

6) Выводы / рекомендации

Для учебных целей и компактности ваша реализация хороша и читабельна.Для практического применения на больших данных её не рекомендуется использовать: слишком много копирований, возможный перепад памяти/стека, константные множители.В продакшене используйте list.sort/sorted TimsortTimsortTimsort или реализуйте in-place quicksort с хорошей стратегией выбора опорного элемента и управлением стеком; для очень больших/внешних данных — внешние или распределённые алгоритмы сортировки.

Если хотите, могу:

прислать готовую рабочую реализацию in-place quicksort с обработкой граничных случаев и тестами,показать сравнение по времени/памяти между вашей реализацией, in-place quicksort и list.sort на реальных данных.
12 Окт в 08:55
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Прямой эфир