Chiziqli saralashlar va JS sort ichidan: counting, radix, bucket va V8 TimSort

Qisqacha: Solishtirib saralaydigan algoritm O(n log n) dan tez bo'la olmaydi. Lekin qiymatlar kichik diapazonda bo'lsa (baho 1–5, yosh 0–120), ularni sanab O(n + k) da saralash mumkin — bu counting sort. Radix sort uzun sonlarni raqamma-raqam, bucket sort esa tekis taqsimlangan qiymatlarni savatlarga bo'lib saralaydi. JavaScript'ning sort i esa V8 da TimSort (Node 24) — merge sort'ning moslashuvchan, barqaror avlodi; Chrome 149 dan boshlab uning o'rnini PowerSort egalladi.

Bu darsda

• Counting sort'ni yozasiz va uni barqaror qilasiz (obyektlar uchun).
• Radix va bucket sort qanday ishlashini va qachon foydali ekanini tushuntira olasiz.
• V8 ichidagi sort ning tarixini va TimSort g'oyasini (yugurishlar, birlashtirish) bilasiz.
• Taqqoslash funksiyasining qoidalarini va (a, b) => a > b tuzog'ini tanib olasiz.

Oldin bilishingiz kerak: Saralash tushunchalari, Merge sort, Quick sort, Prefix sum, sort va taqqoslash funksiyasi.

1. Nega bu kerak?

Saralash tushunchalari darsida qattiq chegarani ko'rgan edik: faqat solishtirib ishlaydigan har qanday saralash eng yomon holatda kamida n · log₂ n atrofida solishtirish qiladi. Merge sort va quick sort bu chegaraga yetib kelgan. Undan tez bo'lmaydi.

Lekin «Bahor»da bitta qiziq masala bor. Har kuni mehmonlar taomga baho qo'yadi — 1 dan 5 gacha. Oyiga 100 000 ta baho yig'iladi. Jasur aka ularni tartiblangan holda ko'rmoqchi. Sardor so'radi: "Qiymatlar atigi beshta. Har bahoni boshqa baholar bilan solishtirib o'tirishimiz shartmi?"

Shart emas. "Nechta besh, nechta to'rt..." deb sanash yetadi. Chegaradagi so'zga qarang: solishtirib. Solishtirmasak, chegara bizga tegishli emas. Bugun shunday uch algoritmni ko'ramiz. Keyin JavaScript'ning o'z sort i ichiga qaraymiz — u qaysi algoritm va nega aynan shu.

2. Counting sort — sanab saralash

2.1 G'oya

Avval hayotdan rasm. Saylov uchastkasini tasavvur qiling: har nomzod uchun bitta quti bor. Har kim qog'ozini o'z qutisiga tashlaydi — qog'ozlarni bir-biri bilan solishtirmaydi. Oxirida qutilarni chapdan o'ngga ochib, sanaymiz. «Bahor»da ham shunday: har baho uchun bitta "quti", har mehmon bahosi o'z qutisiga tushadi.

Endi kodda. Baholar 0 dan 5 gacha bo'lsin. 6 ta katakli count massivini ochamiz: count[v] — v bahodan nechta borligi. Ro'yxatni bir marta yurib, sanaymiz. Keyin count ni 0 dan 5 gacha yurib, har bahoni shuncha marta yozamiz:

Birorta ham a < b bo'lmadi. Ish — n ta baho (sanash) va k ta katak (yozish). Bu — counting sort (sanab saralash).

2.2 Kod

function countingSort(ratings, maxValue) {
  const count = new Array(maxValue + 1).fill(0);
  for (const r of ratings) count[r]++; // har bahodan nechta
  const result = [];
  for (let v = 0; v <= maxValue; v++) {
    for (let c = 0; c < count[v]; c++) result.push(v);
  }
  return result;
}

const ratings = [4, 5, 3, 5, 1, 4, 5, 2, 4, 3];
console.log(countingSort(ratings, 5));

Konsolda:

[
  1, 2, 3, 3, 4,
  4, 4, 5, 5, 5
]

• new Array(maxValue + 1).fill(0) — maxValue + 1 ta nol. Indeks — qiymatning o'zi: count[4] — to'rtlar soni.
• Ichma-ich sikl qo'rqitmasin: ichki sikl jami n marta aylanadi (har baho bir marta yoziladi), tashqi — k marta. Jami O(n + k).
• Xotira: count — O(k), natija — O(n).

2.3 Qachon foydali, qachon zararli

Bu yerda k — qiymatlar diapazoni, ya'ni count massivi nechta katakdan iborat. Counting sort faqat butun sonlarda va k n dan katta bo'lmaganda foydali. 1 000 ta narxni saralash uchun million katakli massiv ochish — isrof. Manfiy sonlar bo'lsa, eng kichik qiymatni ayirib, indeksni surish kerak (count[x - min]).

Tekshirib ko'ring: «Bahor» xodimlarining tug'ilgan yili (1960–2008) bo'yicha 40 ta xodimni saralash kerak. Counting sort'da count massivi qancha katak bo'ladi va bu foydalimi?

3. Barqaror counting sort

3.1 Muammo: obyektlar

Baholarning o'zini emas, sharhlarni saralash kerak bo'lsa-chi? Har sharhda mehmon ismi va baho bor. "Nechta besh bor" degan son yetmaydi — qaysi sharh qayerga tushishini bilish kerak. Ustiga-ustak, bir xil bahoda sharhlar yozilgan tartibda qolsin (barqarorlik).

Yechim — prefix sum. Sanagandan keyin count ni "boshlanish joyi" ga aylantiramiz: count[v] — v bahoning natijada qaysi indeksdan boshlanishi. Keyin sharhlarni chapdan o'ngga yurib, har birini o'z joyiga qo'yamiz va joyni bittaga suramiz:

// barqaror counting sort: obyektlarni baho bo'yicha
function countingSortBy(items, key, maxValue) {
  const count = new Array(maxValue + 1).fill(0);
  for (const item of items) count[item[key]]++;
  // prefiks yig'indi: count[v] — v bahoning natijadagi boshlanishi
  let start = 0;
  for (let v = 0; v <= maxValue; v++) {
    const c = count[v];
    count[v] = start;
    start += c;
  }
  const result = new Array(items.length);
  for (const item of items) {
    // chapdan o'ngga yuramiz — teng baholar tartibi saqlanadi
    result[count[item[key]]++] = item;
  }
  return result;
}

const reviews = [
  { guest: "Malika", rating: 5 },
  { guest: "Bobur", rating: 3 },
  { guest: "Dilshod aka", rating: 5 },
  { guest: "Sardor", rating: 4 },
  { guest: "Ali", rating: 3 },
];
for (const r of countingSortBy(reviews, "rating", 5)) {
  console.log(r.rating, r.guest);
}

Konsolda:

3 Bobur
3 Ali
4 Sardor
5 Malika
5 Dilshod aka

Sanashdan keyin count = [0, 0, 0, 2, 1, 2]. Prefiks yig'indidan keyin [0, 0, 0, 0, 2, 3]: uchlar 0-indeksdan, to'rt — 2 dan, beshlar — 3 dan boshlanadi. Malika birinchi bo'lib 3-o'ringa tushdi va beshlar joyi 4 ga surildi — Dilshod aka 4-o'ringa. Ular yozilgan tartibida qoldi.

result[count[item[key]]++] = item — zich qator. Uni bo'lib o'qing: count[item[key]] — shu bahoning navbatdagi bo'sh joyi; ++ — keyingi safar uchun joyni suradi.

4. Radix sort — raqamma-raqam

4.1 G'oya

Buyurtma raqamlari olti xonali: 100 000 dan 999 999 gacha. Counting sort uchun bu million katak — zararli. Lekin har raqam atigi 0–9. Unda raqamlar bo'yicha, birma-bir saralasak-chi?

Sirli tomoni — tartib: o'ngdagi (eng kichik) raqamdan boshlaymiz, har o'tishda barqaror saralaymiz. Birlar bo'yicha saralangan ro'yxatni o'nlar bo'yicha barqaror saralasak, o'nlari teng sonlar birlar tartibida qoladi. Uch o'tishdan keyin uch xonali sonlar to'liq saralanadi:

Bu — radix sort (xonalar bo'yicha saralash), aniqrog'i LSD varianti (Least Significant Digit — eng kichik xonadan). Savatlarga tarqatish va 0 dan 9 gacha yig'ish — bu k = 10 bo'lgan barqaror counting sort'ning o'zi.

4.2 Murakkablik

d ta xona, har xonada 10 ta savat: O(d · (n + 10)). Olti xonali raqamlarda d = 6 — o'zgarmas. Demak, n bo'yicha chiziqli. Xotira — O(n) (savatlar).

Lekin "chiziqli" har doim "tez" degani emas. Har o'tishda n ta son yangi massivlarga ko'chadi. O'lchovimiz: 250 000 ta olti xonali raqam — ≈ 58 ms, 500 000 — ≈ 106 ms (×1,8), 1 000 000 — ≈ 233 ms (×2,2), 2 000 000 — ≈ 509 ms (×2,2). Xuddi shu sonlarda toSorted: ≈ 76, 160, 330 va 715 ms. Radix sort tezroq, lekin farq atigi 1,4 baravar — counting sort'dagidek o'n baravar emas. Olti o'tish, har birida o'nta yangi massiv va hamma sonni ko'chirish — o'zgarmas ko'paytuvchi katta.

4.3 Matnlar uchun ham

Radix sort bir xil uzunlikdagi satrlarni ham saralaydi: telefon raqamlari, sana kodlari (20261006), mahsulot artikullari. Har "xona" — bitta belgi. Shuning uchun u pochta indekslari va katta hajmdagi kalitlar bilan ishlaydigan tizimlarda uchraydi.

5. Bucket sort — savatlarga bo'lish

Yetkazish vaqtlari — 0 dan 60 daqiqagacha, kasr sonlar: 12,5; 47,1; 3,8... Counting sort kasr bilan ishlamaydi. Lekin vaqtlar diapazonda taxminan tekis taqsimlangan: har 10 daqiqalik oraliqqa taxminan bir xil miqdorda vaqt tushadi, hammasi bir burchakka to'planib qolmaydi. Diapazonni 6 ta savatga bo'lamiz: 0–10, 10–20, …, 50–60. Har vaqtni o'z savatiga tashlaymiz, har savatni alohida saralaymiz va ketma-ket ulaymiz:

// yetkazish vaqtlari, daqiqada (0 dan 60 gacha, kasr bilan)
function bucketSort(times, bucketCount = 6, maxValue = 60) {
  const buckets = Array.from({ length: bucketCount }, () => []);
  for (const t of times) {
    const index = Math.min(
      bucketCount - 1,
      Math.floor((t / maxValue) * bucketCount),
    );
    buckets[index].push(t);
  }
  console.log(buckets.map((b) => b.join(", ") || "—").join(" | "));
  // har savat kichik — ichini oddiy saralash bilan
  return buckets.flatMap((b) => b.sort((x, y) => x - y));
}

const times = [12.5, 47.1, 3.8, 33.3, 18.0, 41.9, 7.2, 25.6, 59.5];
console.log(bucketSort(times).join(" "));

Konsolda:

3.8, 7.2 | 12.5, 18 | 25.6 | 33.3 | 47.1, 41.9 | 59.5
3.8 7.2 12.5 18 25.6 33.3 41.9 47.1 59.5

• Math.min(bucketCount - 1, …) — chetdagi qiymat (aynan 60) 6-indeksga tushib qolmasligi uchun.
• flatMap har savatni saralab, hammasini bitta massivga yoyadi (flat va flatMap).

Vaqt tekis taqsimlangan bo'lsa, har savatda o'rtacha bir necha element — o'rtacha O(n). Lekin hamma vaqt bitta savatga tushsa (masalan, hammasi 40–45 daqiqa), bucket sort bitta katta saralashga aylanadi. Shuning uchun u faqat taqsimotni oldindan bilganda ishlatiladi.

Tekshirib ko'ring: Nega radix sort o'ngdan (birlardan) boshlaydi? Chapdan (yuzlardan) boshlasa nima bo'ladi?

6. O'lchov: counting sort va toSorted

250 000 dan 2 000 000 gacha baho (0–100). Performansni o'lchash darsidagi usul bilan o'lchadik: har n alohida jarayonda, avval isitish, urug'li kirish, 7 o'lchovning medianasi:

Ikkalasida ham n ikki baravar — vaqt taxminan ikki baravar. Kutilgan edi: toSorted da log n ning o'sishi bu oraliqda juda kichik (log₂ 250 000 ≈ 18, log₂ 2 000 000 ≈ 21). Asosiy farq — o'zgarmas ko'paytuvchida: counting sort o'n baravar tez. U hech qanday funksiya chaqirmaydi, faqat indeks bilan katakni oshiradi.

Teskari tomoni ham o'lchandi: atigi 1 000 ta son, lekin diapazon katta. Diapazon 1 000 000 bo'lganda counting sort ≈ 4,9 ms oldi, 2 000 000 da — ≈ 9,5 ms, 4 000 000 da — ≈ 20 ms, 8 000 000 da — ≈ 40 ms. Sonlar soni o'zgarmadi, k esa ikki baravar oshdi — vaqt ham ikki baravar. Bu O(n + k) dagi k ning "narxi": 1 000 ta sonni toSorted bilan saralash bundan yuzlab baravar arzon.

7. JavaScript'ning sort i ichidan

7.1 Qisqa tarix

V8 jamoasi 2018-yil sentabrdagi "Getting things sorted in V8" maqolasida (Simon Zünd, v8.dev) o'tishni tushuntirgan. Oldingi quick sort barqaror emas edi va maxsus tuzilgan kirishda sekinlashardi. Yangi algoritm Torque'da yozildi — V8 ichki funksiyalari uchun maxsus til.

2026-yil 20-aprelda V8 ga "TimSort → PowerSort" o'zgarishi kiritildi (commit izohida: "macrobenchmarks are neutral" — tezlik deyarli o'zgarmadi, lekin birlashtirish tartibi isbotlangan holda deyarli optimal). Bu V8 14.9 ga, ya'ni Chrome 149 ga tushdi. Python ham 3.11 versiyadan (2022) PowerSort'ga o'tgan.

Hozir kursda ishlatayotgan ikki muhit:

• Node 24.21 — V8 13.6 → TimSort.
• Chrome 154 — V8 15.4 → PowerSort.

Ikkalasi ham barqaror va O(n log n). Farq faqat ichki tafsilotda — taqqoslash funksiyasi necha marta va qaysi juftlar bilan chaqirilishida.

7.2 TimSort g'oyasi: tayyor bo'laklardan foydalanish

TimSort'ni 2002-yilda Tim Peters Python uchun yozgan. U merge sort'ning "moslashuvchan" (adaptive) varianti. Asosiy kuzatuv: real ma'lumot kamdan-kam butunlay aralash bo'ladi. Unda allaqachon tartiblangan bo'laklar ko'p uchraydi — ular yugurish (run) deyiladi.

1. Massivni chapdan yurib, yugurishlarni topadi. Kamayib boruvchi yugurishni joyida teskari aylantiradi.
2. Juda qisqa yugurishni (V8 da 32–64 elementgacha, aniq uzunlik n ga qarab hisoblanadi) ikkiga bo'lib qidirishli insertion sort bilan uzaytiradi (Oddiy saralashlar).
3. Yugurishlarni stekka qo'yib, merge sort'dagidek juft-juft birlashtiradi.
4. Birlashtirishda bir tomon ketma-ket 7 marta "yutsa", galloping (chopish) rejimiga o'tadi — elementlarni bittalab emas, sakrab-sakrab qidiradi: 1, 2, 4, 8… qadam oldinga, keyin topilgan oraliq ichida ikkiga bo'lib qidirish.

Natija Node'da yaqqol ko'rinadi. Taqqoslash funksiyasi necha marta chaqirilishini sanaymiz:

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

function countComparisons(arr) {
  let comparisons = 0;
  arr.toSorted((a, b) => {
    comparisons++;
    return a - b;
  });
  return comparisons;
}

const n = 1000;
const random = makeRandom(2026);
const half = Array.from({ length: n / 2 }, (_, i) => i * 2);
const inputs = {
  saralangan: Array.from({ length: n }, (_, i) => i),
  teskari: Array.from({ length: n }, (_, i) => n - i),
  "ikki saralangan bo'lak": [...half, ...half.map((x) => x + 1)],
  tasodifiy: Array.from({ length: n }, random),
};
for (const [name, arr] of Object.entries(inputs)) {
  console.log(`${name}: ${countComparisons(arr)}`);
}

Konsolda (Node 24.21):

saralangan: 999
teskari: 999
ikki saralangan bo'lak: 1998
tasodifiy: 8616

Saralangan va teskari ro'yxatda — atigi n − 1 ta solishtirish: bitta yugurish topildi (teskarisi aylantirildi) va tamom. Ikki saralangan bo'lak — ikki yugurish, bitta birlashtirish. Tasodifiy ro'yxatda esa 8 616 ta, n · log₂ n ≈ 9 966 ga yaqin. Insertion sort'ning yaxshi tomoni (saralanganda O(n)) va merge sort'ning kafolati (O(n log n)) bitta algoritmda.

Shu kodni Chrome 154 da ishga tushirdik: birinchi uch qator aynan shunday, tasodifiyda esa 8 626 ta. Bitta raqam farqi — PowerSort'ning boshqa birlashtirish tartibidan. Shuning uchun sort va taqqoslash funksiyasi darsida aytilgan gap muhim: taqqoslash funksiyasi qaysi juftlar bilan chaqirilishiga tayanmang — u dvigatelga bog'liq.

7.3 Barqarorlikni o'zimiz tekshiramiz

Standart barqarorlikni talab qiladi. Ishonamiz, lekin tekshiramiz: 100 000 ta buyurtmani uchta holat bo'yicha saralab, bir xil holatdagilar kelish tartibida qolganini ko'ramiz.

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

const random = makeRandom(7);
// 100 000 buyurtma: 3 xil holat, id — kelish tartibi
const orders = Array.from({ length: 100000 }, (_, id) => ({
  id,
  status: random() % 3,
}));
const sorted = orders.toSorted((a, b) => a.status - b.status);

let stable = true;
for (let k = 1; k < sorted.length; k++) {
  const prev = sorted[k - 1];
  const cur = sorted[k];
  if (prev.status === cur.status && prev.id > cur.id) stable = false;
}
console.log(`barqaror: ${stable}`); // barqaror: true

Node 24.21 da ham, Chrome 154 da ham — true. vazifalar ilovasidagi saralash (Saralash tushunchalari darsidagi qadam) aynan shunga tayanadi: bir xil guruhdagi vazifalar qo'shilgan tartibida qoladi.

8. Taqqoslash funksiyasi qoidalari

8.1 Shartnoma

sort taqqoslash funksiyasidan uchta narsani kutadi:

1. Ishora: manfiy — a oldin, musbat — b oldin, 0 — teng.
2. Izchillik: bir juftga har safar bir xil javob. cmp(a, b) manfiy bo'lsa, cmp(b, a) musbat bo'lsin.
3. O'tuvchanlik: a < b va b < c bo'lsa, a < c ham bo'lsin.

Bu shartlar buzilsa, standart natijani "implementation-defined" — dvigatelning o'zi hal qiladi deb qoldiradi. Xato chiqmaydi — tartib shunchaki noto'g'ri bo'ladi.

8.2 (a, b) => a > b tuzog'i

Internetda tez-tez uchraydigan xato. U true yoki false qaytaradi — son emas. sort ularni 1 va 0 ga aylantiradi. "Manfiy" javob hech qachon kelmaydi:

const nums = [5, 1, 4, 2, 3, 1, 5, 2, 4, 3, 1, 2];
console.log(nums.toSorted((a, b) => a > b).join(" "));
console.log(nums.toSorted((a, b) => a - b).join(" "));

Konsolda:

5 1 4 2 3 1 5 2 4 3 1 2
1 1 1 2 2 2 3 3 4 4 5 5

Kutilmagan natija: birinchi massiv umuman o'zgarmadi! Node 24 da ham, Chrome 154 da ham. TimSort chap elementni "oldin turishi kerakmi?" deb so'raganda, javob false (0 — "teng") yoki true (1 — "keyin"). Teng elementlarni barqaror saralash joyida qoldiradi. Eski quick sort'li V8 da bu ba'zan "ishlab" ketardi — shuning uchun eski kodda uchraydi. Tuzatish: sonlar uchun a - b, satrlar uchun a.localeCompare(b).

8.3 Tasodifiy aralashtirish sort bilan emas

arr.sort(() => Math.random() - 0.5) — izchillik qoidasini ataylab buzadi: bir juftga har safar boshqa javob. Natija "aralash" ko'rinadi, lekin tartiblar teng ehtimolli emas va algoritmga bog'liq. To'g'ri usul — Fisher–Yates aralashtirish: oxiridan boshlab har elementni o'zidan oldingi tasodifiy element bilan almashtirish, O(n).

8.4 Default sort va typed massivlar

Taqqoslash funksiyasisiz sort elementlarni satrga aylantirib solishtiradi — [100, 25, 3].sort() → [100, 25, 3] (sort darsidagi tuzoq). Typed massivlar (Int32Array, Float64Array — sonlar uchun maxsus massivlar, Typed arrays) esa default holatda son sifatida saralaydi:

const plain = [100, 25, 3];
const typed = new Int32Array([100, 25, 3]);
console.log(plain.sort()); // [ 100, 25, 3 ]
console.log(typed.sort()); // Int32Array(3) [ 3, 25, 100 ]

9. Chegaraviy holatlar

10. Ko'p uchraydigan xatolar

10.1 Katta diapazonda counting sort

Narxlar 0 dan 1 000 000 gacha, n = 1 000. count million katakli bo'ladi — vaqt n emas, k ga bog'liq. Tuzatish: k n dan ancha katta bo'lsa (k ≫ n) — oddiy toSorted.

10.2 Radix sort'da barqaror bo'lmagan ichki saralash

Har o'tish barqaror bo'lishi shart. Savatga push va 0 dan 9 gacha yig'ish — barqaror. Agar savatlarni teskari yig'sangiz yoki ichki saralash sifatida quick sort ishlatsangiz, oldingi o'tishlarning ishi yo'qoladi. Tuzatish: savatlar yoki barqaror counting sort.

10.3 Taqqoslovchidan boolean qaytarish

(a, b) => a > b — yuqorida ko'rdik, massiv o'zgarmay qolishi mumkin. Xato chiqmaydi, shuning uchun bunday kodni testsiz payqash qiyin. Tuzatish: son qaytaring.

10.4 Taqqoslovchi ichida og'ir ish

Taqqoslovchi n log n marta chaqiriladi. Uning ichida har safar toLowerCase, normalize yoki regex — n log n marta qimmat ish. Ilovamiz — vazifalar o'lchovida alifbo bo'yicha saralash kalitsiz (taqqoslovchi ichida normallash) 100 000 vazifada ≈ 21 s, kalit bir marta hisoblanganda ≈ 1,5 s chiqqan. Tuzatish: kalitni oldindan hisoblang (bezash-saralash-qaytarish, Saralash tushunchalari).

11. Mashqlar

1-mashq (oson): count ni to'ldiring

countingSort([2, 0, 2, 1, 0, 2], 2) uchun sanashdan keyin count massivi qanday bo'ladi? count[2] ning qiymatini yozing:

2-mashq (o'rta): Yosh bo'yicha mehmonlar

Bron ro'yxatida mehmonlarning yoshi bor (0–120). sortGuestsByAge(guests) funksiyasini yozing: barqaror counting sort bilan, bir xil yoshdagilar bron tartibida qolsin. Darsdagi countingSortBy ni qayta ishlating.

const guests = [
  { name: "Jasur aka", age: 45 },
  { name: "Malika", age: 23 },
  { name: "Bobur", age: 23 },
];
// 23 Malika, 23 Bobur, 45 Jasur aka

function countingSortBy(items, key, maxValue) {
  const count = new Array(maxValue + 1).fill(0);
  for (const item of items) count[item[key]]++;
  let start = 0;
  for (let v = 0; v <= maxValue; v++) {
    const c = count[v];
    count[v] = start;
    start += c;
  }
  const result = new Array(items.length);
  for (const item of items) result[count[item[key]]++] = item;
  return result;
}

const sortGuestsByAge = (list) => countingSortBy(list, "age", 120);

const guests = [
  { name: "Jasur aka", age: 45 },
  { name: "Malika", age: 23 },
  { name: "Bobur", age: 23 },
];
for (const g of sortGuestsByAge(guests)) console.log(g.age, g.name);

23 Malika
23 Bobur
45 Jasur aka

3-mashq (qiyin): Radix sort testlari bilan

kurs/mashqlar/14/31-chiziqli/radix.test.mjs faylida radixSort(nums) ni yozing: manfiy bo'lmagan butun sonlar uchun LSD radix sort. Xonalar soni eng katta sondan aniqlansin. Asl massiv o'zgarmasin. Testlar (node:test):

1. Bo'sh, bitta element va faqat nollar.
2. Har xil uzunlikdagi sonlar: [905, 7, 31, 1200, 0].
3. Asl massiv o'zgarmaydi.
4. Urug'li tasodifiy 5 000 ta olti xonali son — natija toSorted bilan bir xil.

// kurs/mashqlar/14/31-chiziqli/radix.test.mjs
import { test } from "node:test";
import assert from "node:assert/strict";

// manfiy bo'lmagan butun sonlar uchun LSD radix sort
function radixSort(nums) {
  if (nums.length === 0) return [];
  let max = 0;
  for (const x of nums) if (x > max) max = x;
  let result = nums;
  for (let place = 1; place <= max; place *= 10) {
    const buckets = Array.from({ length: 10 }, () => []);
    for (const x of result) {
      buckets[Math.floor(x / place) % 10].push(x);
    }
    result = buckets.flat();
  }
  return result === nums ? [...nums] : result;
}

test("chegaraviy: bo'sh, bitta, faqat nollar", () => {
  assert.deepEqual(radixSort([]), []);
  assert.deepEqual(radixSort([7]), [7]);
  assert.deepEqual(radixSort([0, 0, 0]), [0, 0, 0]);
});

test("har xil uzunlikdagi sonlar", () => {
  const sorted = radixSort([905, 7, 31, 1200, 0]);
  assert.deepEqual(sorted, [0, 7, 31, 905, 1200]);
});

test("asl massiv o'zgarmaydi", () => {
  const ids = [30, 5, 12];
  radixSort(ids);
  assert.deepEqual(ids, [30, 5, 12]);
});

test("toSorted bilan bir xil (urug'li tasodifiy)", () => {
  let seed = 32;
  const random = () => (seed = (seed * 16807) % 2147483647);
  const ids = Array.from({ length: 5000 }, () => random() % 1e6);
  assert.deepEqual(radixSort(ids), ids.toSorted((a, b) => a - b));
});

✔ chegaraviy: bo'sh, bitta, faqat nollar (1.4138ms)
✔ har xil uzunlikdagi sonlar (0.2109ms)
✔ asl massiv o'zgarmaydi (0.1297ms)
✔ toSorted bilan bir xil (urug'li tasodifiy) (6.4459ms)
ℹ tests 4
ℹ suites 0
ℹ pass 4
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 101.3001

4-mashq: Amaliy tajriba — jadvalga to'rt qator

kurs/mashqlar/14/MURAKKABLIK.md ga counting, radix va bucket sort'ni, hamda sort/toSorted (V8) ni qo'shing. "Shart" ustunini oching: algoritm qachon ishlaydi.

| Masala | Yechim | Vaqt | Xotira | Barqaror? | Shart |
|---|---|---|---|---|---|
| Baholarni saralash | counting sort | O(n + k) | O(n + k) | ha (prefiks bilan) | butun, kichik k |
| Raqamlarni saralash | radix sort (LSD) | O(d·(n + 10)) | O(n) | ha | sobit xonalar |
| Kasr vaqtlar | bucket sort | O(n) o'rtacha | O(n) | ha | tekis taqsimot |
| Har qanday | sort / toSorted (V8) | O(n log n), saralanganda O(n) | O(n) | ha | izchil taqqoslovchi |

git add 14/MURAKKABLIK.md 14/31-chiziqli
git commit -m "14/31: counting, radix, bucket va V8 sort"

12. Real ishda

• Ma'lumotlar bazalari va katta ma'lumot. Kalitlar sobit uzunlikda bo'lsa (sana, butun id), radix sort'ning turli variantlari ishlatiladi. Kichik diapazondagi guruhlash ("har baho bo'yicha nechta") — counting sort'ning yarmi, ya'ni oddiy sanash: Hash map bilan hisoblash.
• Grafika. Uch o'lchamli sahnada obyektlarni chuqurlik bo'yicha saralashda bucket va radix sort ko'p uchraydi — millionlab nuqta har kadrda.
• Frontend. 99 % holatda toSorted yetarli va to'g'ri tanlov: barqaror, saralangan ma'lumotda O(n), ichki kodda optimallashtirilgan. O'z saralashingizni faqat o'lchov (profil) buni talab qilsa yozing.
• Intervyu. "O(n log n) dan tez saralash mumkinmi?" — "ha, agar solishtirmasak: counting/radix, shartlari bilan". "JS sort qaysi algoritm?" — "V8 da TimSort, endi PowerSort; barqaror (ES2019)".

Xulosa

• Solishtirib saralash O(n log n) dan tez bo'lmaydi; counting, radix va bucket sort solishtirmaydi.
• Counting sort — O(n + k), faqat kichik diapazondagi butun sonlar uchun; prefiks yig'indi bilan barqaror bo'ladi.
• Radix sort — xonalar bo'yicha barqaror o'tishlar, o'ngdan chapga; bucket sort — tekis taqsimotda o'rtacha O(n).
• V8 sort: 2018-gacha quick sort (barqaror emas), Chrome 70 dan TimSort, Chrome 149 dan PowerSort. Node 24 — TimSort.
• Taqqoslovchi son qaytarsin va izchil bo'lsin: (a, b) => a > b massivni o'zgarishsiz qoldirishi mumkin.

Keyingi dars: Binary search asoslari — saralangan ma'lumotning eng katta foydasi: qidiruvni O(log n) ga tushirish va chegaralarda adashmaslik.

Manbalar

• Simon Zünd, "Getting things sorted in V8", v8.dev blogi, 2018-09-28 — v8.dev/blog/array-sort
• V8 manba kodi: third_party/v8/builtins/array-sort.tq — Node 24 (V8 13.6) da TimSort; "[builtins] Sorting: TimSort --> PowerSort" commit'i, 2026-04-20 (V8 14.9) — chromium.googlesource.com/v8/v8
• ECMAScript 2019, Array.prototype.sort — barqarorlik talabi — tc39.es/ecma262
• J. Ian Munro, Sebastian Wild, "Nearly-Optimal Mergesorts", ESA 2018 — PowerSort.
• Tim Peters, "listsort.txt" — TimSort tavsifi, CPython repozitoriysi.