Bubble Sort

---

Vaqt murakkabligi nima ekani haqidagi umumiy tushuntirish uchun oldingi sahifaga qarang.

---

Bubble Sort’ning vaqt murakkabligi

Eng yomon holatda Bubble Sort algoritmi \(n\) ta qiymatli massivni \(n-1\) marta aylanib chiqadi.

Algoritm massivni birinchi marta aylanib chiqqanda har bir qiymat keyingisi bilan taqqoslanadi va chapdagi qiymat o‘ngdagisidan katta bo‘lsa, qiymatlarning o‘rni almashtiriladi. Bu eng katta qiymat pufakchadek yuqoriga suzib chiqishini va saralash tugaguncha massivning saralanmagan qismi tobora qisqarib borishini anglatadi. Demak, algoritm qiymatlarni taqqoslab va o‘rnini almashtirib massivni aylanib chiqqanda o‘rtacha \(\frac{n}{2}\) ta element ko‘rib chiqiladi.

Bubble Sort algoritmi \(n\) ta qiymat ustida bajaradigan amallar sonini hisoblashni boshlashimiz mumkin:

\[Amallar = (n-1)\cdot \frac{n}{2} = \frac{n^2}{2} - \frac{n}{2} \]

Algoritmlarning vaqt murakkabligini ko‘rib chiqayotganda juda katta ma’lumotlar to‘plamlariga qaraymiz, ya’ni \(n\) juda katta son. Juda katta \(n\) uchun esa \(\frac{n^2}{2}\) hadi \(\frac{n}{2}\) hadidan ancha katta bo‘ladi — shunchalik kattaki, ikkinchi had \(\frac{n}{2}\) ni shunchaki olib tashlab, taqribiy hisoblashimiz mumkin.

\[Amallar = \frac{n^2}{2} - \frac{n}{2} \approx \frac{n^2}{2} = \frac{1}{2} \cdot n^2 \]

Bu yerdagidek Big O notatsiyasi yordamida vaqt murakkabligini ko‘rib chiqayotganda koeffitsiyentlar e’tiborga olinmaydi, shuning uchun \(\frac{1}{2}\) koeffitsiyenti tashlab yuboriladi. Bu Bubble Sort algoritmining bajarilish vaqtini Big O notatsiyasidan foydalanib, vaqt murakkabligi orqali quyidagicha tavsiflash mumkinligini anglatadi:

\[ O( \frac{1}{2} \cdot n^2) = \underline{\underline{O(n^2)}} \]

Bubble Sort vaqt murakkabligini tasvirlovchi grafik esa quyidagicha ko‘rinadi:

Ko‘rib turganingizdek, massiv hajmi oshirilganda bajarilish vaqti juda tez ortadi.

Yaxshiyamki, bundan tezroq saralash algoritmlari ham bor, masalan, Quicksort.

---

Bubble Sort simulyatsiyasi

Massivdagi qiymatlar sonini tanlang va Bubble Sort \(n\) ta elementli massiv uchun bajaradigan amallar soni qanday qilib \(O(n^2)\) bo‘lishini ko‘rish uchun ushbu simulyatsiyani ishga tushiring:

Yuqoridagi qizil chiziq yuqori chegara vaqt murakkabligi \(O(n^2)\) ni ifodalaydi, bu holatdagi haqiqiy funksiya esa \(1.05 \cdot n^2\).

Agar qiymatlar soni \(n\) katta bo‘lganda \(C \cdot g(n)>f(n)\) bo‘ladigan musbat \(C\) konstanta mavjud bo‘lsa, \(f(n)\) funksiya \(O(g(n))\) bo‘ladi, deyiladi.

Bu holatda \(f(n)\) — Bubble Sort bajaradigan amallar soni, \(g(n)=n^2\) va \(C=1.05\).

Big O notatsiyasi va vaqt murakkabligi haqida ushbu sahifada batafsilroq o‘qing.

---

---