Quick sort и лошият пивот в Python

Проблем

Подреденият ценоразпис замръзва

Магазинът подрежда своите 100 000 продукта с quick sort: при разбъркан каталог това са 2 136 015 сравнения и страницата се отваря веднага. После доставчикът започва да праща ценоразписа си вече подреден по цена. Същият бутон „Подреди по цена“ мисли дълго и спира с грешка:

prices = sorted(catalog(2000))
try:
    quick_sort(prices, 0, len(prices) - 1)
    print("Подредени")
except RecursionError as e:
    print("Стекът свърши: " + type(e).__name__)

Стекът свърши: RecursionError

(В Python границата на рекурсията е 1000 нива, затова тук стигат 2000 цени.)

Входът не е по-голям, само е подреден. Подреденият вход трябва да е най-лесният, а тук е най-трудният. За да видиш защо, първо виж как работи quick sort.

Идеята

Пивот и разделяне

Merge sort дели списъка на две половини, без да гледа цените, и цялата работа е в сливането. Quick sort (бързо сортиране) прави обратното: работата е в деленето, а сливане няма. Пак е разделяй и владей, както в merge sort.

Избери една цена за пивот (pivot, опорна точка). Тук е първата цена на частта.
Раздели (partition): цените, по-малки от пивота, отиват вляво, останалите вдясно, а пивотът застава между тях. Това е и окончателното му място.
Подреди лявата и дясната част със същия метод. Част с една цена или празна вече е подредена: това е дъното на рекурсията.

Разделянето разменя цени в същия списък, без копия. Затова quick sort не иска O(n) допълнителна памет като merge sort.

Виж го

Разделянето стъпка по стъпка

Тук разделянето е на Lomuto: j минава по цените една по една, а i бележи края на лявата зона, където са цените под пивота. Всяка по-малка цена влиза в зоната с една размяна. Накрая пивотът се разменя с prices[i] и застава на мястото си:

def partition(prices, lo, hi):
    pivot = prices[lo]
    i = lo
    for j in range(lo + 1, hi + 1):
        if prices[j] < pivot:
            i += 1
            prices[i], prices[j] = prices[j], prices[i]
    prices[lo], prices[i] = prices[i], prices[lo]
    return i

Стъпка по стъпка, с думи

Пивотът е първата цена, 45. i = 0 бележи края на лявата зона, цените под 45. Тя още е празна.
j = 1: 80 < 45? Не. 80 остава отдясно, i не мърда.
j = 2: 20 < 45? Да. i става 1, а 20 се разменя с 80: лявата зона расте.
j = 3: 65 < 45? Не. 65 остава отдясно, i не мърда.
j = 4: 10 < 45? Да. i става 2, а 10 се разменя с 80: лявата зона расте.
j = 5: 90 < 45? Не. 90 остава отдясно, i не мърда.
j = 6: 30 < 45? Да. i става 3, а 30 се разменя с 65: лявата зона расте.
j = 7: 55 < 45? Не. 55 остава отдясно, i не мърда.
j стигна края: 7 сравнения за 8 цени, n − 1. Пивотът се разменя с prices[i] = 30 и застава на място 3.
Отляво 30, 20, 10, всички под 45; отдясно 80, 90, 65, 55. 45 е на окончателното си място, а двете части се подреждат отделно, в същия масив, без допълнителна памет.

prices = [45, 80, 20, 65, 10, 90, 30, 55]
p = partition(prices, 0, len(prices) - 1)
print(f"{prices}, p = {p}")

[30, 20, 10, 45, 80, 90, 65, 55], p = 3

partition връща мястото на пивота, p = 3. Сравненията са n − 1: всяка цена освен пивота се сравнява с него точно веднъж.

prices[i], prices[j] = prices[j], prices[i] разменя двете места: дясната страна се смята цялата, преди да се запише лявата.

Виж го

Целият quick sort

quick_sort разделя частта от lo до hi и вика себе си за двете страни на пивота. Самият пивот вече е на мястото си и не влиза в никоя от тях:

def quick_sort(prices, lo, hi):
    if lo >= hi:
        return
    p = partition(prices, lo, hi)
    quick_sort(prices, lo, p - 1)
    quick_sort(prices, p + 1, hi)

prices = [45, 80, 20, 65, 10, 90, 30, 55]
print(f"Преди: {prices}")
quick_sort(prices, 0, len(prices) - 1)
print(f"След: {prices}")

Преди: [45, 80, 20, 65, 10, 90, 30, 55]
След: [10, 20, 30, 45, 55, 65, 80, 90]

Идеята

Средно n · log n, понякога n²

Колко струва quick sort, зависи от пивота.

Добър пивот е някъде около средата. Двете части са приблизително наполовина, и както при merge sort нивата са около log₂ n. На всяко ниво разделянията заедно минават всички n цени веднъж: общо около n · log₂ n. При случайно разбъркани цени първата цена е случайна, затова средният случай е такъв.
Лош пивот е най-малката (или най-голямата) цена в частта. Лявата част е празна, а дясната губи само пивота. Нивата стават n, а сравненията (n − 1) + (n − 2) + … + 1 = n(n − 1)/2. Това е O(n²), колкото простите сортирания.

При подреден вход първата цена на всяка част е най-малката. Така най-лесният вход става най-лошият случай:

def quick_sort(prices, lo, hi):
    if lo >= hi:
        return
    p = partition(prices, lo, hi)
    quick_sort(prices, lo, p - 1)
    quick_sort(prices, p + 1, hi)

def quick_sort(prices, lo, hi):
    if lo >= hi:
        return
    k = random.randint(lo, hi)
    prices[lo], prices[k] = prices[k], prices[lo]
    p = partition(prices, lo, hi)
    quick_sort(prices, lo, p - 1)
    quick_sort(prices, p + 1, hi)

Стъпка по стъпка, с думи

Ценоразписът вече е подреден, от 7 до 80. Пивотът е първата цена на всяка част.
Пивотът 7 е най-малката цена: 7 сравнения, и нищо не отива вляво. Лявата част е празна, дясната е 7 цени.
Същото на всяко ниво: пивотът пак е най-малкият, и частта губи само една цена. Всяко ниво е още едно вложено извикване.
8 нива и 7 + 6 + 5 + 4 + 3 + 2 + 1 = 28 сравнения, n(n − 1)/2. При 100 000 цени: 4 999 950 000 сравнения и 100 000 вложени извиквания, повече, отколкото събира стекът.
Поправката: преди разделянето една случайна цена от частта отива отпред. Останалият код е същият.
Един възможен ход върху същия подреден списък. Случайният пивот обикновено е някъде в средата, затова и двете части получават цени.
5 нива вместо 8 и 17 сравнения вместо 28. Друг ход би бил малко по-различен, но редът на входа вече няма значение: средно около n · log₂ n.

Пробвай

Предвиди изхода

Пет цени, пивотът е първата, 50. Какво отпечатва програмата?

def partition(prices, lo, hi):
    pivot = prices[lo]
    i = lo
    for j in range(lo + 1, hi + 1):
        if prices[j] < pivot:
            i += 1
            prices[i], prices[j] = prices[j], prices[i]
    prices[lo], prices[i] = prices[i], prices[lo]
    return i


prices = [50, 70, 20, 90, 40]
p = partition(prices, 0, len(prices) - 1)
print(f"{prices}, p = {p}")

Отговор

[40, 20, 50, 90, 70], p = 0

[40, 20, 50, 90, 70], p = 2

[20, 40, 50, 70, 90], p = 2

Виж го

Измери го: първият пивот и случайният пивот

Пусни quick sort върху разбъркан и върху подреден каталог. Броят е на сравненията с пивота. Първият пивот при подредени 100 000 цени не се пуска наистина: Bench го оценява по кривата.

Quick sort, първият пивот, разбъркани цени O(n log n)
Quick sort, първият пивот, подредени цени O(n²)
Quick sort, случаен пивот, подредени цени O(n log n)

Алгоритъм	n = 10	n = 1000	n = 10 000	n = 100 000
Quick sort, първият пивот, разбъркани цени	35	10 591	151 493	2 136 015
Quick sort, първият пивот, подредени цени	45	499 500	49 995 000	≈ 4 999 500 000
Quick sort, случаен пивот, подредени цени	21	10 576	153 725	2 316 280

Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.

def quick_sort(prices, lo, hi):
    if lo >= hi:
        return
    k = random.randint(lo, hi)
    prices[lo], prices[k] = prices[k], prices[lo]
    p = partition(prices, lo, hi)
    quick_sort(prices, lo, p - 1)
    quick_sort(prices, p + 1, hi)

При разбъркан каталог от 1000 цени първият пивот прави 10 591 сравнения. При същия каталог, подреден, прави 499 500, точно 1000 · 999 / 2. Случайният пивот върху подредения каталог: 10 576, почти колкото при разбъркания. При 100 000 цени случайният пивот прави 2 316 280 сравнения, а първият би направил n(n − 1)/2 = 4 999 950 000 (Bench го оценява от кривата на около 5 милиарда).

По-точно, за любопитните

Същите числа на твоя език. Каталогът и случайните места идват от малък генератор със семе, затова са еднакви при всяко пускане, на всеки език и в Bench. Тази версия е крайната от урока (с рекурсия в по-малката част, виж по-долу) и печата и колко дълбоко е стигнал стекът:

comparisons = 0
seed = 0
deepest = 0


def catalog(n):
    prices = []
    x = 2026
    for _ in range(n):
        x = x * 48271 % 2147483647
        prices.append(1 + x % 10000)
    return prices


def quick_sort(prices, lo, hi, random_pivot, depth):
    global seed, deepest
    deepest = max(deepest, depth)
    while lo < hi:
        if random_pivot:
            seed = seed * 48271 % 2147483647
            k = lo + seed % (hi - lo + 1)
            prices[lo], prices[k] = prices[k], prices[lo]
        p = partition(prices, lo, hi)
        if p - lo < hi - p:
            quick_sort(prices, lo, p - 1, random_pivot, depth + 1)
            lo = p + 1
        else:
            quick_sort(prices, p + 1, hi, random_pivot, depth + 1)
            hi = p - 1


def partition(prices, lo, hi):
    global comparisons
    pivot = prices[lo]
    i = lo
    for j in range(lo + 1, hi + 1):
        comparisons += 1
        if prices[j] < pivot:
            i += 1
            prices[i], prices[j] = prices[j], prices[i]
    prices[lo], prices[i] = prices[i], prices[lo]
    return i


runs = [
    ("първият пивот, разбъркани", 1000, False, False),
    ("първият пивот, разбъркани", 100000, False, False),
    ("първият пивот, подредени", 1000, True, False),
    ("случаен пивот, подредени", 1000, True, True),
    ("случаен пивот, подредени", 100000, True, True),
]
for label, n, is_sorted, random_pivot in runs:
    prices = sorted(catalog(n)) if is_sorted else catalog(n)
    comparisons = 0
    seed = 12345
    deepest = 0
    quick_sort(prices, 0, len(prices) - 1, random_pivot, 1)
    print(f"{label}, n = {n}: {comparisons} сравнения, дълбочина {deepest}")

първият пивот, разбъркани, n = 1000: 10591 сравнения, дълбочина 7
първият пивот, разбъркани, n = 100000: 2136015 сравнения, дълбочина 11
първият пивот, подредени, n = 1000: 499500 сравнения, дълбочина 2
случаен пивот, подредени, n = 1000: 10576 сравнения, дълбочина 7
случаен пивот, подредени, n = 100000: 2316280 сравнения, дълбочина 11

Merge sort при същите 100 000 цени прави 1 536 292 сравнения, по-малко от quick sort. Въпреки това quick sort често е по-бърз на практика: разменя цени в същия масив, без копия, и чете паметта поред.

Идеята

Защо стекът свършва

Всяко извикване на quick_sort стои в стека от извиквания, докато не се върне. При лош пивот дясната част е само с една цена по-малка, затова извикванията се влагат едно в друго: n нива за n цени. Стекът е ограничен, често около 1 MB, и при 100 000 вложени извиквания свършва.

Python не чака стекът да свърши: при около 1000 вложени извиквания хвърля RecursionError. Границата може да се вдигне с sys.setrecursionlimit, но това само мести проблема: при достатъчно дълбока рекурсия процесът пада.

Отделно от стека е и времето: n(n − 1)/2 сравнения. При 100 000 цени това са около 5 милиарда, затова бутонът „мисли“, преди да падне.

Идеята

Три поправки

Случаен пивот. Преди разделянето една случайна цена от частта отива отпред и става пивот. Тогава никой вход не е лош нарочно: и подреденият, и обърнатият, и разбърканият дават средно n · log₂ n. Най-лошият случай още съществува, но вероятността е нищожна: на всяко ниво случайната цена трябва да е точно най-малката или най-голямата в частта.

def quick_sort(prices, lo, hi):
    if lo >= hi:
        return
    k = random.randint(lo, hi)
    prices[lo], prices[k] = prices[k], prices[lo]
    p = partition(prices, lo, hi)
    quick_sort(prices, lo, p - 1)
    quick_sort(prices, p + 1, hi)

Медиана от три. Вместо случайна цена взимаш средната по стойност от първата, средната по място и последната. При подреден вход това е точно средата. Тази поправка е задачата накрая на урока.

Рекурсия в по-малката част. Извикването е само за по-малката от двете части, а по-голямата остава за цикъла: lo или hi се местят и цикълът я разделя наново. По-малката част е най-много половината, затова стекът е най-много log₂ n нива при всеки пивот: за 100 000 цени до 17 (програмата с броенето стига 11). Сравненията не намаляват, затова тази поправка върви заедно със случайния пивот:

def quick_sort(prices, lo, hi):
    while lo < hi:
        k = random.randint(lo, hi)
        prices[lo], prices[k] = prices[k], prices[lo]
        p = partition(prices, lo, hi)
        if p - lo < hi - p:
            quick_sort(prices, lo, p - 1)
            lo = p + 1
        else:
            quick_sort(prices, p + 1, hi)
            hi = p - 1

prices = sorted(catalog(100000))
quick_sort(prices, 0, len(prices) - 1)
print("Подредени: " + str(prices == sorted(prices)))

Подредени: True

Пробвай

Намери грешката

Осемте цени излизат почти подредени:

prices = [45, 80, 20, 65, 10, 90, 30, 55]
print(f"Преди: {prices}")
quick_sort(prices, 0, len(prices) - 1)
print(f"След: {prices}")

Преди: [45, 80, 20, 65, 10, 90, 30, 55]
След: [20, 30, 10, 45, 65, 80, 90, 55]

Това е partition от програмата. На кой ред е грешката?

Избери реда с грешката.

Пробвай

Попълни

Рекурсията е в по-малката, лявата част. Каква е новата стойност на lo, за да продължи цикълът с дясната?

def quick_sort(prices, lo, hi):
    while lo < hi:
        k = random.randint(lo, hi)
        prices[lo], prices[k] = prices[k], prices[lo]
        p = partition(prices, lo, hi)
        if p - lo < hi - p:
            quick_sort(prices, lo, p - 1)
            lo = 
        else:
            quick_sort(prices, p + 1, hi)
            hi = p - 1

Упражнение

Медиана от три

Реши задачата в редактора си.

Медиана от три. Напиши median(prices, lo, hi), който гледа три цени: на lo, на средата lo + (hi - lo) / 2 и на hi, и връща мястото на средната по стойност. В quick_sort (обикновената рекурсия от урока) размени тази цена с prices[lo] преди разделянето. Преброй сравненията с пивота в partition върху подредения каталог от урока (catalog от програмата с броенето, после подреден) с 1000 и със 100 000 цени.

медиана от три, подредени, n = 1000: 8005 сравнения
медиана от три, подредени, n = 100000: 1773717 сравнения

Сравни с първия пивот: 499 500 сравнения при 1000 подредени цени, а при 100 000 стекът свършва.

Още задачи

Обърнат ценоразпис. Подай каталога подреден от най-скъпото към най-евтиното. Колко сравнения прави първият пивот? А медианата от три?
Еднакви цени. Подай 1000 еднакви цени. Колко сравнения прави разделянето на Lomuto, и защо? (Подсказка: нищо не е строго по-малко от пивота.)
От най-скъпото. Смени един знак в partition, така че списъкът да излиза от най-скъпото към най-евтиното.

По-точно

Quick sort във вграденото сортиране

Quick sort е изобретен от Тони Хоор през 1959 г. и и днес е в основата на вграденото сортиране на много езици, но не в чист вид: всеки добавя предпазители срещу лошия пивот.

По-точно, за любопитните

Lomuto и Hoare. Тук разделянето е на Lomuto: просто е за четене, но разменя повече. Разделянето на Hoare, оригиналното, пуска два показалеца от двата края един към друг и разменя само двойки цени, които са от грешната страна. Прави около три пъти по-малко размени и се справя по-добре с еднакви цени, но пивотът не застава непременно на окончателното си място и кодът е по-лесен за объркване.

Еднакви цени. При много еднакви цени Lomuto пак дава лоши части: всички равни на пивота отиват вдясно. Тройното разделяне (three-way partition) прави три зони: по-малки, равни и по-големи. Равните са готови и не влизат в рекурсията.

Вграденото сортиране. В Python sorted и list.sort не са quick sort, а TimSort, вариант на merge sort: стабилен и бърз при частично подреден вход. Quick sort се среща в NumPy: numpy.sort по подразбиране е introsort.

Quick sort не е стабилен: размяната може да прескочи еднаква цена, и еднаквите продукти сменят реда си. Какво значи това и кога е важно, е в урока „Стабилно сортиране“.

Тест

Провери се

1. Какво прави разделянето (partition) около пивот?Дели масива точно на две равни частиПодрежда двете половини на масиваСлага по-малките цени вляво от пивота, а останалите вдясно; пивотът застава на окончателното си място

2. Пивотът е първата цена. Кой вход е най-лошият случай?Ценоразпис с различни цениВече подреден ценоразписСлучайно разбъркан ценоразпис

3. Защо обикновеният quick sort пада със StackOverflowError (RecursionError, RangeError) при подредени 100 000 цени?Всяко ниво е още едно вложено извикване, а нивата са 100 000Рекурсията никога не стига до дънотоМасивът е твърде голям за паметта

4. Рекурсията е само в по-малката част, а по-голямата се обработва в цикъл. Какво печели това?Quick sort става стабиленСравненията стават n log n и при подреден входСтекът е най-много log₂ n нива, какъвто и да е пивотът

5. Колко допълнителна памет иска quick sort, ако рекурсията е в по-малката част?O(n), колкото merge sortO(n²)O(log n): само стекът

Quick sort и лошият пивот

Бисквитки