3.9-bob: Saralash algoritmlari (bubble, selection, insertion, merge, quick)

3-QISM — Algoritm va ma'lumotlar tuzilmasi · 9-mavzu

1. Kirish va motivatsiya

Ma'lumotlar tuzilmalarini (3.2–3.8) bildik; endi klassik algoritmlarga o'tamiz. Saralash (sorting) — eng fundamental algoritm masalasi: tartibsiz ma'lumotni tartiblangan qilish. Real loyihada arr.sort() 2.7-bob ishlatasiz — lekin uning ichida nima borligini, nega ba'zi saralash O(n²), ba'zilari O(n log n) ekanligini bilish — har bir dasturchi uchun zarur.

Bu bob — algoritmik fikrlashning 0.6-bob eng yaxshi mashqgohi. Bir muammoning (saralash) bir necha xil yechimini ko'rib, ularning Big-O 3.1-bob farqini, savdolarini (vaqt vs xotira, barqarorlik) tushunamiz. Bu — intervyularning klassikasi.

O'xshatish: qo'lingizdagi o'yin kartalarini tartiblashni tasvur qiling. Kimdir har juftni almashtirib boradi (bubble), kimdir eng kichigini topib oldinga qo'yadi (selection), kimdir har kartani o'z joyiga suqib qo'yadi (insertion), kimdir kartalarni ikkiga bo'lib, alohida tartiblab, keyin birlashtiradi (merge). Hammasi tartiblaydi — lekin tezligi turlicha.

Nega muhim?

• sort() ichida nima borligini bilish (O(n log n) — odatda quick/merge variant).
• Big-O 3.1-bob, divide-and-conquer 3.11-bob, barqarorlik tushunchalari.
• Intervyu klassikasi; algoritmik fikrlashning eng yaxshi mashqi.

2. Nazariya — chuqur tushuntirish

2.1. Saralash nima va asosiy tushunchalar

Saralash — elementlarni ma'lum tartibda (odatda o'sish/kamayish) joylashtirish. Saralash algoritmlarini baholash mezonlari:

• Vaqt murakkabligi (Big-O — 3.1): O(n²) yoki O(n log n).
• Xotira (in-place mi?): qo'shimcha xotira O(1) (in-place) yoki O(n).
• Barqarorlik (stable): teng elementlarning dastlabki tartibi saqlanadimi? (muhim — ko'p maydonli saralashda).

2.2. Bubble sort — O(n²)

Bubble sort — qo'shni juftlarni taqqoslab, noto'g'ri tartibda bo'lsa almashtiradi; har o'tishda eng katta element "pufakcha kabi" oxiriga "ko'tariladi":

  [5, 2, 8, 1]    2,5 to'g'ri; 5,8 to'g'ri; 8,1 almash  [2,5,1,8]
  Keyingi o'tish: [2,1,5,8]  [1,2,5,8]

function bubbleSort(arr) {
  const a = [...arr];                     // nusxa (immutable — 2.7)
  for (let i = 0; i < a.length - 1; i++) {
    let almashdi = false;
    for (let j = 0; j < a.length - 1 - i; j++) {   // ichma-ich (O(n²) — 3.1)
      if (a[j] > a[j + 1]) {
        [a[j], a[j + 1]] = [a[j + 1], a[j]];  // almash (2.8)
        almashdi = true;
      }
    }
    if (!almashdi) break;                  // optimallashtirish: tartiblangan bo'lsa to'xta
  }
  return a;
}
// O(n²) — eng yomon va o'rtacha; O(n) — eng yaxshi (allaqachon tartibli)

Bubble sort — o'rgatish uchun, real ishda emas (sekin). Lekin tushunish oson.

2.3. Selection sort — O(n²)

Selection sort — har o'tishda eng kichik elementni topib, boshiga qo'yadi:

function selectionSort(arr) {
  const a = [...arr];
  for (let i = 0; i < a.length - 1; i++) {
    let minIdx = i;
    for (let j = i + 1; j < a.length; j++)   // qolganidan eng kichik (O(n²))
      if (a[j] < a[minIdx]) minIdx = j;
    if (minIdx !== i) [a[i], a[minIdx]] = [a[minIdx], a[i]];  // boshiga
  }
  return a;
}
// O(n²) doim (hatto tartiblangan bo'lsa ham); kam almashtirish

2.4. Insertion sort — O(n²), lekin kichik/qisman tartibli uchun yaxshi

Insertion sort — har elementni oldingi tartiblangan qismga to'g'ri joyiga "suqib" qo'yadi (kartalarni qo'lda tartiblagandek):

function insertionSort(arr) {
  const a = [...arr];
  for (let i = 1; i < a.length; i++) {
    const joriy = a[i];
    let j = i - 1;
    while (j >= 0 && a[j] > joriy) {   // joriy'dan kattalarni o'ngga sur
      a[j + 1] = a[j];
      j--;
    }
    a[j + 1] = joriy;                   // joriyni to'g'ri joyga
  }
  return a;
}
// O(n²) o'rtacha, lekin O(n) qisman tartibli; kichik massivlar uchun TEZ

Insertion sort — kichik (n < ~10) yoki deyarli tartiblangan massivlar uchun samarali. Shuning uchun ko'p kutubxona katta massivni quick/merge bilan, kichik bo'laklarni insertion bilan saralaydi (gibrid).

2.5. Merge sort — O(n log n), barqaror

Merge sort — divide and conquer (bo'l va hukmronlik qil — 3.11): massivni ikkiga bo'l, har yarmini sarala (rekursiv), keyin birlashtir:

  [5,2,8,1,9,3]
    bo'l  [5,2,8]  [1,9,3]
    bo'l  [5][2,8] [1][9,3]   ... (bittagacha)
    birlashtir (saralangan): [2,5,8] [1,3,9]
    birlashtir: [1,2,3,5,8,9]

function mergeSort(arr) {
  if (arr.length <= 1) return arr;        // base case (3.11)
  const orta = Math.floor(arr.length / 2);
  const chap = mergeSort(arr.slice(0, orta));    // rekursiv (3.11)
  const ong = mergeSort(arr.slice(orta));
  return merge(chap, ong);
}
function merge(a, b) {                      // ikki saralangan'ni birlashtir (3.2)
  const natija = [];
  let i = 0, j = 0;
  while (i < a.length && j < b.length)     // ikki ko'rsatkich (3.2)
    natija.push(a[i] <= b[j] ? a[i++] : b[j++]);
  return [...natija, ...a.slice(i), ...b.slice(j)];   // qolganini ula
}
// O(n log n) DOIM (kafolatlangan); O(n) xotira; BARQAROR (stable)

Merge sort — kafolatlangan O(n log n), barqaror, lekin O(n) qo'shimcha xotira. Tashqi saralash (katta fayllar), bog'langan ro'yxat 3.3-bob uchun yaxshi.

2.6. Quick sort — o'rtacha O(n log n)

Quick sort — pivot (tayanch element) tanlanadi; massiv pivot'dan kichik va katta qismlarga ajratiladi (partition), keyin har qism rekursiv saralanadi:

  [5,2,8,1,9,3]  pivot = 3
  kichik: [2,1]   pivot: [3]   katta: [5,8,9]
  har qismni rekursiv quick sort  birlashtir

function quickSort(arr) {
  if (arr.length <= 1) return arr;         // base case (3.11)
  const pivot = arr[arr.length - 1];        // oxirgini pivot
  const kichik = [], katta = [];
  for (let i = 0; i < arr.length - 1; i++)  // partition (3.2)
    (arr[i] < pivot ? kichik : katta).push(arr[i]);
  return [...quickSort(kichik), pivot, ...quickSort(katta)];  // rekursiv (3.11)
}
// O(n log n) o'rtacha; O(n²) worst (yomon pivot — saralangan massiv);
// O(log n) xotira (in-place variant); odatda eng tez amalda

Quick sort — amalda ko'pincha eng tez (yaxshi cache, kam doimiy koeffitsient). Lekin worst O(n²) (yomon pivot). Yechim: tasodifiy yoki "median-of-three" pivot. Ko'p tilning sort()i quick sort varianti (yoki Timsort — merge+insertion gibrid).

2.7. Taqqoslash jadvali

Yuqoridagilarning hammasi — taqqoslovga asoslangan (comparison) saralash: ular elementlarni faqat bir-biriga taqqoslab (<, >) tartiblaydi. Bunday algoritm uchun nazariy chegara O(n log n) — undan tez bo'lolmaydi (isbotlangan: n element n! xil tartibga ega, har taqqoslov javobni ikkiga bo'ladi kamida log₂(n!) ≈ n log n taqqoslov kerak).

Taqqoslovsiz (non-comparison) saralash elementlarni taqqoslamaydi — ularning qiymati/raqamini kalit sifatida ishlatadi va shu sabab O(n log n) chegarasidan tez (O(n) yoki O(n+k)) bo'la oladi. Lekin faqat maxsus turdagi ma'lumotga (butun son, qisqa qator) ishlaydi:

• Counting sort — O(n + k), bu yerda k — qiymatlar diapazoni. Har qiymat nechta uchraganini sanab, tartibni tiklaydi. Diapazon kichik bo'lganda (masalan, 0–100 oraliq baholar) juda tez. Kamchiligi: k katta bo'lsa (masalan, ixtiyoriy 32-bit son), xotira behuda.
• Radix sort — O(d·(n + k)), raqamlarni xona-xona (birlik, o'nlik, ...) counting sort bilan tartiblaydi; d — xonalar soni. Katta hajmli butun sonlar/qatorlar uchun amalda tez.

Xulosa: O(n log n) — faqat comparison saralash uchun chegara. Diapazoni cheklangan butun sonlarni saralayotgan bo'lsangiz, counting/radix bilan O(n) ga erishishingiz mumkin. Lekin umumiy maqsadli holatda (ixtiyoriy obyekt, komparator) comparison saralash — merge/quick/Timsort — standart tanlov.

2.8. JS'ning sort() (2.7 takror)

JS Array.prototype.sort — odatda Timsort (merge + insertion gibrid) yoki quick variant; O(n log n), barqaror (zamonaviy):

arr.sort((a, b) => a - b);   // sonlar o'sish (komparator SHART — 2.7!)
arr.sort((a, b) => b - a);   // kamayish
arr.sort();                  //  matn sifatida (10 < 2!) — 2.7 tuzog'i

Real ishda sort() ishlating — u optimallashgan. O'z saralashingiz — faqat o'rganish yoki maxsus holat uchun.

3. Sintaksis — tez ma'lumotnoma

O(n²):       bubble, selection, insertion (kichik/o'rgatish)
O(n log n):  merge (barqaror, O(n) xotira), quick (tez, worst O(n²)), heap 3.8-bob
DIVIDE&CONQUER: merge/quick — bo'l, sarala, birlashtir 3.11-bob
BARQAROR:    teng elementlar tartibi saqlanadi (bubble/insertion/merge)
JS:          arr.sort((a,b) => a-b)  — komparator SHART (2.7)

4. Batafsil kod namunalari

(2-bo'limda har algoritm to'liq kodi berildi.) Qo'shimcha amaliy misollar:

Misol 1 — Obyektlarni bir necha maydon bo'yicha saralash (2.7)

const odamlar = [
  { ism: "Ali", yosh: 25 }, { ism: "Vali", yosh: 20 }, { ism: "Guli", yosh: 25 },
];
// Yosh bo'yicha, teng bo'lsa ism bo'yicha (barqaror saralash muhim)
odamlar.sort((a, b) => a.yosh - b.yosh || a.ism.localeCompare(b.ism));
// [Vali 20, Ali 25, Guli 25]  (|| — birinchi teng bo'lsa ikkinchi mezon)

Misol 2 — Saralashlarni vaqt bo'yicha solishtirish (3.1)

function olcha(fn, arr) {
  const a = [...arr];
  console.time(fn.name);
  fn(a);
  console.timeEnd(fn.name);
}
const katta = Array.from({ length: 10000 }, () => Math.floor(Math.random() * 10000));
olcha(bubbleSort, katta);   // sekin (O(n²))
olcha(mergeSort, katta);    // ancha tez (O(n log n))
// n=10000: bubble ~yuz ms, merge ~bir necha ms — Big-O farqi ko'rinadi

Misol 3 — Barqarorlik (stable) namoyishi (2.1)

// Barqaror: teng elementlarning dastlabki tartibi saqlanadi
const data = [
  { id: 1, ball: 90 }, { id: 2, ball: 85 }, { id: 3, ball: 90 },
];
// merge sort (barqaror): ball=90 lar id tartibida qoladi (1, keyin 3)
// selection sort (barqaror emas): id tartibi buzilishi mumkin

Misol 4 — Quick sort pivot muammosi (2.6)

//  Allaqachon tartiblangan massivda oxirgi pivot  O(n²)!
quickSort([1, 2, 3, 4, 5]);   // har partition bir tomonlama (worst case)

//  Tasodifiy pivot (worst case ehtimolini kamaytiradi)
function quickSortYaxshi(arr) {
  if (arr.length <= 1) return arr;
  const pi = Math.floor(Math.random() * arr.length);   // tasodifiy (3.1)
  const pivot = arr[pi];
  const kichik = arr.filter((x, i) => i !== pi && x < pivot);
  const katta = arr.filter((x, i) => i !== pi && x >= pivot);
  return [...quickSortYaxshi(kichik), pivot, ...quickSortYaxshi(katta)];
}

5. To'g'ri va noto'g'ri holatlar

1) sort() komparatorsiz (sonlar)

//  matn sifatida saralaydi (2.7)
[10, 2, 1].sort();        // [1, 10, 2]

//  komparator
[10, 2, 1].sort((a, b) => a - b);   // [1, 2, 10]

2) sort() asl massivni o'zgartiradi (2.7)

//  sort in-place — asl o'zgaradi (2.7: mutating)
const tartibli = arr.sort((a, b) => a - b);   // arr ham o'zgardi!

//  nusxa
const tartibli = [...arr].sort((a, b) => a - b);

3) O'z O(n²) saralashini katta ma'lumotda

 1 million element uchun bubble sort — muzlaydi (3.1)
 sort() (O(n log n)) yoki merge/quick

4) Barqarorlik kerak bo'lganda noto'g'ri algoritm

 ko'p maydonli saralashda barqaror bo'lmagan algoritm — tartib buziladi
 merge sort yoki JS sort() (barqaror — 2.8)

6. Keng tarqalgan xatolar va yechimlari

Xato 1 — sort() raqamlarni noto'g'ri tartiblaydi

Sababi: komparatorsiz — matn sifatida (2.7, 2.8). Yechimi: (a, b) => a - b.

Xato 2 — Quick sort katta massivda Maximum call stack

Sababi: yomon pivot chuqur rekursiya (2.6, 0.1). Yechimi: tasodifiy/median pivot; tail recursion yoki iterativ.

Xato 3 — Merge sort sekin/ko'p xotira

Sababi: har bo'linishda slice yangi massiv (O(n) xotira — 2.5). Yechimi: odatda maqbul; juda katta bo'lsa in-place variant (murakkab).

Xato 4 — Asl massiv kutilmaganda o'zgardi

Sababi: sort mutating 2.7-bob. Yechimi: [...arr].sort().

Xato 5 — O'z saralashi notog'ri (off-by-one/chegara)

Sababi: indeks chegarasi xato (0.6, 3.2). Yechimi: kichik misolda qo'lda yuring; chegaralarni tekshiring.

7. Integratsiya — bu mavzu stack'ning qayerida uchraydi

• Big-O 3.1-bob: saralash — O(n²) vs O(n log n) farqining eng yaxshi misoli.
• Rekursiya/divide-conquer 3.11-bob: merge/quick.
• Heap 3.8-bob: heap sort; priority.
• BST 3.6-bob: in-order = saralash.
• Array sort 2.7-bob: kunlik ishda sort().
• DB 6.10-bob: ORDER BY — DB ichida saralash; indeks.
• Qidiruv 3.10-bob: binary search saralangan massivni talab qiladi.

8. Eng yaxshi amaliyotlar (best practices)

• Real ishda sort() ishlating (optimallashgan); o'z saralashingiz — o'rganish/maxsus holat 2.8-bob.
• sort()ga komparator (sonlar uchun a - b) va nusxa ([...arr]) 2.7-bob.
• Algoritm tanlovi: katta — O(n log n) (merge/quick); kichik/qisman tartibli — insertion 2.4-bob.
• Barqarorlik kerak bo'lsa — merge yoki JS sort 2.8-bob.
• Quick sort'da yaxshi pivot (tasodifiy/median) — worst O(n²) dan saqlaydi 2.6-bob.
• Vaqt vs xotira: merge (O(n) xotira) vs quick (O(log n)) vs heap (O(1)) 2.7-bob.
• Saralashni tushunib ishlating — Big-O, barqarorlik, in-place ni biling.

9. Amaliy loyiha: "Saralash Algoritmlari Laboratoriyasi"

Saralash algoritmlarini qurib, vizual va o'lchovli solishtirish.

Maqsad

Beshta saralash algoritmini yozib, ularning Big-O, barqarorlik va tezligini amalda solishtirish; divide-and-conquer'ni tushunish.

Talablar (requirements)

1. Beshta algoritm: bubble, selection, insertion, merge, quick — har biri (2.2–2.6). Hech biri asl massivni o'zgartirmasin (nusxa — 2.7).
2. To'g'rilik testi: har birini bir xil massivda sinab, natija JS sort() bilan mos kelishini tekshiring.
3. Vaqt o'lchovi: turli n (100, 1000, 10000) da har birini o'lchab, jadval chiqaring (Misol 2, 3.1).
4. Tahlil: "n 10x oshganda vaqt necha barobar?" — O(n²) (100x) vs O(n log n) (10x) ni isbotlang 3.1-bob.
5. Barqarorlik testi: obyekt massivida teng elementlar tartibi saqlanishini tekshiring (Misol 3).
6. Maxsus holatlar: allaqachon tartiblangan, teskari tartiblangan, hammasi teng — har algoritm qanday ishlaydi (quick worst case — 2.6).
7. Komparator: saralashlarni (a, b) komparator qabul qiladigan qiling (o'sish/kamayish/maydon — Misol 1).
8. (Bonus) Tasodifiy pivot'li quick sort (Misol 4).

Maslahatlar (hint)

• Har algoritmni [...arr] nusxasi ustida (immutable — 2.7).
• Merge/quick — rekursiv (base case length <= 1 — 3.11).
• Vaqt: console.time/timeEnd (3.1, Misol 2).
• O(n²) ni 100000+ da ishlatma (muzlaydi).
• Barqarorlik: {id, ball} bilan teng ball'lar id tartibini saqlaydimi tekshiring.
• Komparator default (a, b) => a - b.

"Tayyor" mezonlari (acceptance criteria)

• Beshta algoritm to'g'ri saralaydi (sort() bilan mos).
• Hech biri asl massivni o'zgartirmaydi.
• Vaqt jadvali turli n uchun; O(n²) vs O(n log n) farqi ko'rinadi.
• "10x necha barobar" tahlili Big-O ga mos.
• Barqarorlik testi (merge stable, selection emas) ko'rsatilgan.
• Maxsus holatlar (tartibli/teskari/teng) sinalgan.
• Komparator bilan o'sish/kamayish/maydon ishlaydi.

Yechim kodi ataylab berilmagan — bu loyihani o'zingiz yozib ko'ring.

10. Xulosa va keyingi bobga ko'prik

Bu bobda klassik saralash algoritmlarini o'rgandik:

• O(n²): bubble (qo'shni almashtirish), selection (eng kichikni tanlash), insertion (suqib qo'yish — kichik/qisman tartibli uchun yaxshi).
• O(n log n): merge (divide-and-conquer, barqaror, O(n) xotira), quick (pivot bo'lib, amalda tez, worst O(n²)), heap 3.8-bob.
• Baholash: vaqt (Big-O), xotira (in-place), barqarorlik (teng tartib saqlanadi).
• JS sort() — Timsort/quick variant, O(n log n), barqaror; komparator + nusxa bilan ishlating.

Keyingi bob — 3.10-bob: Qidiruv algoritmlari (linear, binary). Saralashni bildik; endi qidiruvni — linear (O(n)) va binary (O(log n), saralangan massivda) — chuqur o'rganamiz. Binary search 3.1 va 3.6 da ko'rdik; endi uning variantlari va qo'llanishlarini to'liq ochamiz.

Foydalanilgan rasmiy/ishonchli manbalar

• bigocheatsheet.com — sorting algoritmlari murakkabligi (vaqt/xotira/barqarorlik)
• Universal CS — comparison sorts, divide-and-conquer, stability
• MDN Web Docs — Array.prototype.sort (komparator, Timsort)