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

Проблем

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

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

int[] prices = catalog(100000);
Arrays.sort(prices);
Thread worker = new Thread(null, () -> {
    try {
        quickSort(prices, 0, prices.length - 1);
        System.out.println("Подредени");
    } catch (StackOverflowError e) {
        System.out.println("Стекът свърши: " + e.getClass().getSimpleName());
    }
}, "sort", 1024 * 1024);
worker.start();
worker.join();

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

Входът не е по-голям, само е подреден. Подреденият вход трябва да е най-лесният, а тук е най-трудният. За да видиш защо, първо виж как работи 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++;
            swap(prices, i, j);
        }
    }
    swap(prices, lo, i);
    return i;
}

static void swap(int[] prices, int a, int b) {
    int tmp = prices[a];
    prices[a] = prices[b];
    prices[b] = tmp;
}

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

Пивотът е първата цена, 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);
System.out.println(Arrays.toString(prices) + ", p = " + p);

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

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

Java няма размяна на две места в масив в един ред, затова swap е отделен метод.

Виж го

Целият 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};
System.out.println("Преди: " + Arrays.toString(prices));
quickSort(prices, 0, prices.length - 1);
System.out.println("След: " + Arrays.toString(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.nextInt(lo, hi + 1);
    swap(prices, lo, k);
    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++;
            swap(prices, i, j);
        }
    }
    swap(prices, lo, i);
    return i;
}

static void swap(int[] prices, int a, int b) {
    int tmp = prices[a];
    prices[a] = prices[b];
    prices[b] = tmp;
}

int[] prices = {50, 70, 20, 90, 40};
int p = partition(prices, 0, prices.length - 1);
System.out.println(Arrays.toString(prices) + ", p = " + p);

Отговор

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

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

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

static void quickSort(int[] prices, int lo, int hi) {
    if (lo >= hi) {
        return;
    }
    int k = RANDOM.nextInt(lo, hi + 1);
    swap(prices, lo, k);
    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, boolean random, int depth) {
    deepest = Math.max(deepest, depth);
    while (lo < hi) {
        if (random) {
            seed = seed * 48271 % 2147483647;
            swap(prices, lo, lo + (int) (seed % (hi - lo + 1)));
        }
        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++;
            swap(prices, i, j);
        }
    }
    swap(prices, lo, i);
    return i;
}

static void swap(int[] prices, int a, int b) {
    int tmp = prices[a];
    prices[a] = prices[b];
    prices[b] = tmp;
}

String[] labels = {"първият пивот, разбъркани", "първият пивот, разбъркани", "първият пивот, подредени", "случаен пивот, подредени", "случаен пивот, подредени"};
int[] sizes = {1000, 100000, 1000, 1000, 100000};
boolean[] sorted = {false, false, true, true, true};
boolean[] random = {false, false, false, true, true};
for (int r = 0; r < sizes.length; r++) {
    int[] prices = catalog(sizes[r]);
    if (sorted[r]) {
        Arrays.sort(prices);
    }
    comparisons = 0;
    seed = 12345;
    deepest = 0;
    quickSort(prices, 0, prices.length - 1, random[r], 1);
    System.out.println(labels[r] + ", n = " + sizes[r] + ": " + 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 вложени извиквания свършва.

Java хвърля StackOverflowError. Това е Error, а не Exception: може да се хване, но обикновено значи грешка в програмата. Тук сортирането върви в нишка със стек от 1 MB (четвъртият аргумент на new Thread), за да е еднакво на всяка машина.

Отделно от стека е и времето: 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.nextInt(lo, hi + 1);
    swap(prices, lo, k);
    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.nextInt(lo, hi + 1);
        swap(prices, lo, k);
        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);
Arrays.sort(prices);
quickSort(prices, 0, prices.length - 1);
int[] check = prices.clone();
Arrays.sort(check);
System.out.println("Подредени: " + Arrays.equals(prices, check));

Подредени: true

Пробвай

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

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

int[] prices = {45, 80, 20, 65, 10, 90, 30, 55};
System.out.println("Преди: " + Arrays.toString(prices));
quickSort(prices, 0, prices.length - 1);
System.out.println("След: " + Arrays.toString(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.nextInt(lo, hi + 1);
        swap(prices, lo, k);
        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) прави три зони: по-малки, равни и по-големи. Равните са готови и не влизат в рекурсията.

Вграденото сортиране. В Java Arrays.sort за int[] и другите примитивни масиви е quick sort с два пивота (dual-pivot quicksort): три части наведнъж, а при малки части минава на insertion sort. За масиви от обекти и за List.sort Java ползва TimSort, защото там трябва стабилност.

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

Бисквитки