Quickselect va k-chi element: medianani saralamasdan O(n) da topish

Qisqacha: Medianani yoki k-chi eng kichik elementni topish uchun butun massivni saralash shart emas. Quickselect quick sort'ning partition ini ishlatadi: pivot o'z joyiga tushgach, k qaysi tomonda ekanini bilamiz va faqat o'sha tomon bilan davom etamiz. Ish har safar taxminan yarmiga kamayadi: n + n/2 + n/4 + … ≈ 2n — o'rtacha O(n). Saralash esa O(n log n). Eng yomon holat O(n²), shuning uchun pivot tasodifiy tanlanadi.

Bu darsda

• Quickselect'ni partition asosida yozasiz va u nega faqat bir tomonga borishini tushuntira olasiz.
• O'rtacha O(n) qayerdan kelishini hisoblab, o'lchov bilan tasdiqlaysiz.
• Medianani toq va juft uzunlikda to'g'ri hisoblaysiz.
• Top-K masalasida saralash, quickselect va heap yondashuvlarini solishtira olasiz.

Oldin bilishingiz kerak: Quick sort, Binary search asoslari, Xotira murakkabligi va eng yomon holat.

1. Nega bu kerak?

Oy oxirida Jasur aka so'radi: "Bizda odatiy chek qancha?" Sardor o'rtacha arifmetikni hisobladi — 312 ming so'm. Jasur aka ishonmadi: "Mehmonlarning ko'pi 30–40 ming so'mga ovqatlanadi-ku!" Sababi oddiy: oyda bitta to'y bo'lgan — 25 million so'mlik chek. U o'rtachani tepaga tortib ketgan.

Bunday holatda mediana to'g'riroq javob beradi — saralangan ro'yxatning o'rtasidagi qiymat. Bitta katta chek uni deyarli o'zgartirmaydi. Medianani benchmarking darsida o'lchov natijalarini umumlashtirishda ishlatganmiz — aynan shu sababdan.

Sardorning yechimi: sums.toSorted((a, b) => a - b)[Math.floor(n / 2)]. To'g'ri, lekin O(n log n). Bizga bitta element kerak, butun tartib emas. Saralash qolgan n − 1 ta elementni ham joy-joyiga qo'yadi — bu ortiqcha ish. Bugun shu ortiqcha ishni tashlaymiz.

2. G'oya: partition — va faqat bir tomon

2.1 Partition yana bir bor

Avval kodsiz, stol ustida. Sardor 11 ta chekni stolga qator qilib qo'ydi. Bittasini — 40 ming so'mlikni — tanladi. Undan arzonlarini chapga, qimmatlarini o'ngga surdi. Chapda 8 ta chek qoldi. Demak, 40 ming saralangan ro'yxatda 9-o'rinda (8-indeksda) turadi — qolganlarini saralamasdan ham buni aniq bilamiz.

Mediana esa 6-o'rinda (5-indeksda). U 40 dan chapda. O'ngdagi 2 ta chekka endi qaramasa ham bo'ladi — mediana ular orasida emas. Sardor faqat chapdagi 8 ta chek bilan xuddi shu ishni takrorlaydi. Har safar stoldagi cheklar kamayadi.

Bu "tanlab, ikki tomonga surish" — Quick sort darsidagi partition (Lomuto bo'lishi). U pivotni yakuniy joyiga qo'yadi: pivot p indeksga tushsa, saralangan massivda ham u aynan p da turadi. Chapda kichiklar, o'ngda kattalar.

Endi bizga k-indeksdagi element kerak. Mediana uchun k = n ÷ 2 — n ning yarmi, pastga yaxlitlangan (Math.floor(n / 2)): 11 ta chekda 5. partition dan keyin uch holat bor:

1. p === k — omad! Pivotning o'zi javob.
2. k < p — javob chap qismda. O'ng qismga umuman tegmaymiz.
3. k > p — javob o'ng qismda. Chap qismni tashlaymiz.

Quick sort ikkala qismni ham saralar edi. Quickselect faqat bitta qismga boradi. Binar qidiruvga o'xshaydi-ku? Ha — har qadamda bir qism tashlanadi. Farqi: bu yerda qismlar teng bo'lishi kafolatlanmagan va har qadamda tashlash uchun qismni "yurib chiqish" kerak.

2.2 Kuzatamiz

11 ta chek summasi (ming so'mda), mediana qidiramiz. Kuzatishni oson qilish uchun pivot — oxirgi element:

4 ta partition — 11 + 8 + 3 + 2 = 24 ta elementni ko'rdi. Oxirida massiv saralanmagan: 28 dan chapda 12 5 18 8 25, o'ngda 30 35 40 90 48 — tartibsiz. Lekin 28 aniq o'z joyida va u mediana.

2.3 Kod

Haqiqiy kodda pivot tasodifiy — buning sababini quick sort darsida ko'rgan edik. Darsda natija bir xil chiqishi uchun urug'li generator:

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

function quickselect(arr, k, random) {
  let lo = 0;
  let hi = arr.length - 1;
  while (lo < hi) {
    const r = lo + (random() % (hi - lo + 1)); // tasodifiy pivot
    [arr[r], arr[hi]] = [arr[hi], arr[r]];
    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]];
    if (i === k) return arr[i];
    if (k < i) hi = i - 1; // faqat chap qism
    else lo = i + 1; // faqat o'ng qism
  }
  return arr[lo];
}

const random = makeRandom(7);
const sums = [35, 12, 48, 5, 28, 90, 18, 30, 8, 25, 40];
console.log(quickselect([...sums], 5, random)); // 28 — mediana
console.log(quickselect([...sums], 0, random)); // 5 — eng kichigi
console.log(quickselect([...sums], 10, random)); // 90 — eng kattasi

• lo + (random() % (hi - lo + 1)) — lo dan hi gacha (ikkalasi ham kiradi) tasodifiy indeks. % qoldig'i 0 dan hi - lo gacha bo'ladi, unga lo ni qo'shamiz.
• Tanlangan pivot oxirgi o'ringa (hi) ko'chiriladi. Keyin hammasi tanish Lomuto bo'lishi: pivot — oxirgi element.
• partition ni alohida funksiyaga ajratmadik — while ichida yozdik. Mazmuni o'zgarmadi.
• Rekursiya ham yo'q: bitta tomonga borilgani uchun lo/hi ni o'zgartirib, sikl bilan davom etish yetadi. Stek — O(1).
• [...sums] — nusxa. Quickselect massivni joyida qayta joylaydi; asl ro'yxat buzilmasin desak, nusxa olamiz.

Tekshirib ko'ring: quickselect(arr, 0, random) aslida qanday masalani yechadi? Unga quickselect kerakmi?

3. Murakkablik

3.1 O'rtacha: n + n/2 + n/4 + …

Pivot o'rtacha "o'rtaroqqa" tushadi. Birinchi partition n ta elementni ko'radi. Keyingisi — qolgan qismni, taxminan yarmini: n/2. Keyin n/4, n/8… Bu yig'indi 2n dan oshmaydi:

n + n/2 + n/4 + n/8 + … = 2n

Pizza misoli: avval butun pizzani, keyin yarmini, keyin chorakini yeysiz… Qancha davom ettirsangiz ham, ikki pizzadan oshmaydi. Shuning uchun quickselect o'rtacha O(n). Kodning murakkabligini hisoblash darsidagi jadvalda bu "1 chaqiruv, yarim, O(n) ish → O(n)" qatori edi.

Quick sort bilan farq: u ikkala yarimga boradi — har qatlamda jami n ish, log n qatlam → n log n. Quickselect bitta yarimga boradi — har qatlam oldingisidan ikki baravar arzon.

Solishtirishlarni sanab tekshiramiz:

let comparisons = 0;

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

function quickselect(arr, k, random) {
  let lo = 0;
  let hi = arr.length - 1;
  while (lo < hi) {
    const r = lo + (random() % (hi - lo + 1)); // tasodifiy pivot
    [arr[r], arr[hi]] = [arr[hi], arr[r]];
    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]];
    if (i === k) return arr[i];
    if (k < i) hi = i - 1; // faqat chap qism
    else lo = i + 1; // faqat o'ng qism
  }
  return arr[lo];
}

const random = makeRandom(2026);
for (const n of [1000, 10_000, 100_000, 1_000_000]) {
  const nums = Array.from({ length: n }, random);
  comparisons = 0;
  quickselect(nums, Math.floor(n / 2), random);
  const ratio = (comparisons / n).toFixed(1);
  console.log(`n=${n}: ${comparisons} ta (${ratio}·n)`);
}

Konsolda:

n=1000: 2146 ta (2.1·n)
n=10000: 36024 ta (3.6·n)
n=100000: 241567 ta (2.4·n)
n=1000000: 4043465 ta (4.0·n)

Solishtirishlar soni doim n ning bir necha baravari — 2 dan 4 gacha. n ming baravar oshdi, nisbat esa "suzib" yuribdi, lekin o'smayapti. Bu chiziqli o'sish belgisi. Nazariya mediana uchun o'rtacha ≈ 3,4·n beradi; bizning raqamlar tasodifga qarab shu atrofda tebranadi. Saralash esa n · log₂ n: million elementda ≈ 20·n.

3.2 Eng yomon holat

Pivot har safar chetga tushsa (eng kichik yoki eng katta), qism faqat bittaga kichrayadi: n + (n − 1) + … ≈ n² ÷ 2. Bu quick sort'ning tuzog'i bilan bir xil. Tasodifiy pivot bilan bu juda kam ehtimolli.

Eng yomon holatda ham O(n) kafolat beradigan algoritm bor — medianalar medianasi (median of medians). Uni 1973-yilda Blum, Floyd, Pratt, Rivest va Tarjan taklif qilgan. Massivni 5 talik guruhlarga bo'lib, har guruh medianasidan "yaxshi" pivot yasaydi. Kafolat chiroyli, lekin o'zgarmas ko'paytuvchi katta — amalda tasodifiy pivot tezroq. Kutubxonalar ikkalasini birlashtiradi (introselect): odatda tasodifiy, ish cho'zilib ketsa — medianalar medianasi.

Tekshirib ko'ring: Pivot har safar aynan o'rtaga tushdi deylik. 1 000 000 ta chekda barcha partition lar jami taxminan nechta elementni ko'radi? Butun sonda, millionlarda yozing:

4. O'lchov: quickselect va saralash

Medianani topish — tasodifiy sonlar (urug' 2026). Performansni o'lchash darsidagi usul bilan o'lchadik: har n alohida jarayonda, avval isitish, 7 o'lchovning medianasi:

Ikkala ustunda ham n ikki baravar — vaqt taxminan ikki baravar. Bu oraliqda n log n va n ni nisbat bo'yicha ajratish qiyin: log₂ n 18 dan 21 ga — atigi 1,17 baravar. Lekin mutlaq farq aniq: quickselect 13 baravar tez. Quickselect'ning nisbatlari ko'proq tebranadi (×1,8–2,1) — tasodifiy pivot har safar boshqa yo'l tanlaydi.

5. Mediana: toq va juft

Toq sonli ro'yxatda mediana — aynan o'rtadagi. Juft sonli ro'yxatda o'rtada ikkita element bor; odatda ularning o'rtachasi olinadi: [12, 35, 48, 5] → saralangan [5, 12, 35, 48] → (12 + 35) ÷ 2 = 23,5.

Ikki quickselect bilan hisoblaymiz: n ÷ 2 − 1 va n ÷ 2 indekslari. Har biri O(n), jami ham O(n).

function median(nums) {
  const n = nums.length;
  if (n === 0) return undefined;
  const upper = kthSmallest(nums, Math.floor(n / 2));
  if (n % 2 === 1) return upper;
  const lower = kthSmallest(nums, n / 2 - 1);
  return (lower + upper) / 2;
}

kthSmallest — nusxa oladigan quickselect, uni 3-mashqda to'liq yozasiz. Bitta nozik joy: ikkinchi quickselect'ni ham nusxada ishlatsak, birinchisining ishi qayta qilinadi. Optimallashtirish mumkin: birinchi chaqiruvdan keyin n ÷ 2 - 1 element shu massivning chap qismidagi eng kattasi — uni bitta sikl bilan topsa bo'ladi. Big-O o'zgarmaydi, ish taxminan yarmiga kamayadi.

Tekshirib ko'ring: Cheklar: [30, 35, 32, 25000] (ming so'mda; oxirgisi — to'y). O'rtacha va mediana qancha? Qaysi biri "odatiy chek" ga yaqin?

6. Top-K: eng qimmat k ta chek

6.1 Quickselect bilan

Jasur akaga oyning eng qimmat 3 ta cheki kerak. k-chi eng katta element — saralangan tartibda n - k indeksda turadi. Quickselect uni o'z joyiga qo'yganda, undan o'ngdagilarning hammasi kattaroq — aynan eng katta k ta, faqat o'zaro tartibsiz. Faqat ularni saralaymiz:

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;
}

// arr ni shunday joylaydiki, k-indeksda k-chi eng kichik tursin
function selectInPlace(arr, k) {
  let lo = 0;
  let hi = arr.length - 1;
  while (lo < hi) {
    const p = partition(arr, lo, hi);
    if (p === k) return;
    if (k < p) hi = p - 1;
    else lo = p + 1;
  }
}

function topK(sums, k) {
  const arr = [...sums]; // asl ro'yxatga tegmaymiz
  selectInPlace(arr, arr.length - k);
  // oxirgi k ta — eng kattalar; faqat ularni saralaymiz
  return arr.slice(arr.length - k).sort((a, b) => b - a);
}

const sums = [35, 12, 48, 5, 28, 90, 18, 30, 8, 25, 40];
console.log(topK(sums, 3)); // [ 90, 48, 40 ]
console.log(sums.length, sums[0]); // 11 35

Qadamma-qadam: 11 ta chek, k = 3. Eng qimmat uchtalikning eng arzoni — saralangan ro'yxatda 11 − 3 = 8-indeksda (bu 40 ming). Funksiya selectInPlace uni 8-indeksga qo'yadi. O'ngida, 9 va 10-indekslarda, 48 va 90 qoladi — qaysi tartibda, farqi yo'q. Keyin slice oxirgi uchtasini oladi, sort ularni kamayish tartibida teradi.

Narxi: quickselect O(n) + k ta elementni saralash O(k log k). k kichik bo'lsa — deyarli O(n).

6.2 Uch yondashuv

Uchinchi qator haqida. Heap — eng kichik elementni doim tepada saqlaydigan maxsus daraxt; uni Heap darsida o'rganamiz, hozir bilish shart emas. Uning afzalligi: cheklar bittalab kelsa (masalan, kun davomida kassadan), hammasini xotirada saqlamay, faqat eng yaxshi k tasini ushlab turish mumkin. Quickselect esa hamma ma'lumot bir vaqtda massivda bo'lishini talab qiladi. Bu taqqoslashni Priority queue va heap naqshlari darsida o'lchov bilan davom ettiramiz.

Tekshirib ko'ring: 10 million chekdan eng qimmat 10 tasi kerak. Saralash va quickselect taxminan necha baravar farq qiladi?

7. Chegaraviy holatlar

To'rtinchi qatorni quick sort darsidan eslang: hamma element teng bo'lsa, Lomuto har safar pivotni chetga qo'yadi. Quickselect'da ham xuddi shu. Takrorlar ko'p bo'lsa, uch yo'lli bo'lish qiling. U massivni ikkiga emas, uchga ajratadi: pivotdan kichiklar, pivotga tenglar va kattalar. k "tenglar" zonasiga tushsa — darhol javob: bu zonadagi hamma element pivotning o'zi.

8. Ko'p uchraydigan xatolar

8.1 Asl massivni buzib qo'yish

quickselect(sums, 5) dan keyin sums ning tartibi o'zgarib ketadi. Agar u boshqa joyda ishlatilsa (masalan, ekranda kelish tartibida ko'rsatilsa), xato paydo bo'ladi — va bu xato boshqa joyda chiqadi. Tuzatish: [...sums] nusxasida ishlang yoki funksiya nomida aytib qo'ying: selectInPlace.

8.2 k ni 1 dan sanash

"3-eng kichik" — insonlar 1 dan sanaydi, indeks esa 0 dan. quickselect(arr, 3) — to'rtinchi eng kichik. Tuzatish: chegarani bitta joyda o'giring: kthSmallest(arr, place - 1).

8.3 k-chi eng katta uchun noto'g'ri indeks

k-chi eng katta — n - k indeksda (k 1 dan sanalganda). n - k - 1 yoki k yozish — bittaga adashish. Tuzatish: kichik misolda tekshiring: n = 5, eng katta (k = 1) — indeks 4 = 5 − 1.

8.4 O'rtacha va medianani chalkashtirish

O'rtacha — hammasi yig'indisi ÷ n, O(n), quickselect kerak emas. Mediana — o'rtadagi qiymat. Ular faqat simmetrik ma'lumotda bir xil chiqadi. Bitta to'y cheki o'rtachani 300 mingga ko'taradi, mediana esa 35 mingda qoladi.

9. Mashqlar

1-mashq (oson): Qaysi tomonga?

partition dan keyin pivot 7-indeksga tushdi, siz esa 3-indeksdagi elementni qidiryapsiz. Keyingi qadamda qaysi qism bilan ishlaysiz — "chap" yoki "o'ng"?

2-mashq (o'rta): k-chi eng katta chek

kthLargest(sums, k) funksiyasini yozing (k 1 dan sanaladi: 1 — eng kattasi). Darsdagi quickselect ni qayta ishlating. [35, 12, 48, 5, 28, 90] uchun k = 2 da 48 chiqsin.

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

function quickselect(arr, k, random) {
  let lo = 0;
  let hi = arr.length - 1;
  while (lo < hi) {
    const r = lo + (random() % (hi - lo + 1));
    [arr[r], arr[hi]] = [arr[hi], arr[r]];
    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]];
    if (i === k) return arr[i];
    if (k < i) hi = i - 1;
    else lo = i + 1;
  }
  return arr[lo];
}

const random = makeRandom(11);
function kthLargest(sums, k) {
  return quickselect([...sums], sums.length - k, random);
}

const sums = [35, 12, 48, 5, 28, 90];
console.log(kthLargest(sums, 1)); // 90
console.log(kthLargest(sums, 2)); // 48
console.log(kthLargest(sums, 6)); // 5

3-mashq (qiyin): kthSmallest va median testlari

kurs/mashqlar/14/35-quickselect/select.test.mjs faylida kthSmallest(nums, k) (asl massivga tegmaydi, noto'g'ri k da undefined) va median(nums) ni yozing. Testlar (node:test):

1. Bo'sh, bitta element va chegaradan tashqari k.
2. Toq va juft uzunlikdagi mediana.
3. Takroriy qiymatlar; asl massiv o'zgarmagan.
4. Urug'li tasodifiy 200 ta son: har k uchun javob saralangan massivning k-elementiga teng.

// kurs/mashqlar/14/35-quickselect/select.test.mjs
import { test } from "node:test";
import assert from "node:assert/strict";

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

// k-chi eng kichik (k — 0 dan); asl massivga tegmaydi
function kthSmallest(nums, k) {
  if (k < 0 || k >= nums.length) return undefined;
  const arr = [...nums];
  let lo = 0;
  let hi = arr.length - 1;
  while (lo < hi) {
    const r = lo + (random() % (hi - lo + 1));
    [arr[r], arr[hi]] = [arr[hi], arr[r]];
    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]];
    if (i === k) return arr[i];
    if (k < i) hi = i - 1;
    else lo = i + 1;
  }
  return arr[lo];
}

function median(nums) {
  const n = nums.length;
  if (n === 0) return undefined;
  const upper = kthSmallest(nums, Math.floor(n / 2));
  if (n % 2 === 1) return upper;
  const lower = kthSmallest(nums, n / 2 - 1);
  return (lower + upper) / 2;
}

test("chegaraviy: bo'sh, bitta, noto'g'ri k", () => {
  assert.equal(median([]), undefined);
  assert.equal(median([7]), 7);
  assert.equal(kthSmallest([1, 2, 3], 3), undefined);
});

test("mediana: toq va juft uzunlik", () => {
  assert.equal(median([35, 12, 48, 5, 28]), 28);
  assert.equal(median([35, 12, 48, 5]), 23.5); // (12 + 35) / 2
});

test("takrorlar va asl massiv o'zgarmaydi", () => {
  const sums = [5, 5, 5, 1, 5];
  assert.equal(kthSmallest(sums, 0), 1);
  assert.equal(kthSmallest(sums, 4), 5);
  assert.deepEqual(sums, [5, 5, 5, 1, 5]);
});

test("har k uchun saralash bilan bir xil (urug'li tasodifiy)", () => {
  const nums = Array.from({ length: 200 }, () => random() % 50);
  const sorted = nums.toSorted((a, b) => a - b);
  for (let k = 0; k < nums.length; k++) {
    assert.equal(kthSmallest(nums, k), sorted[k]);
  }
});

✔ chegaraviy: bo'sh, bitta, noto'g'ri k (0.8072ms)
✔ mediana: toq va juft uzunlik (0.1944ms)
✔ takrorlar va asl massiv o'zgarmaydi (0.6934ms)
✔ har k uchun saralash bilan bir xil (urug'li tasodifiy) (6.1805ms)
ℹ tests 4
ℹ suites 0
ℹ pass 4
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 95.8359

4-mashq: Amaliy tajriba — jadvalga uch qator

kurs/mashqlar/14/MURAKKABLIK.md ga qo'shing: mediana (saralash va quickselect), top-K (quickselect). O'rtacha va eng yomon vaqtni alohida yozing.

| Masala | Yechim | Vaqt | Xotira | Izoh |
|---|---|---|---|---|
| Mediana | toSorted + indeks | O(n log n) | O(n) | sodda |
| Mediana | quickselect | O(n) o'rt., O(n²) yomon | O(1) (+ nusxa O(n)) | tasodifiy pivot |
| Top-K | quickselect + k log k | O(n + k log k) o'rt. | O(n) nusxa | hamma ma'lumot qo'lda |

git add 14/MURAKKABLIK.md 14/35-quickselect
git commit -m "14/35: quickselect, mediana va top-K"

10. Real ishda

• Statistika va monitoring. Javob vaqtlarining medianasi (p50) va 95-persentili (p95) — server monitoringining asosiy raqamlari. Persentil (percentile) — qiymatlarning shuncha foizi undan kichik bo'lgan chegara: "p95 = 200 ms" — so'rovlarning 95 foizi 200 ms dan tez. Ya'ni p95 — k = 0,95·n bo'lgan k-chi element, mediana esa p50. Katta hajmda taxminiy algoritmlar ishlatiladi, lekin g'oya — tanlash.
• Standart kutubxonalar. C++ std::nth_element — introselect (quickselect + kafolat). NumPy'da np.partition va np.median ham tanlash algoritmiga tayanadi. JavaScript'da tayyori yo'q.
• Grafika va geometriya. k-d daraxt qurishda har qadamda nuqtalarning medianasi bo'yicha bo'linadi — har safar quickselect.
• Intervyu. LeetCode 215 "Kth Largest Element" — eng mashhur savollardan. Kutilgan javob: avval saralash (O(n log n)), keyin heap (O(n log k)), keyin quickselect (o'rtacha O(n)) — har biri bilan narxi.

Xulosa

• Quickselect = partition + faqat k turgan tomonga borish. Rekursiyasiz, stek O(1).
• O'rtacha O(n): n + n/2 + n/4 + … ≈ 2n. Solishtirishlar 2·n–4·n, saralash esa n · log₂ n.
• Eng yomon O(n²) — tasodifiy pivot bilan kam ehtimolli; medianalar medianasi O(n) kafolat beradi.
• Massiv joyida qayta joylanadi — kerak bo'lsa nusxa oling. k ni 0 dan sanang; k-chi eng katta — n - k indeks.
• Top-K: hammasi qo'lda — quickselect; ma'lumot oqim bo'lib keladi — heap.

Keyingi dars: Daraxt atamalari va binar daraxt — chiziqli tuzilmalardan ierarxik tuzilmaga: ildiz, tugun, barg, chuqurlik va balandlik.

Manbalar

• C. A. R. Hoare, "Algorithm 65: Find", Communications of the ACM 4(7), 1961.
• M. Blum, R. W. Floyd, V. Pratt, R. L. Rivest, R. E. Tarjan, "Time bounds for selection", Journal of Computer and System Sciences 7(4), 1973.
• Thomas H. Cormen va boshq., "Introduction to Algorithms", 4-nashr, MIT Press, 2022 — 9-bob (tanlash).
• LeetCode 215 "Kth Largest Element in an Array" — leetcode.com