Saralash tushunchalari: barqarorlik, joyida saralash va n log n chegarasi

Qisqacha: Saralash algoritmlari to'rt savol bilan baholanadi. Qancha vaqt oladi (eng yomon va o'rtacha holat)? Qancha qo'shimcha xotira (joyida yoki nusxa bilan)? Barqarormi — teng kalitli elementlar kelgan tartibini saqlaydimi? Adaptivmi — deyarli saralangan kirishda tezlashadimi? Taqqoslab saralaydigan har qanday algoritm eng yomon holatda kamida log₂(n!) ≈ n log₂ n solishtirish qiladi — bu matematik chegara. JavaScript'ning sort/toSorted i (Node 24 dagi V8 da TimSort) barqaror, deyarli shu chegarada ishlaydi va saralangan kirishni n − 1 solishtirishda tugatadi. Ko'p kalitli saralash — || zanjiri yoki barqarorlikka tayanish; qimmat kalit — bezash, saralash, qaytarish.

Bu darsda

• Saralash algoritmini vaqt, xotira, barqarorlik va adaptivlik bo'yicha baholay olasiz.
• Barqaror saralash nima uchun muhimligini va undan ko'p kalitli saralashda qanday foydalanishni ko'rsata olasiz.
• n log n quyi chegarasini "qaror daraxti" bilan tushuntira olasiz va uni toSorted dagi solishtirishlar soni bilan tasdiqlaysiz.
• Qimmat kalitni bir marta hisoblash (bezash → saralash → qaytarish) va Intl.Collator("uz") ning Chrome'dagi bo'shlig'ini bilasiz.
• vazifalar ga bir nechta kalitli, URL'da saqlanadigan saralash qo'shasiz.

Oldin bilishingiz kerak: Bo'lib-yech, sort va taqqoslash funksiyasi, toSorted va nusxa bilan o'zgartirish, Intl.Collator.

1. Nega bu kerak?

«Bahor» oshxonasidagi ekranda buyurtmalar ro'yxati turibdi. Jasur aka qoida qo'ydi: avval kutayotgan buyurtmalar, keyin tayyorlari. Bir holatdagilar orasida esa — kelgan tartibida: 12:05 dagi buyurtma 12:07 dagisidan oldin turishi shart, aks holda oshpaz kech kelgan mehmonni birinchi xizmat qiladi.

Sardor ro'yxatni holat bo'yicha saraladi. Kutayotganlar tepaga chiqdi — lekin ular orasidagi tartib saqlanib qoldimi? Javob saralash algoritmiga bog'liq. Ba'zi algoritmlar teng elementlarning tartibini saqlaydi, ba'zilari — aralashtirib yuboradi.

sort va taqqoslash funksiyasi darsida sort dan foydalanishni o'rgandik. Endi uning xususiyatlarini o'rganamiz: qanday saralash yaxshi, qanday saralash yomon va nega. Bu keyingi to'rt darsdagi algoritmlarni — bubble, insertion, merge, quick sort — solishtirish uchun o'lchov tizimi bo'ladi.

2. Saralashni baholashning to'rt o'lchovi

Bundan tashqari, algoritm elementlarni taqqoslab saralaydimi yoki ularning qiymatidan to'g'ridan-to'g'ri foydalanadimi — bu ham muhim. Bugungi darsning hammasi taqqoslab saralash haqida. Taqqoslamasdan saralash (masalan, sanab saralash) Chiziqli saralashlar darsida.

3. Barqarorlik

3.1 Ta'rif

Barqaror saralash (stable sort) — kalitlari teng elementlar natijada ham kelgan tartibida qoladi. Beqaror saralash (unstable sort) — bunday kafolat bermaydi: teng elementlar o'rin almashishi mumkin.

O'xshatish: navbatda turgan mehmonlarni "oldindan bron qilganlar oldinga" qoidasi bilan qayta tizsangiz, bron qilganlar orasida kim avval kelgan bo'lsa, o'sha oldinda turishi kerak. Barqaror saralash — adolatli navbat.

Beqarorlikni oddiy saralashlardan biri — tanlab saralash (selection sort) da ko'ramiz. U har qadamda qolgan qismdan eng kichigini topadi va uni joriy o'ringa almashtiradi. Uning ichini keyingi darsda batafsil o'rganamiz; hozir faqat almashtirishga qarang. T — tayyor, K — kutmoqda, raqam — buyurtma id:

Muammo — uzoq masofaga almashtirish. T1 birinchi qadamda 2-o'ringa "uchib ketdi" va T3 dan o'tib ketdi. Shu bitta sakrash T1 va T3 ning nisbiy tartibini buzdi.

3.2 JavaScript'da sort barqarormi?

Ha — ES2019 dan beri standart talab qiladi: Array.prototype.sort va toSorted barqaror. Undan oldin V8 kichik massivlarni barqaror, kattalarini (10 tadan ortiq) beqaror quick sort bilan saralardi — bir xil kod 10 ta va 11 ta elementda turlicha natija berardi. Chrome 70 (2018) dan beri V8 TimSort ni ishlatadi — u barqaror. Node 24 da ham shu. Chrome 149 dan boshlab V8 uning davomchisi PowerSort'ga o'tdi — u ham barqaror (Chiziqli saralashlar va JS sort ichidan darsida). Eski maqolalarda "sort barqaror emas" degan gapni uchratsangiz — bu o'sha davrdan qolgan.

Tekshirib ko'ring: ["T1", "K2", "T3"] ni toSorted bilan holat bo'yicha saralasak (kutayotganlar oldin), K2 dan keyin qaysi buyurtma turadi?

4. Ko'p kalitli saralash

4.1 Ikki usul

Endi Jasur aka ikkinchi qoida qo'shdi: bir holat ichida — yangilari oldin (id kattasi — kechroq kelgan). Bu ko'p kalitli saralash: birinchi kalit teng bo'lsa, ikkinchisiga qaraladi. Ikki yo'l bor:

const orders = [
  { id: 1, status: "tayyor" },
  { id: 2, status: "kutmoqda" },
  { id: 3, status: "tayyor" },
  { id: 4, status: "kutmoqda" },
  { id: 5, status: "kutmoqda" },
];
const rank = { kutmoqda: 0, tayyor: 1 }; // kutayotganlar oldin
const byStatus = (a, b) => rank[a.status] - rank[b.status];
const ids = (list) => list.map((o) => o.id).join(" ");

// 1) bitta kalit: barqaror — teng holatlilar kelgan tartibida
console.log(ids(orders.toSorted(byStatus)));

// 2) ikki kalit: holat, keyin yangilari (id kamayib) oldin
const newestFirst = (a, b) => b.id - a.id;
const byBoth = (a, b) => byStatus(a, b) || newestFirst(a, b);
console.log(ids(orders.toSorted(byBoth)));

// 3) xuddi shu natija, ikki o'tishda: avval ikkinchi kalit,
//    keyin birinchisi — barqarorlik ikkinchi tartibni saqlaydi
console.log(ids(orders.toSorted(newestFirst).toSorted(byStatus)));

Konsolda:

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

Birinchi usul — || zanjiri. Taqqoslash funksiyasi 0 qaytarsa ("teng"), || keyingi funksiyaga o'tadi. byStatus(a, b) || newestFirst(a, b): holatlar farqli bo'lsa — holat hal qiladi, teng bo'lsa — id. Kalitlar qancha bo'lsa, zanjir shuncha uzun.

Ikkinchi usul — barqarorlikka tayanish. Avval ikkinchi kalit bo'yicha saralaymiz, keyin birinchi bo'yicha. Ikkinchi saralash barqaror bo'lgani uchun, holati teng buyurtmalar birinchi saralashdagi (yangilari oldin) tartibda qoladi. Tartib teskari: eng muhim kalit — oxirgi saralash. Jadval ilovalarida "avval nom bo'yicha, keyin turkum bo'yicha bosish" aynan shunday ishlaydi.

Ikkinchi usul faqat barqaror saralashda ishlaydi. Beqaror algoritm bilan birinchi saralash natijasi yo'qolib ketardi.

4.2 Qimmat kalit: bezash → saralash → qaytarish

Vazifalarni alifbo bo'yicha saralashda kalit — normallashtirilgan matn: kichik harf, apostroflar bir xil, bo'shliqlarsiz chetlar. Uni taqqoslash funksiyasi ichida hisoblash tabiiy tuyuladi. Lekin taqqoslash funksiyasi necha marta chaqiriladi? Asosiy murakkablik sinflari darsida sanagan edik — n log₂ n atrofida. Har chaqiruvda ikkita normalize. Sanaymiz:

let calls = 0;
function normalize(text) {
  calls++;
  return text.toLowerCase().replace(/[‘’ʻʼ`]/g, "'").trim();
}
// Collator bir marta yaratiladi (12-qism qoidasi)
const alphabet = new Intl.Collator("uz", { numeric: true });

// 1 000 ta vazifa matni (urug'li generator — har safar bir xil)
const words = ["Non", "o'quv", "Oʻrik", "choy", "sabzi", "10-dars"];
let seed = 14;
const next = () => (seed = (seed * 16807) % 2147483647);
const tasks = Array.from({ length: 1000 }, () =>
  `${words[next() % 6]} ${words[next() % 6]} ${next() % 100}`);

calls = 0;
const slow = tasks.toSorted((a, b) =>
  alphabet.compare(normalize(a), normalize(b)));
console.log("taqqoslovchi ichida:", calls);

calls = 0;
const fast = tasks
  .map((text) => ({ text, key: normalize(text) })) // bezash
  .sort((a, b) => alphabet.compare(a.key, b.key)) // saralash
  .map(({ text }) => text); // qaytarish
console.log("bezash bilan:", calls);
console.log(slow.join() === fast.join());

Konsolda:

taqqoslovchi ichida: 17234
bezash bilan: 1000
true

1 000 ta matnga 17 234 marta normalize — har matn o'rtacha 17 marta qayta normallashtirildi! Ikkinchi usulda har matn bir marta:

1. Bezash (decorate) — har elementni { text, key } juftiga aylantirish: kalit oldindan hisoblanadi, n ta chaqiruv.
2. Saralash (sort) — tayyor kalitlar bo'yicha.
3. Qaytarish (undecorate) — juftlardan asl elementni olish.

Bu usul bezash-saralash-qaytarish (decorate-sort-undecorate) deb ataladi; Perl dasturchilari orasida "Schwartzian transform" nomi bilan mashhur. Natija bir xil (true), lekin kalit narxi O(n log n) marta emas, n marta to'lanadi. Oraliq .sort — map yangi massiv qaytargani uchun asl massivga tegmaydi.

Maslahat: Intl.Collator ni ham bir marta yarating — taqqoslash funksiyasi ichida new Intl.Collator(...) yoki localeCompare(b, "uz") har chaqiruvda til qoidalarini qaytadan tayyorlaydi (Intl.Collator darsidagi qoida).

4.3 Intl.Collator("uz"): Node va Chrome

O'zbekcha alifbo tartibi uchun Intl.Collator("uz"). Lekin u qayerda ishlayotganiga bog'liq. Bir xil kodni ikkala muhitda sinadik (Chrome 154 — puppeteer orqali, 2026-10-06):

const words = ["choy", "sabzi", "o'rik", "olma", "shakar",
  "g'isht", "zira"];
const alphabet = new Intl.Collator("uz");
console.log(alphabet.resolvedOptions().locale);
console.log(words.toSorted(alphabet.compare).join(", "));

Konsolda (Node 24):

uz
olma, sabzi, zira, o'rik, g'isht, shakar, choy

Chrome 154 da esa:

en-GB
choy, g'isht, o'rik, olma, sabzi, shakar, zira

Node'da o'zbek qoidalari bor: o', g', sh, ch — alifbo oxirida. Chrome'da o'zbek saralash qoidalari yo'q, u brauzer tiliga (bizda en-GB, boshqa kompyuterda en-US yoki ru) o'tadi va ingliz tartibida saralaydi. Bu xato emas — resolvedOptions().locale buni halol aytadi. Saytdagi «Ishga tushir» tugmasi kodni brauzeringizda bajaradi — natija ikkinchisiga o'xshaydi. Brauzerda haqiqiy o'zbek tartibi kerak bo'lsa — o'z taqqoslovchingizni yozasiz (3-mashq).

5. Joyida saralash va xotira

Joyida saralash (in-place sort) — elementlarni o'sha massivning ichida joyini almashtirib saralash, qo'shimcha massivsiz: O(1) (yoki rekursiya uchun O(log n)) qo'shimcha xotira (Massiv xotirada va joyida amallar). Oddiy saralashlar va quick sort — joyida; merge sort esa birlashtirish uchun O(n) yordamchi massiv oladi (Bo'lib-yech darsidagi merge).

JavaScript'da ikki xil API bor:

• arr.sort(cmp) — massivning o'zini o'zgartiradi va o'shani qaytaradi.
• arr.toSorted(cmp) — asl massivga tegmaydi, yangi massiv qaytaradi: O(n) qo'shimcha xotira.

Diqqat: "o'zini o'zgartiradi" va "O(1) xotira" — bir narsa emas. V8 dagi TimSort birlashtirish uchun vaqtincha n ÷ 2 gacha joy oladi. Ya'ni sort ham ichida O(n) xotira ishlatishi mumkin — faqat natijani asl massivga yozadi. Qaysi API ni tanlash xotira emas, ma'no masalasi: massiv boshqa joyda ham ishlatilsa (masalan, holat obyektida), toSorted xavfsiz (Immutability chuqur).

6. Quyi chegara: n log n dan tez bo'lmaydi

6.1 Qaror daraxti

Taqqoslab saralaydigan algoritm haqida faqat bitta narsani bilamiz: u elementlar haqida ma'lumotni faqat "a < b mi?" savoli orqali oladi. Har savolga javob — ha yoki yo'q. Savollar ketma-ketligini daraxt qilib chizish mumkin: har tugun — bitta solishtirish, ikki shoxi — ikki javob. Bu qaror daraxti (decision tree).

n ta turli element n! xil tartibda kelishi mumkin, va algoritm har birini to'g'ri saralashi uchun ularni bir-biridan farqlashi kerak. Demak, daraxtda kamida n! ta barg bo'lishi shart. Balandligi h bo'lgan ikkilik daraxtda ko'pi bilan 2ʰ barg bor. 2ʰ ≥ n! — demak, h ≥ log₂(n!). Daraxt balandligi — eng yomon holatdagi solishtirishlar soni.

log₂(n!) qancha? Matematiklar hisoblagan: taxminan n log₂ n − 1,44 n. Ya'ni har qanday taqqoslab saralash eng yomon holatda Ω(n log n) solishtirish qiladi. Ω (omega) — "bundan tez bo'lmaydi" degan belgi (Xotira murakkabligi darsida ko'rgan edik). Merge sort va TimSort shu chegarada ishlaydi — ulardan asimptotik tezroq taqqoslash algoritmi bo'lishi mumkin emas.

6.2 Tekshiramiz

toSorted tasodifiy sonlarda nechta solishtirish qilishini chegara bilan solishtiramiz:

function log2Factorial(n) {
  let sum = 0;
  // log₂(n!) = log₂ 2 + log₂ 3 + … + log₂ n
  for (let k = 2; k <= n; k++) sum += Math.log2(k);
  return Math.ceil(sum);
}

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

const random = makeRandom(2026);
for (const n of [10, 100, 1000, 10000]) {
  const nums = Array.from({ length: n }, random);
  let comparisons = 0;
  nums.toSorted((a, b) => {
    comparisons++;
    return a - b;
  });
  const bound = log2Factorial(n);
  console.log(`n=${n}: chegara ${bound}, toSorted ${comparisons}`);
}

Konsolda:

n=10: chegara 22, toSorted 22
n=100: chegara 525, toSorted 535
n=1000: chegara 8530, toSorted 8628
n=10000: chegara 118459, toSorted 119828

TimSort chegaradan atigi 1–2 % ko'proq solishtirish qildi — 10 ta elementda esa aynan chegarada. Bu urug'li tasodifiy kirish uchun; boshqa kirishda son biroz boshqacha bo'ladi, lekin chegaradan pastga hech qachon tushmaydi (eng yomon holat uchun).

Tekshirib ko'ring: 3 ta elementni saralash uchun eng yomon holatda kamida nechta solishtirish kerak? Ishora: 3! = 6 ta tartib.

7. Adaptiv saralash

Chegara eng yomon holat haqida. Kirish allaqachon deyarli tartibda bo'lsa-chi? Real hayotda bu ko'p uchraydi: kecha saralangan ro'yxatga bugun bir nechta yozuv qo'shildi; vaqt bo'yicha kelgan buyurtmalar deyarli tartibda. Adaptiv saralash (adaptive sort) — bunday kirishda tezroq ishlaydigan algoritm. TimSort adaptiv: u kirishdagi tayyor tartiblangan bo'laklarni (yugurishlar — runs) topadi va ularni qayta saralamaydi, faqat birlashtiradi.

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

const n = 10000;
const sorted = Array.from({ length: n }, (_, i) => i);
const reversed = sorted.toReversed();
const nearly = [...sorted];
for (let k = 0; k < 10; k++) {
  const i = (k * 997) % n; // 10 ta juftni almashtiramiz
  [nearly[i], nearly[i + 1]] = [nearly[i + 1], nearly[i]];
}
let seed = 2026;
const shuffled = sorted.map(
  () => (seed = (seed * 16807) % 2147483647),
);

console.log("saralangan:", countComparisons(sorted));
console.log("teskari:", countComparisons(reversed));
console.log("deyarli saralangan:", countComparisons(nearly));
console.log("aralash:", countComparisons(shuffled));

Konsolda:

saralangan: 9999
teskari: 9999
deyarli saralangan: 10471
aralash: 119947

Saralangan 10 000 ta sonda — 9 999 solishtirish: har qo'shni juft bir marta, bu O(n). Teskari tartibda ham 9 999: TimSort kamayuvchi yugurishni topib, uni shunchaki ag'daradi. 10 ta joyi almashgan ro'yxatda — 10 471. Aralash ro'yxatda esa 119 947 — o'n ikki baravar ko'p.

Vaqtni ham o'lchadik (benchmarking darsidagi usul: har n alohida jarayonda, isitish, 7 o'lchov medianasi):

Aralash kirishda n ikki baravar — vaqt 2,1 baravar (n log n). Saralangan kirishda — ikki baravar (n) va 20–25 baravar tez. Adaptivlik quyi chegarani buzmaydi: chegara eng yomon holat haqida, saralangan kirish esa eng yaxshi holat.

8. Chegaraviy holatlar

• Bo'sh va bitta elementli massiv. Saralangan hisoblanadi; taqqoslash funksiyasi umuman chaqirilmaydi.
• Hamma kalitlar teng. Barqaror saralash massivni o'zgartirmaydi. Beqaror saralash — o'zgartirishi mumkin.
• undefined va teshiklar. sort undefined qiymatlarni taqqoslash funksiyasini chaqirmasdan oxiriga qo'yadi (sort darsida).
• NaN qaytaradigan taqqoslash. a.price - b.price da narx yo'q bo'lsa — NaN. Natija tartibi kutilmagan bo'ladi, xato chiqmaydi. Kalitlarni oldindan tekshiring.
• Har xil yozilgan bir so'z. "O'rik", "oʻrik", "o‘rik" — apostroflar har xil. Normallashtirmasdan saralasangiz, bir so'z uch joyga tushadi.

9. Ko'p uchraydigan xatolar

9.1 Mantiqiy qiymat qaytarish

const prices = [35000, 5000, 28000, 30000];
console.log(prices.toSorted((a, b) => a > b)); // ❌ true/false
console.log(prices.toSorted((a, b) => a - b)); // ✅ son

Konsolda:

[ 35000, 5000, 28000, 30000 ]
[ 5000, 28000, 30000, 35000 ]

Taqqoslash funksiyasi son qaytarishi kerak: manfiy — a oldin, musbat — b oldin, 0 — teng. Mantiqiy true 1 ga, false 0 ga aylanadi. Shuning uchun "a kichik" holati hech qachon manfiy bermaydi, algoritm ko'p juftni "teng" deb o'ylaydi. Natija — saralanmagan massiv, xato xabarisiz.

9.2 Ikki o'tishli usulni beqaror saralash bilan

"Avval ikkinchi kalit, keyin birinchi" usulini o'zingiz yozgan beqaror saralash bilan ishlatsangiz, birinchi o'tish natijasi yo'qoladi. Qoida: ikki o'tishli usul — faqat barqaror saralash bilan; ishonch bo'lmasa — || zanjiri.

9.3 Kalitni taqqoslovchi ichida hisoblash

Yuqorida ko'rdik: 1 000 ta matnga 17 234 ta normalize. Kalit qimmat bo'lsa (matn normallash, sana parse qilish, regex) — bezash-saralash-qaytarish.

10. Mashqlar

1-mashq (oson): Barqarormi?

Quyidagi holatlarning qaysi birida natija saralashning barqarorligiga bog'liq?

1. Takrorsiz sonlarni o'sish tartibida saralash.
2. Talabalarni ball bo'yicha saralash (ballar takrorlanadi), ro'yxat oldin ism bo'yicha tartiblangan.
3. Buyurtmalarni id bo'yicha saralash.

2-mashq (o'rta): Menyuni uch kalit bilan saralash

Menyuni saralang: avval turkum bo'yicha (alifbo), turkum ichida qimmatlari oldin, narxi teng bo'lsa — nomi bo'yicha alifbo. Intl.Collator("uz") ni bir marta yarating.

const menu = [
  { name: "manti", category: "milliy", price: 30000 },
  { name: "ko'k choy", category: "ichimlik", price: 5000 },
  { name: "osh", category: "milliy", price: 35000 },
  { name: "kompot", category: "ichimlik", price: 7000 },
  { name: "lag'mon", category: "milliy", price: 28000 },
  { name: "chuchvara", category: "milliy", price: 30000 },
  { name: "ayron", category: "ichimlik", price: 5000 },
];
const alphabet = new Intl.Collator("uz");

const sorted = menu.toSorted(
  (a, b) =>
    alphabet.compare(a.category, b.category) || // 1) turkum
    b.price - a.price || // 2) qimmatlari oldin
    alphabet.compare(a.name, b.name), // 3) nomi
);
for (const dish of sorted) {
  console.log(dish.category, dish.price, dish.name);
}

ichimlik 7000 kompot
ichimlik 5000 ayron
ichimlik 5000 ko'k choy
milliy 35000 osh
milliy 30000 manti
milliy 30000 chuchvara
milliy 28000 lag'mon

3-mashq (qiyin): O'zbek alifbosi taqqoslovchisi

Chrome'da Intl.Collator("uz") o'zbek tartibini bermaydi. kurs/mashqlar/14/27-saralash/alifbo.test.mjs faylida compareUz(a, b) ni yozing — Intl siz, istalgan brauzerda bir xil ishlaydi. Alifbo tartibi: a b d e f g h i j k l m n o p q r s t u v x y z o' g' sh ch (c va w yo'q). Qoidalar: katta-kichik harf va apostrof turlari (', ‘, ’, ʻ) farq qilmaydi; so'zdagi tutuq belgisi (ma'no) harflardan oldin turadi; bir so'z boshqasining boshi bo'lsa, qisqasi oldin. Testlar (node:test): asosiy tartib, apostroflar, tutuq va prefiks, Node'dagi Intl.Collator("uz") bilan 15 so'zda bir xil natija.

// kurs/mashqlar/14/27-saralash/alifbo.test.mjs
import { test } from "node:test";
import assert from "node:assert/strict";

// O'zbek lotin alifbosi: lotin harflaridan keyin o', g', sh, ch
const ALPHABET = [
  ..."abdefghijklmnopqrstuvxyz", // c va w — o'zbek alifbosida yo'q
  "o'", "g'", "sh", "ch",
];
const RANK = new Map(ALPHABET.map((letter, i) => [letter, i]));

// So'z → harflar o'rinlari: "choy" → [ch, o, y]
function letterRanks(word) {
  const text = word.toLowerCase().replace(/[‘’ʻʼ`]/g, "'");
  const ranks = [];
  let i = 0;
  while (i < text.length) {
    const pair = text.slice(i, i + 2);
    if (RANK.has(pair)) {
      ranks.push(RANK.get(pair)); // ikki belgili harf
      i += 2;
    } else {
      const ch = text[i];
      // tutuq belgisi (ma'no) — harflardan oldin;
      // alifboda yo'q belgi — hammasidan keyin
      if (ch === "'") ranks.push(-1);
      else ranks.push(RANK.get(ch) ?? 100 + ch.codePointAt(0));
      i += 1;
    }
  }
  return ranks;
}

function compareUz(a, b) {
  const x = letterRanks(a);
  const y = letterRanks(b);
  const len = Math.min(x.length, y.length);
  for (let i = 0; i < len; i++) {
    if (x[i] !== y[i]) return x[i] - y[i];
  }
  return x.length - y.length; // qisqasi (prefiks) oldin
}

test("o', g', sh, ch — z dan keyin", () => {
  const words = ["choy", "sabzi", "o'rik", "olma", "shakar",
    "g'isht"];
  assert.deepEqual(words.toSorted(compareUz),
    ["olma", "sabzi", "o'rik", "g'isht", "shakar", "choy"]);
});

test("apostrof turlari va katta harf farq qilmaydi", () => {
  assert.equal(compareUz("Oʻrik", "o'rik"), 0);
  assert.equal(compareUz("O‘RIK", "o’rik"), 0);
});

test("tutuq belgisi va prefiks", () => {
  const words = ["mano", "ma'no", "mab", "ton", "tong", "tonv"];
  assert.deepEqual(words.toSorted(compareUz),
    ["ma'no", "mab", "mano", "ton", "tong", "tonv"]);
});

test("Node'dagi Intl.Collator(\"uz\") bilan bir xil", () => {
  const words = ["zira", "choy", "sut", "shirin", "g'oz", "gul",
    "o'q", "ota", "ng", "non", "cho'p", "sabzi", "ma'no",
    "yo'l", "xo'roz"];
  const collator = new Intl.Collator("uz");
  assert.deepEqual(words.toSorted(compareUz),
    words.toSorted(collator.compare));
});

✔ o', g', sh, ch — z dan keyin (1.4072ms)
✔ apostrof turlari va katta harf farq qilmaydi (0.2209ms)
✔ tutuq belgisi va prefiks (0.1349ms)
✔ Node'dagi Intl.Collator("uz") bilan bir xil (10.3189ms)
ℹ tests 4
ℹ suites 0
ℹ pass 4
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 94.9916

4-mashq: Vazifalar qadami — bir nechta kalitli saralash

vazifalar ga 14-qismning ikkinchi qadami. Hozir ro'yxat bitta tartibda: faollar tepada, bajarilganlar pastda, har guruh qo'shilish tartibida. Endi foydalanuvchi tartibni tanlaydi: «Qo'shilgan tartibda», «Avval yangilari», «Alifbo bo'yicha». Tanlov URL'da saqlanadi (?saralash=alifbo) — havolani yuborsangiz, do'stingiz ham shu tartibni ko'radi. Bu darsdagi to'rt g'oya birdaniga ishlatiladi: barqarorlik, || zanjiri, bezash-saralash-qaytarish va bir marta yaratilgan Intl.Collator.

Bajarilganlar har qanday tartibda pastda qoladi — bu birinchi kalit. Tanlangan tartib — ikkinchi kalit. Vazifada sana maydoni yo'q ({ id, matn, bajarildi }), shuning uchun "yangi" — id kattasi: id qo'shilish tartibida beriladi.

1. Branch:

git switch -c feature/saralash

2. Yangi fayl assets/js/saralash.js (// @ts-check bilan; JSDoc tur izohlari bu yerda qisqartirilgan, to'liq fayl — kanon repoda):

// @ts-check
// saralash.js — ko'rinadigan vazifalar tartibi:
// bir nechta kalit bilan
import { normalla } from "./qidiruv.js";

// URL ham, <select> ham shu ro'yxatga qaraydi
export const SARALASHLAR = Object.freeze([
  "standart",
  "yangi",
  "alifbo",
]);

const faollarOldin = (a, b) =>
  Number(a.bajarildi) - Number(b.bajarildi);
const yangilarOldin = (a, b) => b.id - a.id;
const eskilarOldin = (a, b) => a.id - b.id;

// Bir marta yaratiladi — har taqqoslashda emas. numeric: "2-dars"
// "10-dars" dan oldin. Chrome 154 da "uz" qoidalari yo'q: brauzer
// tiliga o'tadi (12-qism) — o', g', sh, ch alifbo oxirida emas
const alifbo = new Intl.Collator("uz", { numeric: true });

// Har saralash: avval faollar (oldingi xulq), keyin tanlangan kalit.
// Array.prototype.toSorted barqaror (stable): kalitlari teng
// vazifalar kelgan tartibida qoladi — "standart" shunga tayanadi.
export function tartibla(vazifalar, saralash) {
  if (saralash === "yangi") {
    // Bir nechta kalit: birinchisi 0 (teng) bo'lsa,
    // || keyingisiga o'tadi
    return vazifalar.toSorted(
      (a, b) => faollarOldin(a, b) || yangilarOldin(a, b),
    );
  }
  if (saralash === "alifbo") {
    // Kalit har vazifa uchun BIR marta (n ta normalla),
    // har taqqoslashda emas (~n log n ta):
    // bezash → saralash → qaytarish
    const bezalgan = vazifalar.map((vazifa) => ({
      vazifa,
      kalit: normalla(vazifa.matn),
    }));
    bezalgan.sort(
      (a, b) =>
        faollarOldin(a.vazifa, b.vazifa) ||
        alifbo.compare(a.kalit, b.kalit) ||
        eskilarOldin(a.vazifa, b.vazifa),
    );
    return bezalgan.map(({ vazifa }) => vazifa);
  }
  return vazifalar.toSorted(faollarOldin);
}

Uch tartibni darsdagi g'oyalar bilan solishtiring:

• standart — bitta kalit (faollarOldin). Faollar orasidagi qo'shilish tartibi barqarorlik tufayli saqlanadi — alohida kalit kerak emas.
• yangi — || zanjiri: holat, keyin id kamayib.
• alifbo — bezash-saralash-qaytarish: normalla (Matn algoritmlari qadamida yozilgan: kichik harf, apostroflar bitta) har vazifa uchun bir marta. Uchinchi kalit eskilarOldin: "O'rik" va "oʻrik" normallashgandan keyin teng — kichik id oldin, natija har safar bir xil. bezalgan.sort (toSorted emas) — bezalgan yangi massiv, uni o'zgartirish xavfsiz.
• Noma'lum qiymat (masalan, "constructor") — standart.

Kanon faylda uzun izohlar bitta qatorda; bu yerda ular telefon uchun bo'lindi, kodning o'zi aynan kanondagidek. Fayl jsconfig.json ning include ro'yxatiga qo'shiladi — npm run tip uni ham tekshirsin.

3. royxat.js — saralash endi saralash.js da. Ichki faollarOldin u yerga ko'chdi, korinadiganlar ikkinchi parametr oldi. U ixtiyoriy — eski chaqiruvlar o'zgarmaydi:

// Oldin
korinadiganlar(filtr) {
  return this.#vazifalar
    .filter((v) => VazifalarRoyxati.mosmi(v, filtr))
    .toSorted(faollarOldin);
}

// Keyin
korinadiganlar(filtr, saralash = "standart") {
  return tartibla(
    this.#vazifalar.filter((v) => VazifalarRoyxati.mosmi(v, filtr)),
    saralash,
  );
}

4. marshrut.js — saralash URL'da. Filtr uchun yozilgan kod umumiy yordamchilarga aylandi, saralash ham ulardan foydalanadi:

// URL'dagi qiymat — oq ro'yxatdan; yo'q yoki begona bo'lsa — standart
function parametrniOl(manzil, nomi, ruxsatlar, standart) {
  const qiymat = new URL(manzil).searchParams.get(nomi);
  return ruxsatlar.includes(qiymat) ? qiymat : standart;
}

export function saralashniOl(manzil = location.href) {
  return parametrniOl(manzil, "saralash", SARALASHLAR, "standart");
}

export function saralashniYoz(saralash) {
  parametrniYoz("saralash", saralash, "standart");
}

parametrniYoz filtrdagi eski kod: standart qiymat URL'ga yozilmaydi, URL o'zgarmasa — pushState qilinmaydi. filtrniOl/filtrniYoz endi shu ikki yordamchini chaqiradi — xulq bir xil, eski 8 ta test o'zgarishsiz o'tadi.

5. Holat, chizish va tinglovchi. holat.js: saralash: "standart" maydoni va korinadiganlar() uni uzatadi. index.html da filtr tugmalari ostiga tanlov:

<p id="saralash-qatori">
  <label for="saralash">Tartib</label>
  <select id="saralash">
    <option value="standart">Qo'shilgan tartibda</option>
    <option value="yangi">Avval yangilari</option>
    <option value="alifbo">Alifbo bo'yicha</option>
  </select>
</p>

asosiy.js — tanlov o'zgarsa:

function saralashniTanla(saralash) {
  if (!SARALASHLAR.includes(saralash)) {
    return; // <option> qiymatini DevTools'da o'zgartirish mumkin
  }
  holat.saralash = saralash;
  holat.tahrirId = null;
  saralashniYoz(saralash);
  render();
}

saralashTanlov.addEventListener("change", () => {
  elonQil("");
  saralashniTanla(saralashTanlov.value);
});

Oq ro'yxat tekshiruvi ikki joyda: URL'dan o'qishda va tanlovda. <option> qiymatini foydalanuvchi DevTools'da istalgan matnga o'zgartirishi mumkin — kod unga ishonmaydi. popstate (Orqaga/Oldinga) va ishga tushishda holat.saralash = saralashniOl(); render.js da saralashTanlov.value = holat.saralash — «Orqaga» bosilganda tanlov ham URL'ga ergashadi. CSS'da select tugmalar uslubida, sw.js da VERSIYA "v4-5" ga oshdi va saralash.js qobiq ro'yxatiga qo'shildi. index.html ga <link rel="modulepreload" href="assets/js/saralash.js">.

6. Testlar. Yangi fayl tekshiruv/saralash.test.js da 9 ta test:

• barqarorlik — kelish tartibi id tartibida emas, xuddi import qilingan fayldagidek;
• «yangi» va «alifbo» (Node'dagi ICU uz bilan: sabzi < o'rik < choy);
• raqamlar son kabi (2-dars < 10-dars), teng kalit — kichik id oldin;
• noma'lum saralash va asl massiv o'zgarmasligi, SARALASHLAR muzlatilgani;
• korinadiganlar(filtr, saralash) — 2 ta.

Yana marshrut.test.js ga +6 test: to'rt URL holati (shu jumladan ?saralash=__proto__ → standart), filtr parametri joyida qolishi va standart qiymat parametrni o'chirishi. Natija — 120/120; lint, format:check, tip — toza.

Barqarorlik testi — darsning yuragi (kanondagi birinchi test, qisqartirilgan):

const vazifalar = [
  v(5, "Choy damlash"),
  v(2, "olma olish", true),
  v(9, "O'rik"),
  v(1, "Shakar", true),
  v(7, "sabzi"),
];
// "standart: faollar oldin, qolgani kelgan tartibda (barqaror)"
assert.deepEqual(idlar(vazifalar, "standart"), [5, 9, 7, 2, 1]);

Faollar 5, 9, 7 — id tartibida emas, kelgan tartibida. Beqaror saralash bilan bu test tasodifan yiqilishi mumkin edi.

7. Brauzerda tekshirish (Live Server, kanon tekshiruvidan — 144/144 ning saralash qismi):

✅ saralash: standart — faollar oldin, qo'shilish tartibida: ["standart",[1,2,4,5,7,8,9,3,6]]
✅ saralash: yangi — faollar oldin, id kamayib; URL: [[9,8,7,5,4,2,1,6,3],"?saralash=yangi"]
   Chrome Intl.Collator("uz") → en-GB (uz qoidalari yo'q, 12-qism)
✅ saralash: alifbo — raqam son kabi, apostrof bir xil: [9,8,5,1,2,4,7,6,3]
✅ saralash: filtr bilan URL: "?saralash=alifbo&filtr=faol"
✅ saralash: Orqaga → yangi (tanlov ergashdi): ["yangi",9]
✅ saralash: qidiruv bilan birga: [9,8,2,4]
✅ saralash: DevTools'da o'zgartirilgan option — e'tiborsiz (URL va tartib o'zgarmadi): ["?saralash=%3Cscript%3E",true,10]

Uchinchi qatorga qarang: Chrome'da «Alifbo bo'yicha» o'zbekcha emas — ch "c" o'rnida turadi. Node testida (ICU uz) ch va sh oxirida. Apostrof turlari va katta-kichik harf esa ikkala muhitda bir xil — bu normalla ning xizmati. Kanon shu holatni qabul qilgan va TEXNIK-QARZ.md ga yozgan (19-band); o'z o'zbek taqqoslovchingiz (3-mashq) — uni yopishning yo'li.

O'zingiz ham sinang: «Alifbo bo'yicha» ni tanlang — manzil satrida ?saralash=alifbo paydo bo'ladi. Sahifani yangilang — tartib saqlangan. «Orqaga» bosing — tanlov ham, tartib ham qaytadi.

8. Commit va PR. Sarlavha 51 belgi, sababi tanaga:

git add assets/js/saralash.js assets/js/royxat.js \
  assets/js/marshrut.js assets/js/holat.js assets/js/render.js \
  assets/js/asosiy.js assets/css/vazifalar.css index.html sw.js \
  jsconfig.json tekshiruv/saralash.test.js tekshiruv/marshrut.test.js
git commit \
  -m "feat: saralash tanlovi — bir nechta kalit, URL'da" \
  -m "toSorted barqaror; alifbo — Intl.Collator(\"uz\"), kalit bir marta"
git push -u origin feature/saralash
gh pr create --fill
gh pr merge --merge

Diff: 12 fayl, +265 −29.

Murakkablik (kanon o'lchovi, Node, tartibla): «standart» — 1 000 vazifada 0,36 ms, 100 000 da 39 ms; «yangi» — 0,51 / 55 ms; «alifbo» — 11 ms / 1,5 s. Alifbo kalitsiz (taqqoslovchi ichida normalla) — 110 ms / 20,8 s: bezash 10–14 baravar tezlashtirdi. Brauzerda chizish bilan 1 000 vazifada tanlovni almashtirish 13–22 ms — asosiy vaqtni saralash emas, ro'yxatni qayta chizish oladi.

11. Real ishda

• Jadval va ro'yxatlar. Admin panellar, internet do'konlar, Excel'ga o'xshash jadvallar — "ustun sarlavhasini bosib saralash". Bir nechta ustun bo'yicha saralash barqarorlikka tayanadi.
• Server va ma'lumotlar bazasi. SQL'da ORDER BY status, created_at DESC — xuddi || zanjiri. Ma'lumotlar bazasi ORDER BY siz tartibni kafolatlamaydi — bu ham "barqarorlikka ishonmang" qoidasining bir ko'rinishi (SQL'ni 26-qismda o'rganamiz).
• Til va lokal. O'zbek, rus, turk tillarida alifbo tartibi ingliznikidan farq qiladi. Intl.Collator — to'g'ri yo'l, lekin brauzer qo'llashini tekshiring; ba'zan saralashni serverda qilish ishonchliroq.
• Intervyu. "Barqaror saralash nima, misol keltiring", "Nega taqqoslash saralashi n log n dan tez bo'lmaydi?", "Qaysi saralashlar joyida?" — algoritm intervyularining nazariy savollari.

Xulosa

• Saralash to'rt o'lchov bilan baholanadi: vaqt, qo'shimcha xotira (joyida yoki yo'q), barqarorlik, adaptivlik.
• Barqaror saralash teng kalitlilarning kelish tartibini saqlaydi; JavaScript'da sort/toSorted ES2019 dan barqaror, tanlab saralash — beqaror.
• Ko'p kalit: || zanjiri yoki "avval ikkinchi, keyin birinchi kalit" (faqat barqaror saralashda). Qimmat kalit — bezash → saralash → qaytarish: 17 234 o'rniga 1 000 normalize.
• Taqqoslash saralashi eng yomon holatda ≥ log₂(n!) ≈ n log₂ n solishtirish; toSorted chegaradan 1–2 % ko'p qildi.
• TimSort adaptiv: saralangan 10 000 sonda 9 999 solishtirish, 800 000 sonda ≈ 11 ms ga qarshi aralashda ≈ 258 ms.
• Intl.Collator("uz"): Node'da o'zbekcha, Chrome 154 da brauzer tili (en-GB) — kerak bo'lsa o'z taqqoslovchingiz.

Keyingi dars: Oddiy saralashlar: bubble, selection, insertion — uchta O(n²) saralashni ichidan yozamiz, invariantlarini ko'ramiz va insertion sort nega deyarli saralangan ma'lumotda juda yaxshi ekanini o'lchaymiz.

Manbalar

• ECMAScript 2019: Array.prototype.sort barqarorligi talabi — tc39.es/ecma262
• V8 blog: "Getting things sorted in V8" (2018) — TimSort'ga o'tish — v8.dev/blog/array-sort
• Thomas H. Cormen va boshq., "Introduction to Algorithms", 4-nashr, MIT Press, 2022 — 8-bob (taqqoslash saralashining quyi chegarasi).
• Tim Peters, "listsort.txt" — TimSort tavsifi (CPython manba kodi) — github.com/python/cpython