Insertion Sort

---

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

---

Insertion Sort’ning vaqt murakkabligi

Insertion Sort uchun eng yomon holat — massiv allaqachon saralangan, ammo eng katta qiymatlar boshida turgan bo‘lishi. Buning sababi shundaki, bunday holatda har bir yangi qiymat massivning butun saralangan qismi bo‘ylab "o‘tib chiqishi" kerak.

Insertion Sort algoritmi dastlabki elementlar uchun bajaradigan amallar quyidagilar:

• 1-qiymat allaqachon to‘g‘ri joyda turibdi.
• 2-qiymat taqqoslanishi va 1-qiymatdan o‘tkazib ko‘chirilishi kerak.
• 3-qiymat taqqoslanishi va ikkita qiymatdan o‘tkazib ko‘chirilishi kerak.
• 3-qiymat taqqoslanishi va uchta qiymatdan o‘tkazib ko‘chirilishi kerak.
• Va hokazo.

Agar shu qonuniyatni davom ettirsak, \(n\) ta qiymat uchun amallarning umumiy sonini olamiz:

\[1+2+3+...+(n-1)\]

Bu matematikada yaxshi ma’lum bo‘lgan qator bo‘lib, uni quyidagicha yozish mumkin:

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

Juda katta \(n\) uchun \(\frac{n^2}{2}\) hadi ustunlik qiladi, shuning uchun ikkinchi had \(\frac{n}{2}\) ni olib tashlab soddalashtirishimiz mumkin.

Big O notatsiyasidan foydalanib, Insertion Sort algoritmi uchun quyidagi vaqt murakkabligini olamiz:

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

Vaqt murakkabligini quyidagicha ko‘rsatish mumkin:

Ko‘rib turganingizdek, qiymatlar soni \(n\) oshirilganda Insertion Sort sarflaydigan vaqt tez ortadi.

---

Insertion Sort simulyatsiyasi

Nazariy vaqt murakkabligi \(O(n^2)\) (qizil chiziq) haqiqiy Insertion Sort bajarilishlaridagi amallar soni bilan qanday solishtirilishini ko‘rish uchun quyidagi simulyatsiyadan foydalaning.

Insertion Sort uchun eng yaxshi, o‘rtacha va eng yomon holatlar o‘rtasida katta farq bor. Buni yuqoridagi turli simulyatsiyalarni ishga tushirib ko‘rishingiz mumkin.

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

Esda tuting: agar \(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)\) — Insertion Sort bajaradigan amallar soni, \(g(n)=n^2\) va \(C=1.07\).

---

---