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

Проблем

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

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

const prices = catalog(100000).sort((a, b) => a - b);
try {
  quickSort(prices, 0, prices.length - 1);
  console.log("Подредени");
} catch (e) {
  console.log(`Стекът свърши: ${e.name}`);
}

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

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

Идеята

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

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

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

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

Виж го

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

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

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

const prices = [45, 80, 20, 65, 10, 90, 30, 55];
const p = partition(prices, 0, prices.length - 1);
console.log(`[${prices.join(", ")}], 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

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

function quickSort(prices, lo, hi) {
  if (lo >= hi) {
    return;
  }
  const p = partition(prices, lo, hi);
  quickSort(prices, lo, p - 1);
  quickSort(prices, p + 1, hi);
}

const prices = [45, 80, 20, 65, 10, 90, 30, 55];
console.log(`Преди: [${prices.join(", ")}]`);
quickSort(prices, 0, prices.length - 1);
console.log(`След: [${prices.join(", ")}]`);

Преди: [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²), колкото простите сортирания.

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

function quickSort(prices, lo, hi) {
  if (lo >= hi) {
    return;
  }
  const p = partition(prices, lo, hi);
  quickSort(prices, lo, p - 1);
  quickSort(prices, p + 1, hi);
}

function quickSort(prices, lo, hi) {
  if (lo >= hi) {
    return;
  }
  const k = lo + Math.floor(Math.random() * (hi - lo + 1));
  [prices[lo], prices[k]] = [prices[k], prices[lo]];
  const 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. Какво отпечатва програмата?

function partition(prices, lo, hi) {
  const pivot = prices[lo];
  let i = lo;
  for (let 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;
}

const prices = [50, 70, 20, 90, 40];
const p = partition(prices, 0, prices.length - 1);
console.log(`[${prices.join(", ")}], 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 не пускаме, за да не замръзне страницата.

function quickSort(prices, lo, hi) {
  if (lo >= hi) {
    return;
  }
  const k = lo + Math.floor(Math.random() * (hi - lo + 1));
  [prices[lo], prices[k]] = [prices[k], prices[lo]];
  const 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. Тази версия е крайната от урока (с рекурсия в по-малката част, виж по-долу) и печата и колко дълбоко е стигнал стекът:

let comparisons = 0;
let seed = 0;
let deepest = 0;

function catalog(n) {
  const prices = [];
  let x = 2026;
  for (let k = 0; k < n; k++) {
    x = (x * 48271) % 2147483647;
    prices.push(1 + (x % 10000));
  }
  return prices;
}

function quickSort(prices, lo, hi, random, depth) {
  deepest = Math.max(deepest, depth);
  while (lo < hi) {
    if (random) {
      seed = (seed * 48271) % 2147483647;
      const k = lo + (seed % (hi - lo + 1));
      [prices[lo], prices[k]] = [prices[k], prices[lo]];
    }
    const 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;
    }
  }
}

function partition(prices, lo, hi) {
  const pivot = prices[lo];
  let i = lo;
  for (let 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;
}

const runs = [
  ["първият пивот, разбъркани", 1000, false, false],
  ["първият пивот, разбъркани", 100000, false, false],
  ["първият пивот, подредени", 1000, true, false],
  ["случаен пивот, подредени", 1000, true, true],
  ["случаен пивот, подредени", 100000, true, true],
];
for (const [label, n, isSorted, random] of runs) {
  const prices = catalog(n);
  if (isSorted) {
    prices.sort((a, b) => a - b);
  }
  comparisons = 0;
  seed = 12345;
  deepest = 0;
  quickSort(prices, 0, prices.length - 1, random, 1);
  console.log(`${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 често е по-бърз на практика: разменя цени в същия масив, без копия, и чете паметта поред.

Идеята

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

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

JavaScript хвърля RangeError: Maximum call stack size exceeded. В Node стекът е около 1 MB, а колко извиквания събира, зависи от размера на рамката.

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

Идеята

Три поправки

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

function quickSort(prices, lo, hi) {
  if (lo >= hi) {
    return;
  }
  const k = lo + Math.floor(Math.random() * (hi - lo + 1));
  [prices[lo], prices[k]] = [prices[k], prices[lo]];
  const p = partition(prices, lo, hi);
  quickSort(prices, lo, p - 1);
  quickSort(prices, p + 1, hi);
}

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

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

function quickSort(prices, lo, hi) {
  while (lo < hi) {
    const k = lo + Math.floor(Math.random() * (hi - lo + 1));
    [prices[lo], prices[k]] = [prices[k], prices[lo]];
    const 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;
    }
  }
}

const prices = catalog(100000).sort((a, b) => a - b);
quickSort(prices, 0, prices.length - 1);
console.log(`Подредени: ${prices.every((x, i) => i === 0 || prices[i - 1] <= x)}`);

Подредени: true

Пробвай

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

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

const prices = [45, 80, 20, 65, 10, 90, 30, 55];
console.log(`Преди: [${prices.join(", ")}]`);
quickSort(prices, 0, prices.length - 1);
console.log(`След: [${prices.join(", ")}]`);

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

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

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

Пробвай

Попълни

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

function quickSort(prices, lo, hi) {
  while (lo < hi) {
    const k = lo + Math.floor(Math.random() * (hi - lo + 1));
    [prices[lo], prices[k]] = [prices[k], prices[lo]];
    const 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) прави три зони: по-малки, равни и по-големи. Равните са готови и не влизат в рекурсията.

Вграденото сортиране. В JavaScript Array.prototype.sort на V8 (Chrome и Node) е TimSort, вариант на merge sort. До 2018 г. V8 ползваше quick sort. После мина на TimSort, а от ES2019 стандартът изисква стабилно сортиране, което quick sort не е.

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

Бисквитки