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

Проблем

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

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

static void QuickSort(int[] prices, int lo, int hi)
{
    RuntimeHelpers.EnsureSufficientExecutionStack();
    if (lo >= hi)
    {
        return;
    }
    int p = Partition(prices, lo, hi);
    QuickSort(prices, lo, p - 1);
    QuickSort(prices, p + 1, hi);
}

int[] prices = Catalog(100000);
Array.Sort(prices);
var worker = new Thread(() =>
{
    try
    {
        QuickSort(prices, 0, prices.Length - 1);
        Console.WriteLine("Подредени");
    }
    catch (InsufficientExecutionStackException e)
    {
        Console.WriteLine("Стекът свърши: " + e.GetType().Name);
    }
}, 1024 * 1024);
worker.Start();
worker.Join();

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

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

Идеята

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

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

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

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

Виж го

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

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

static int Partition(int[] prices, int lo, int hi)
{
    int pivot = prices[lo];
    int i = lo;
    for (int j = lo + 1; j <= hi; j++)
    {
        if (prices[j] < pivot)
        {
            i++;
            (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 е на окончателното си място, а двете части се подреждат отделно, в същия масив, без допълнителна памет.

int[] prices = { 45, 80, 20, 65, 10, 90, 30, 55 };
int p = Partition(prices, 0, prices.Length - 1);
Console.WriteLine("[" + string.Join(", ", 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]); е размяна с кортежи (tuples): дясната страна се смята цялата, преди да се запише лявата.

Виж го

Целият quick sort

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

static void QuickSort(int[] prices, int lo, int hi)
{
    if (lo >= hi)
    {
        return;
    }
    int p = Partition(prices, lo, hi);
    QuickSort(prices, lo, p - 1);
    QuickSort(prices, p + 1, hi);
}

int[] prices = { 45, 80, 20, 65, 10, 90, 30, 55 };
Console.WriteLine("Преди: [" + string.Join(", ", prices) + "]");
QuickSort(prices, 0, prices.Length - 1);
Console.WriteLine("След: [" + string.Join(", ", 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²), колкото простите сортирания.

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

static void QuickSort(int[] prices, int lo, int hi)
{
    if (lo >= hi)
    {
        return;
    }
    int p = Partition(prices, lo, hi);
    QuickSort(prices, lo, p - 1);
    QuickSort(prices, p + 1, hi);
}

static void QuickSort(int[] prices, int lo, int hi)
{
    if (lo >= hi)
    {
        return;
    }
    int k = Random.Shared.Next(lo, hi + 1);
    (prices[lo], prices[k]) = (prices[k], prices[lo]);
    int p = Partition(prices, lo, hi);
    QuickSort(prices, lo, p - 1);
    QuickSort(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. Какво отпечатва програмата?

static int Partition(int[] prices, int lo, int hi)
{
    int pivot = prices[lo];
    int i = lo;
    for (int j = lo + 1; j <= hi; j++)
    {
        if (prices[j] < pivot)
        {
            i++;
            (prices[i], prices[j]) = (prices[j], prices[i]);
        }
    }
    (prices[lo], prices[i]) = (prices[i], prices[lo]);
    return i;
}

int[] prices = { 50, 70, 20, 90, 40 };
int p = Partition(prices, 0, prices.Length - 1);
Console.WriteLine("[" + string.Join(", ", prices) + "], p = " + p);

Отговор

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

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

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

Виж го

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

Пусни 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 не пускаме, за да не замръзне страницата.

static void QuickSort(int[] prices, int lo, int hi)
{
    if (lo >= hi)
    {
        return;
    }
    int k = Random.Shared.Next(lo, hi + 1);
    (prices[lo], prices[k]) = (prices[k], prices[lo]);
    int p = Partition(prices, lo, hi);
    QuickSort(prices, lo, p - 1);
    QuickSort(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. Тази версия е крайната от урока (с рекурсия в по-малката част, виж по-долу) и печата и колко дълбоко е стигнал стекът:

static long comparisons = 0;
static long seed = 0;
static int deepest = 0;

static int[] Catalog(int n)
{
    int[] prices = new int[n];
    long x = 2026;
    for (int k = 0; k < n; k++)
    {
        x = x * 48271 % 2147483647;
        prices[k] = 1 + (int)(x % 10000);
    }
    return prices;
}

static void QuickSort(int[] prices, int lo, int hi, bool random, int depth)
{
    deepest = Math.Max(deepest, depth);
    while (lo < hi)
    {
        if (random)
        {
            seed = seed * 48271 % 2147483647;
            int k = lo + (int)(seed % (hi - lo + 1));
            (prices[lo], prices[k]) = (prices[k], prices[lo]);
        }
        int p = Partition(prices, lo, hi);
        if (p - lo < hi - p)
        {
            QuickSort(prices, lo, p - 1, random, depth + 1);
            lo = p + 1;
        }
        else
        {
            QuickSort(prices, p + 1, hi, random, depth + 1);
            hi = p - 1;
        }
    }
}

static int Partition(int[] prices, int lo, int hi)
{
    int pivot = prices[lo];
    int i = lo;
    for (int j = lo + 1; j <= hi; j++)
    {
        comparisons++;
        if (prices[j] < pivot)
        {
            i++;
            (prices[i], prices[j]) = (prices[j], prices[i]);
        }
    }
    (prices[lo], prices[i]) = (prices[i], prices[lo]);
    return i;
}

var runs = new (string Label, int N, bool Sorted, bool Random)[]
{
    ("първият пивот, разбъркани", 1000, false, false),
    ("първият пивот, разбъркани", 100000, false, false),
    ("първият пивот, подредени", 1000, true, false),
    ("случаен пивот, подредени", 1000, true, true),
    ("случаен пивот, подредени", 100000, true, true),
};
foreach (var run in runs)
{
    int[] prices = Catalog(run.N);
    if (run.Sorted)
    {
        Array.Sort(prices);
    }
    comparisons = 0;
    seed = 12345;
    deepest = 0;
    QuickSort(prices, 0, prices.Length - 1, run.Random, 1);
    Console.WriteLine($"{run.Label}, n = {run.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 често е по-бърз на практика: разменя цени в същия масив, без копия, и чете паметта поред.

Идеята

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

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

В C# истинското препълване на стека (StackOverflowException) не може да се хване: процесът просто спира. Затова тук сортирането върви в нишка със стек от 1 MB, а RuntimeHelpers.EnsureSufficientExecutionStack() в началото на QuickSort хвърля InsufficientExecutionStackException, когато стекът е почти пълен. Това изключение вече се хваща.

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

Идеята

Три поправки

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

static void QuickSort(int[] prices, int lo, int hi)
{
    if (lo >= hi)
    {
        return;
    }
    int k = Random.Shared.Next(lo, hi + 1);
    (prices[lo], prices[k]) = (prices[k], prices[lo]);
    int p = Partition(prices, lo, hi);
    QuickSort(prices, lo, p - 1);
    QuickSort(prices, p + 1, hi);
}

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

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

static void QuickSort(int[] prices, int lo, int hi)
{
    while (lo < hi)
    {
        int k = Random.Shared.Next(lo, hi + 1);
        (prices[lo], prices[k]) = (prices[k], prices[lo]);
        int p = Partition(prices, lo, hi);
        if (p - lo < hi - p)
        {
            QuickSort(prices, lo, p - 1);
            lo = p + 1;
        }
        else
        {
            QuickSort(prices, p + 1, hi);
            hi = p - 1;
        }
    }
}

int[] prices = Catalog(100000);
Array.Sort(prices);
QuickSort(prices, 0, prices.Length - 1);
Console.WriteLine("Подредени: " + prices.SequenceEqual(prices.Order()));

Подредени: True

Пробвай

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

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

int[] prices = { 45, 80, 20, 65, 10, 90, 30, 55 };
Console.WriteLine("Преди: [" + string.Join(", ", prices) + "]");
QuickSort(prices, 0, prices.Length - 1);
Console.WriteLine("След: [" + string.Join(", ", prices) + "]");

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

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

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

Пробвай

Попълни

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

static void QuickSort(int[] prices, int lo, int hi)
{
    while (lo < hi)
    {
        int k = Random.Shared.Next(lo, hi + 1);
        (prices[lo], prices[k]) = (prices[k], prices[lo]);
        int p = Partition(prices, lo, hi);
        if (p - lo < hi - p)
        {
            QuickSort(prices, lo, p - 1);
            lo = ;
        }
        else
        {
            QuickSort(prices, p + 1, hi);
            hi = p - 1;
        }
    }
}

Упражнение

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

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

Медиана от три. Напиши Median(prices, lo, hi), който гледа три цени: на lo, на средата lo + (hi - lo) / 2 и на hi, и връща мястото на средната по стойност. В QuickSort (обикновената рекурсия от урока) размени тази цена с 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) прави три зони: по-малки, равни и по-големи. Равните са готови и не влизат в рекурсията.

Вграденото сортиране. В C# Array.Sort и List<T>.Sort са introsort: quick sort с медиана от три, който минава на heap sort, когато рекурсията стане твърде дълбока (около 2 · log₂ n нива), и на insertion sort за малки части. Така най-лошият случай е O(n log n). Същото прави std::sort в C++.

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 и лошият пивот

Бисквитки