Quick sort: pivot atrofida bo'lish — o'rtacha eng tez, lekin O(n²) tuzog'i bilan

Qisqacha: Quick sort bitta elementni — pivot ni tanlaydi va massivni ikki qismga ajratadi: chapda pivotdan kichiklar, o'ngda kattalar. Pivot shu zahoti o'z joyiga tushadi, ikki qism esa xuddi shunday saralanadi. O'rtacha O(n log n) va qo'shimcha massivsiz (joyida). Lekin pivot doim eng chetdagi qiymat bo'lsa (masalan, saralangan ro'yxatda oxirgi element), vaqt O(n²) ga tushadi. Himoya — tasodifiy pivot va takrorlarni alohida guruhlash.

Bu darsda

• partition (bo'lish) funksiyasini Lomuto va Hoare usulida yoza olasiz.
• Quick sort'ni yozib, har chaqiruv bitta pivotni o'z joyiga qo'yishini kuzatasiz.
• O'rtacha O(n log n) va eng yomon O(n²) qayerdan kelishini o'lchov bilan ko'rasiz.
• Pivotni to'g'ri tanlash, takroriy qiymatlar va stek to'lishi tuzoqlaridan qochasiz.

Oldin bilishingiz kerak: Merge sort, Bo'lib-yech, Klassik chiziqli algoritmlar: Dutch flag, Massiv joyida amallar.

1. Nega bu kerak?

Merge sort har doim O(n log n) — ajoyib kafolat. Lekin uning narxi bor: n ta element uchun yana n ta joy. «Bahor» kassasidagi eski apparatda xotira kam. Sardor so'radi: "Qo'shimcha massivsiz, shu massivning ichida tez saralasa bo'ladimi?"

Bo'ladi. Jasur aka ombor xodimlariga buyurtma varaqlarini shunday ajratishni o'rgatgan. Bitta varaqni oladi — masalan, 20 ming so'mlik buyurtma. "Bundan arzonlari — chap stolga, qimmatlari — o'ng stolga." Bitta o'tishda varaqlar ikki to'pga bo'linadi va 20 minglik varaq aynan o'rtaga tushadi. Keyin har to'p bilan xuddi shu ish qilinadi.

Bu — quick sort (tez saralash). Tanlangan varaq — pivot (tayanch element). Bizning o'lchovimizda quick sort 800 000 sonni merge sort'dan taxminan ikki baravar tez saraladi. Lekin uning bitta xavfli tuzog'i bor — dars oxirigacha uni ham ko'ramiz.

2. Bo'lish (partition) — Lomuto usuli

2.1 G'oya

Pivot — oxirgi element. Massivni chapdan o'ngga bir marta yuramiz. i — "kichiklar zonasi"ning chegarasi: undan chapdagilarning hammasi pivotdan kichik. j — hozir ko'rilayotgan element. arr[j] kichik bo'lsa, uni zona chegarasiga almashtiramiz va zonani bittaga kengaytiramiz. Oxirida pivotni zona chegarasiga qo'yamiz.

Bo'lishdan keyin massiv saralanmadi! Chapda [12, 5, 8], o'ngda [28, 40, 35, 30] — ikkalasi ham aralash. Lekin 20 endi yakuniy joyida: undan chapdagilarning hammasi kichik, o'ngdagilarning hammasi katta. Saralangan massivda ham u aynan 3-indeksda turadi.

2.2 Kod

function partition(arr, lo, hi) {
  const pivot = arr[hi]; // pivot — oxirgi element
  let i = lo; // i dan chapdagilar — pivotdan kichik
  for (let j = lo; j < hi; j++) {
    if (arr[j] < pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }
  [arr[i], arr[hi]] = [arr[hi], arr[i]]; // pivot o'z joyiga
  return i;
}

const orders = [30, 12, 40, 5, 28, 8, 35, 20];
const p = partition(orders, 0, orders.length - 1);
console.log(p, orders.join(" ")); // 3 12 5 8 20 28 40 35 30

• lo va hi — massivning qaysi qismi bilan ishlayotganimiz (ikkala chet ham kiradi). Butun massiv uchun 0 va length - 1.
• [arr[i], arr[j]] = [arr[j], arr[i]] — ikki elementni almashtirish, massiv destructuring bilan.
• Funksiya pivotning yangi indeksini qaytaradi.

Bu usul Lomuto bo'lishi deb ataladi (Nico Lomuto nomidan). Narxi: j bir marta yuradi — O(n), qo'shimcha xotira O(1).

Tekshirib ko'ring: partition([5, 8, 12], 0, 2) nima qaytaradi va massiv qanday o'zgaradi?

3. Quick sort

3.1 Rekursiya

partition bitta pivotni joyiga qo'yadi. Qolgan ikki qismga o'sha amalni qo'llaymiz:

1. Qismda 0 yoki 1 element bo'lsa — tayyor (asos holat).
2. Aks holda partition — pivot p indeksga tushadi.
3. Chap qism [lo, p - 1] va o'ng qism [p + 1, hi] ni xuddi shunday saralaymiz.

Merge sort bilan farqqa qarang. Merge sort'da asosiy ish keyin — birlashtirishda. Quick sort'da asosiy ish oldin — bo'lishda. Rekursiyadan qaytgach, hech narsa qilish kerak emas: qismlar joyida saralangan bo'ladi.

Stek ustuniga qarang: u hozir qaysi chaqiruvlar "ochiq" ekanini ko'rsatadi (Stack). Har partition dan keyin bitta element yashil bo'ladi — u boshqa hech qachon joyidan qo'zg'almaydi.

3.2 Kod

function partition(arr, lo, hi) {
  const pivot = arr[hi];
  let i = lo;
  for (let j = lo; j < hi; j++) {
    if (arr[j] < pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }
  [arr[i], arr[hi]] = [arr[hi], arr[i]];
  return i;
}

function quickSort(arr, lo = 0, hi = arr.length - 1) {
  if (lo >= hi) return arr; // 0 yoki 1 element
  const p = partition(arr, lo, hi);
  quickSort(arr, lo, p - 1); // chap qism
  quickSort(arr, p + 1, hi); // o'ng qism
  return arr;
}

const orders = [35000, 28000, 5000, 30000, 12000];
quickSort(orders);
console.log(orders); // [ 5000, 12000, 28000, 30000, 35000 ]

Bu safar asl massiv o'zgardi — xuddi sort kabi. slice ham, yangi massiv ham yo'q. Bunday algoritm joyida (in-place) ishlaydi (Massiv xotirada va joyida amallar). lo va hi uchun default qiymatli parametrlar ishlatdik: tashqaridan quickSort(orders) deb chaqirish yetadi.

4. Murakkablik: o'rtacha va eng yomon holat

4.1 Yaxshi pivot — n log n

Pivot qismni taxminan teng ikkiga bo'lsa, rasm merge sort'dagidek: log₂ n qatlam, har qatlamda jami n ta solishtirish. O(n log n).

Pivot "ideal" bo'lishi shart emas. Har safar qism 1 : 9 nisbatda bo'linsa ham, qatlamlar soni baribir log n ga proporsional bo'ladi. Tasodifiy ma'lumotda pivot ko'pincha "yetarlicha o'rtada" tushadi. Shuning uchun o'rtacha holat O(n log n).

4.2 Yomon pivot — n²

Endi saralangan ro'yxatni olaylik. Oxirgi element — eng kattasi. partition uni oxirga qo'yadi: chap qismda n − 1 element, o'ng qism bo'sh. Keyingi qadamda yana shunday: n − 2 va bo'sh. Qatlamlar soni n ga teng, ish esa (n − 1) + (n − 2) + … + 1 ≈ n² ÷ 2. Sanaymiz:

let comparisons = 0;

function partition(arr, lo, hi) {
  const pivot = arr[hi];
  let i = lo;
  for (let j = lo; j < hi; j++) {
    comparisons++;
    if (arr[j] < pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }
  [arr[i], arr[hi]] = [arr[hi], arr[i]];
  return i;
}

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

function makeRandom(seed) {
  return () => (seed = (seed * 16807) % 2147483647);
}

const n = 1000;
const random = makeRandom(2026);
const inputs = {
  tasodifiy: Array.from({ length: n }, random),
  saralangan: Array.from({ length: n }, (_, i) => i),
  teskari: Array.from({ length: n }, (_, i) => n - i),
};
for (const [name, arr] of Object.entries(inputs)) {
  comparisons = 0;
  quickSort(arr);
  console.log(`${name}: ${comparisons} ta`);
}

Konsolda:

tasodifiy: 11145 ta
saralangan: 499500 ta
teskari: 499500 ta

Tasodifiy ro'yxatda 11 145 ta — n · log₂ n ≈ 9 966 ga yaqin. Saralangan va teskari ro'yxatda esa aniq 1000 × 999 ÷ 2 = 499 500 — 45 baravar ko'p. Kirish ma'lumoti bir xil hajmda, faqat tartibi boshqa.

Bu hayotda tez-tez uchraydi: «Bahor» buyurtmalari id bo'yicha allaqachon tartibda keladi. Uni "oxirgi pivot" bilan saralash — eng yomon holatning aynan o'zi.

4.3 Xotira va stek

Quick sort qo'shimcha massiv yaratmaydi. Lekin rekursiya stekida ochiq chaqiruvlar turadi. Yaxshi holatda ular log₂ n ta — O(log n). Yomon holatda chuqurlik n ga yetadi va bu yangi muammo:

function partition(arr, lo, hi) {
  const pivot = arr[hi];
  let i = lo;
  for (let j = lo; j < hi; j++) {
    if (arr[j] < pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }
  [arr[i], arr[hi]] = [arr[hi], arr[i]];
  return i;
}

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

const sorted = Array.from({ length: 10000 }, (_, i) => i);
quickSort(sorted);

Konsolda:

RangeError: Maximum call stack size exceeded

Tarjimasi: "Chaqiruvlar stekining eng katta hajmi oshib ketdi". Atigi 10 000 ta saralangan son — va dastur yiqildi. Bizning kompyuterda chegara taxminan 6 000 da chiqdi: 5 000 ta ishladi, 6 000 ta — yo'q. Aniq chegara o'zgarib turadi: u Node sozlamasiga, funksiyaning o'lchamiga va hatto dvigatel kodni allaqachon optimallashtirgan-optimallashtirmaganiga bog'liq. Merge sort'da bunday bo'lmaydi: uning chuqurligi doim log₂ n.

Tekshirib ko'ring: Sardor pivot sifatida birinchi elementni oldi. Qaysi kirishlar endi eng yomon holat bo'ladi?

5. O'lchov: n ikki baravar oshsa

Uchta holatni benchmarking darsidagi usul bilan o'lchadik (urug'li kirish, har n alohida jarayonda, isitish, 7 o'lchov medianasi):

Birinchi jadvalda n ikki baravar — vaqt taxminan ikki baravar: n log n. Ikkinchida — to'rt baravar: n². Saralangan ro'yxatni oxirgi pivot bilan 4 000 tadan ko'p o'lchab bo'lmadi — stek to'lib qoldi (isitishdan keyin, kod optimallashgach, chegara pastroq tushishi mumkin). Endi hammasini bitta rasmda ko'ramiz. Vaqt birinchi o'lchamga nisbatan necha baravar oshgani:

Uchinchi chiziq tepaga "uchib" ketdi: n 8 baravar — vaqt 58 baravar (nazariyada 64). Qolgan ikkitasi deyarli to'g'ri chiziq.

Merge sort bilan solishtiring: 800 000 tasodifiy son — merge sort ≈ 284 ms, toSorted ≈ 282 ms, quick sort ≈ 131 ms. Joyida ishlash (yangi massiv yo'q, GC yo'q) va keshga qulay ketma-ket yurish o'zgarmas ko'paytuvchini kichraytiradi.

6. Pivotni qanday tanlash kerak

6.1 Variantlar

Uchtaning medianasi (median-of-three) — birinchi, o'rtadagi va oxirgi elementdan qiymati o'rtadagisini olish. Saralangan ro'yxatda u aynan o'rtadagini tanlaydi.

Tasodifiy pivot — eng ishonchli. Endi "yomon kirish" tushunchasi deyarli yo'qoladi: yomon holat faqat juda omadsiz tasodifda bo'ladi, ehtimoli esa n o'sgan sari keskin kamayadi.

6.2 Tasodifiy pivot kodi

Tasodifiy indeksni tanlab, uni oxirga almashtiramiz — keyin partition o'zgarmaydi. Darsda natija har safar bir xil chiqishi uchun urug'li generator ishlatamiz. Real kodda Math.random() yetadi (Math obyekti).

let comparisons = 0;

function partition(arr, lo, hi) {
  const pivot = arr[hi];
  let i = lo;
  for (let j = lo; j < hi; j++) {
    comparisons++;
    if (arr[j] < pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }
  [arr[i], arr[hi]] = [arr[hi], arr[i]];
  return i;
}

function makeRandom(seed) {
  return () => (seed = (seed * 16807) % 2147483647);
}
const random = makeRandom(7); // real kodda — Math.random

function quickSort(arr, lo = 0, hi = arr.length - 1) {
  if (lo >= hi) return arr;
  const k = lo + (random() % (hi - lo + 1)); // tasodifiy indeks
  [arr[k], arr[hi]] = [arr[hi], arr[k]]; // pivotni oxiriga
  const p = partition(arr, lo, hi);
  quickSort(arr, lo, p - 1);
  quickSort(arr, p + 1, hi);
  return arr;
}

const sorted = Array.from({ length: 1000 }, (_, i) => i);
quickSort(sorted);
console.log(`saralangan, 1000: ${comparisons} ta`);
comparisons = 0;
const big = Array.from({ length: 100000 }, (_, i) => i);
quickSort(big);
console.log(`saralangan, 100000: ${comparisons} ta`);
console.log(big[0], big[99999]); // 0 99999

Konsolda:

saralangan, 1000: 10280 ta
saralangan, 100000: 2090294 ta
0 99999

499 500 o'rniga 10 280 — xuddi tasodifiy ro'yxatdagidek. 100 000 ta saralangan son ham muammosiz saralandi: stek chuqurligi yana log n atrofida.

random() % (hi - lo + 1) — 0 dan hi - lo gacha son beradi. Unga lo qo'shsak, [lo, hi] ichidagi indeks chiqadi.

6.3 Stek kafolati: kichik qism — rekursiya, katta qism — sikl

Tasodifiy pivot stek to'lishini deyarli imkonsiz qiladi, lekin "deyarli" — kafolat emas. To'liq kafolat uchun oddiy hiyla bor. partition dan keyin ikki qismdan kichigini rekursiya bilan saralaymiz, kattasini esa while sikli bilan shu chaqiruvning o'zida davom ettiramiz:

function partition(arr, lo, hi) {
  const pivot = arr[hi];
  let i = lo;
  for (let j = lo; j < hi; j++) {
    if (arr[j] < pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }
  [arr[i], arr[hi]] = [arr[hi], arr[i]];
  return i;
}

let depth = 0;
let maxDepth = 0;

function quickSortSafe(arr, lo = 0, hi = arr.length - 1) {
  depth++;
  maxDepth = Math.max(maxDepth, depth);
  while (lo < hi) {
    const p = partition(arr, lo, hi);
    if (p - lo < hi - p) {
      quickSortSafe(arr, lo, p - 1); // kichik qism — rekursiya
      lo = p + 1; // katta qism — sikl davom etadi
    } else {
      quickSortSafe(arr, p + 1, hi);
      hi = p - 1;
    }
  }
  depth--;
  return arr;
}

const sorted = Array.from({ length: 20000 }, (_, i) => i);
quickSortSafe(sorted);
console.log(sorted[19999], `eng katta chuqurlik: ${maxDepth}`);

Konsolda:

19999 eng katta chuqurlik: 2

Pivot ataylab yomon (oxirgisi), ro'yxat esa saralangan. Avvalgi kod 6 000 ta sonda yiqilgan edi, bu esa 20 000 tada ham atigi 2 qavat chuqurlikka tushdi. Nega? Rekursiyaga doim kichik qism ketadi, u esa joriy qismning yarmidan oshmaydi. Demak, har qavat chuqurlashganda qism kamida ikki baravar kichrayadi — chuqurlik log₂ n dan oshmaydi.

Diqqat: bu hiyla faqat stekni himoya qiladi. Vaqt o'zgarmadi — saralangan ro'yxatda oxirgi pivot bilan baribir O(n²) (20 000 sonda yarim soniyaga yaqin). Shuning uchun real kutubxonalarda ikkalasi birga ishlatiladi: yaxshi pivot tanlash va kichik qismga rekursiya.

7. Takrorlar va Hoare bo'lishi

7.1 Bir xil qiymatlar tuzog'i

«Bahor»da ko'p buyurtma bir xil summada: osh — 35 000, osh — 35 000, osh — 35 000... Hamma element bir xil bo'lsa-chi? Lomuto arr[j] < pivot ni tekshiradi. Teng elementlar "kichik" emas — hammasi o'ng qismga ketadi. Pivot har safar chetga tushadi va tasodifiy pivot ham yordam bermaydi: hammasi teng, qaysi birini olsangiz ham bir xil.

O'lchovimiz: 500 ta bir xil son — ≈ 0,28 ms, 1 000 — ≈ 1,1 ms (×3,8), 2 000 — ≈ 4,1 ms (×3,9), 4 000 tada esa stek to'lib qoldi. Tasodifiy pivot bo'lsa ham — n² ning belgisi. 1 000 ta bir xil sonda solishtirishlar — 499 500 (n² ÷ 2), 20 000 tada esa yana RangeError: Maximum call stack size exceeded.

7.2 Hoare bo'lishi

Quick sort'ning muallifi Tony Hoare 1961-yilda boshqa bo'lish usulini taklif qilgan. Ikki ko'rsatkich ikki chetdan bir-biriga qarab yuradi (Ikki ko'rsatkich). Chapdagi pivotdan katta yoki teng elementda, o'ngdagi kichik yoki teng elementda to'xtaydi — va ular almashadi:

function partitionHoare(arr, lo, hi) {
  const pivot = arr[Math.floor((lo + hi) / 2)]; // o'rtadagi qiymat
  let i = lo - 1;
  let j = hi + 1;
  while (true) {
    do i++; while (arr[i] < pivot); // chapdan: katta yoki teng
    do j--; while (arr[j] > pivot); // o'ngdan: kichik yoki teng
    if (i >= j) return j; // uchrashdi — chegara j
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
}

function quickSortHoare(arr, lo = 0, hi = arr.length - 1) {
  if (lo >= hi) return arr;
  const p = partitionHoare(arr, lo, hi);
  quickSortHoare(arr, lo, p); // p ham chap qismga kiradi!
  quickSortHoare(arr, p + 1, hi);
  return arr;
}

console.log(quickSortHoare([30, 12, 40, 5, 28, 8, 35, 20]).join(" "));
const same = new Array(100000).fill(35000);
quickSortHoare(same);
console.log("100 000 ta bir xil — tayyor");

Konsolda:

5 8 12 20 28 30 35 40
100 000 ta bir xil — tayyor

do … while — avval tanani bajaradi, keyin shartni tekshiradi (Sikllar). Ikki muhim farq:

• Teng elementlar ikki tomonga bo'linadi. Ikkala ko'rsatkich ham pivotga teng elementda to'xtaydi va ularni almashtiradi. Hammasi bir xil bo'lsa, ko'rsatkichlar o'rtada uchrashadi — qism teng ikkiga bo'linadi.
• Pivot yakuniy joyida bo'lishi shart emas. Hoare faqat chegarani j qaytaradi: [lo, j] dagilar ≤ pivot, [j + 1, hi] dagilar ≥ pivot. Shuning uchun rekursiya p - 1 gacha emas, p gacha boradi.

O'lchovimiz: tasodifiy 800 000 son — ≈ 109 ms (Lomuto, oxirgi pivot — ≈ 131 ms): almashtirishlar kamroq. Saralangan 800 000 son — ≈ 19 ms, n ×2 da vaqt ×1,9–2,3. Hoare'ning o'rtadagi pivoti saralangan ro'yxatda aynan medianani oladi.

7.3 Uch yo'lli bo'lish

Takrorlar ko'p bo'lsa, eng yaxshi yechim — massivni uch qismga bo'lish: kichiklar, pivotga tenglar, kattalar. Tenglar o'rtada yig'iladi va keyingi rekursiyaga umuman kirmaydi. Bu Dutch flag algoritmining aynan o'zi — uch rangli bayroq o'rniga "kichik, teng, katta". Uni 3-mashqda yozasiz.

8. Quick sort barqaror emas

Uzoqdagi elementlar almashtirilgani uchun teng elementlar tartibi buzilishi mumkin:

function partition(arr, lo, hi) {
  const pivot = arr[hi].sum;
  let i = lo;
  for (let j = lo; j < hi; j++) {
    if (arr[j].sum < pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }
  [arr[i], arr[hi]] = [arr[hi], arr[i]];
  return i;
}

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

const orders = [
  { time: "12:05", sum: 28000 },
  { time: "12:10", sum: 5000 },
  { time: "12:15", sum: 5000 },
  { time: "12:20", sum: 35000 },
];
for (const o of quickSort(orders)) console.log(o.sum, o.time);

Konsolda:

5000 12:15
5000 12:10
28000 12:05
35000 12:20

12:10 va 12:15 o'rin almashdi. Bu yerda nima bo'ldi: birinchi partition da 28000 ni 5000 12:15 bilan almashtirdik — 5000 12:15 boshqa beshlikdan "sakrab" o'tib ketdi. Barqarorlik kerak bo'lsa — merge sort yoki tayyor sort/toSorted (V8 da barqaror).

9. Chegaraviy holatlar

10. Ko'p uchraydigan xatolar

10.1 Hoare bo'lishida p - 1 gacha rekursiya

Lomuto'dan ko'chirilgan quickSortHoare(arr, lo, p - 1) — xato. Hoare pivotni p ga qo'ymaydi, arr[p] hali saralanmagan bo'lishi mumkin. Natija jimgina noto'g'ri chiqadi. Tuzatish: Hoare'da [lo, p] va [p + 1, hi].

10.2 Asos holatda lo === hi

if (lo === hi) return arr; deb yozilsa, bo'sh qism (lo > hi) asos holatga tushmaydi. Pivot birinchi o'ringa tushganda quickSort(arr, 0, -1) chaqiriladi, partition esa arr[-1] bilan ishlaydi va yana 0 qaytaradi. Funksiya o'zini cheksiz chaqiradi — atigi 5 ta saralangan sonda ham RangeError: Maximum call stack size exceeded. Tuzatish: lo >= hi.

10.3 Saralangan ma'lumotda qat'iy pivot

Kod sinovda tez ishlaydi (tasodifiy sonlar bilan), ishlab chiqarishda esa yiqiladi — chunki u yerda ma'lumot allaqachon tartibda keladi. Tuzatish: tasodifiy pivot yoki uchtaning medianasi.

10.4 Barqarorlikka tayanish

Quick sort bilan ko'p kalitli saralash ("avval vaqt, keyin summa") ishlamaydi — birinchi saralash tartibi yo'qoladi. Tuzatish: barqaror algoritm yoki taqqoslovchida ikkala kalit.

11. Mashqlar

1-mashq (oson): Qo'lda bo'ling

partition([28, 5, 35, 12, 30], 0, 4) ni qog'ozda bajaring (Lomuto, pivot — oxirgisi). Funksiya qaysi indeksni qaytaradi?

2-mashq (o'rta): Uchtaning medianasi

medianOfThree(arr, lo, hi) funksiyasini yozing: arr[lo], arr[mid], arr[hi] ichidan qiymati o'rtadagisining indeksini qaytarsin. Keyin quick sort'da shu indeksdagi elementni oxirga almashtirib, Lomuto bilan ishlating. Saralangan 10 000 ta sonda stek to'lmasligini tekshiring.

function medianOfThree(arr, lo, hi) {
  const mid = Math.floor((lo + hi) / 2);
  const a = arr[lo];
  const b = arr[mid];
  const c = arr[hi];
  if ((a <= b && b <= c) || (c <= b && b <= a)) return mid;
  if ((b <= a && a <= c) || (c <= a && a <= b)) return lo;
  return hi;
}

function partition(arr, lo, hi) {
  const pivot = arr[hi];
  let i = lo;
  for (let j = lo; j < hi; j++) {
    if (arr[j] < pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }
  [arr[i], arr[hi]] = [arr[hi], arr[i]];
  return i;
}

function quickSort(arr, lo = 0, hi = arr.length - 1) {
  if (lo >= hi) return arr;
  const k = medianOfThree(arr, lo, hi);
  [arr[k], arr[hi]] = [arr[hi], arr[k]];
  const p = partition(arr, lo, hi);
  quickSort(arr, lo, p - 1);
  quickSort(arr, p + 1, hi);
  return arr;
}

const sorted = Array.from({ length: 10000 }, (_, i) => i);
console.log(quickSort(sorted)[9999]); // 9999

3-mashq (qiyin): Uch yo'lli quick sort

kurs/mashqlar/14/30-quick/quick.test.mjs faylida quickSort3(arr, random) ni yozing: tasodifiy pivot va uch yo'lli bo'lish (lt, i, gt — Dutch flag dagidek). Testlar (node:test):

1. Bo'sh, bitta va ikkita element.
2. Manfiy va takroriy sonlar.
3. Urug'li tasodifiy 2 000 son — natija toSorted bilan bir xil.
4. Saralangan 100 000 son — stek to'lmaydi.
5. 100 000 ta bir xil narx 100 ms dan tez saralanadi.

// kurs/mashqlar/14/30-quick/quick.test.mjs
import { test } from "node:test";
import assert from "node:assert/strict";

function makeRandom(seed) {
  return () => (seed = (seed * 16807) % 2147483647);
}

// uch yo'lli bo'lish: < pivot | = pivot | > pivot
function quickSort3(arr, random, lo = 0, hi = arr.length - 1) {
  if (lo >= hi) return arr;
  const pivot = arr[lo + (random() % (hi - lo + 1))];
  let lt = lo; // [lo, lt) — kichiklar
  let i = lo; // [lt, i) — tenglar
  let gt = hi; // (gt, hi] — kattalar
  while (i <= gt) {
    if (arr[i] < pivot) {
      [arr[lt], arr[i]] = [arr[i], arr[lt]];
      lt++;
      i++;
    } else if (arr[i] > pivot) {
      [arr[i], arr[gt]] = [arr[gt], arr[i]];
      gt--; // i joyida qoladi: kelgan element hali ko'rilmagan
    } else {
      i++;
    }
  }
  quickSort3(arr, random, lo, lt - 1);
  quickSort3(arr, random, gt + 1, hi);
  return arr;
}

const sortNums = (arr) => quickSort3(arr, makeRandom(42));

test("chegaraviy: bo'sh, bitta, ikkita", () => {
  assert.deepEqual(sortNums([]), []);
  assert.deepEqual(sortNums([7]), [7]);
  assert.deepEqual(sortNums([8, 5]), [5, 8]);
});

test("manfiy va takroriy sonlar", () => {
  assert.deepEqual(sortNums([3, -1, 3, 0, -1]), [-1, -1, 0, 3, 3]);
});

test("toSorted bilan bir xil (urug'li tasodifiy)", () => {
  const random = makeRandom(2026);
  const arr = Array.from({ length: 2000 }, () => random() % 100);
  const expected = arr.toSorted((a, b) => a - b);
  assert.deepEqual(sortNums(arr), expected);
});

test("saralangan 100 000 — stek to'lmaydi", () => {
  const arr = Array.from({ length: 100000 }, (_, i) => i);
  assert.equal(sortNums(arr)[99999], 99999);
});

test("100 000 ta bir xil narx — tez", () => {
  const arr = new Array(100000).fill(35000);
  const start = performance.now();
  sortNums(arr);
  assert.ok(performance.now() - start < 100);
});

✔ chegaraviy: bo'sh, bitta, ikkita (1.3088ms)
✔ manfiy va takroriy sonlar (0.1419ms)
✔ toSorted bilan bir xil (urug'li tasodifiy) (4.2919ms)
✔ saralangan 100 000 — stek to'lmaydi (34.7799ms)
✔ 100 000 ta bir xil narx — tez (2.0353ms)
ℹ tests 5
ℹ suites 0
ℹ pass 5
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 125.0606

4-mashq: Amaliy tajriba — jadvalga uch qator

kurs/mashqlar/14/MURAKKABLIK.md ga quick sort'ning uch variantini yozing: oxirgi pivot, tasodifiy pivot, uch yo'lli. Har biriga o'rtacha va eng yomon vaqt, stek chuqurligi va "Barqaror?" ni to'ldiring.

| Masala | Yechim | Vaqt | Xotira | Barqaror? |
|---|---|---|---|---|
| Massivni saralash | quick sort, oxirgi pivot | O(n log n) o'rt., O(n²) yomon (saralangan!) | O(log n)…O(n) stek | yo'q |
| Massivni saralash | quick sort, tasodifiy pivot | O(n log n) o'rt., O(n²) juda kam ehtimol | O(log n) o'rt. | yo'q |
| Takrorlari ko'p massiv | uch yo'lli quick sort | O(n log k), k — turli qiymatlar soni | O(log n) o'rt. | yo'q |

git add 14/MURAKKABLIK.md 14/30-quick
git commit -m "14/30: quick sort, tasodifiy pivot, uch yo'lli bo'lish"

12. Real ishda

• Standart kutubxonalar. C++ std::sort va Rust sort_unstable — quick sort asosidagi gibrid algoritmlar: kichik qismlarda insertion sort, chuqurlik oshib ketsa — kafolatli boshqa algoritm (introsort, pdqsort). Java'da sonli massivlar uchun ikki pivotli quick sort ishlatiladi.
• V8 tarixi. 2018-yilgacha V8 ning sort i quick sort edi (10 tadan kichik qismlarda insertion sort) — va barqaror emas edi. Nega o'zgargani — JS sort ichidan darsida.
• Hujum. Pivoti qat'iy tanlangan saralashga maxsus tuzilgan ma'lumot yuborib, serverni O(n²) ga tushirish mumkin. Tasodifiy pivot shundan himoya qiladi.
• Intervyu. "Quick sort'ning eng yomon holati qachon?", "Nega amalda merge sort'dan tez?", "Barqarormi?" — eng ko'p beriladigan savollar. partition g'oyasi esa Quickselect da qayta ishlatiladi.

Xulosa

• partition pivotni yakuniy joyiga qo'yadi: chapda kichiklar, o'ngda kattalar — O(n), qo'shimcha xotirasiz.
• Quick sort = partition + ikki qismni rekursiv saralash. Joyida ishlaydi, barqaror emas.
• O'rtacha O(n log n) va amalda juda tez; chetki pivotda O(n²) va O(n) chuqurlikdagi stek — 10 000 ta saralangan sonda RangeError.
• Himoya: tasodifiy pivot (yoki uchtaning medianasi); takrorlar ko'p bo'lsa — Hoare yoki uch yo'lli bo'lish.

Keyingi dars: Chiziqli saralashlar va JS sort ichidan — taqqoslamasdan O(n) da saralash (counting, radix, bucket) va V8'ning sort i aslida qanday ishlashi.

Manbalar

• C. A. R. Hoare, "Quicksort", The Computer Journal 5(1), 1962.
• Thomas H. Cormen va boshq., "Introduction to Algorithms", 4-nashr, MIT Press, 2022 — 7-bob (Lomuto bo'lishi, tasodifiy quick sort).
• Robert Sedgewick, Kevin Wayne, "Algorithms", 4-nashr — 2-bob (uch yo'lli bo'lish).