Merge Sort

---

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

---

Merge Sort’ning vaqt murakkabligi

Merge Sort algoritmi massivni tobora kichikroq bo‘laklarga ajratadi.

Qism massivlar eng kichik qiymatlar birinchi keladigan qilib qayta birlashtirilganda massiv saralangan holga keladi.

Saralanishi kerak bo‘lgan massivda \(n\) ta qiymat bor va vaqt murakkabligini algoritmga kerak bo‘ladigan amallar sonini ko‘rib chiqishdan boshlab topishimiz mumkin.

Merge Sort bajaradigan asosiy amallar — bo‘lish, so‘ngra elementlarni taqqoslab birlashtirish.

Massivni boshidan to qism massivlar faqat bitta qiymatdan iborat bo‘lguncha bo‘lish uchun Merge Sort jami \(n-1\) ta bo‘lish amalini bajaradi. 16 ta qiymatli massivni tasavvur qiling. U bir marta uzunligi 8 bo‘lgan qism massivlarga bo‘linadi, so‘ngra qayta-qayta bo‘linadi va qism massivlar hajmi 4, 2 va nihoyat 1 gacha kamayadi. 16 ta elementli massiv uchun bo‘lishlar soni \(1+2+4+8=15\) ga teng.

Quyidagi rasmda 16 ta sondan iborat massiv uchun 15 ta bo‘lish kerakligi ko‘rsatilgan.

Birlashtirishlar soni ham aslida \(n-1\) ga, ya’ni bo‘lishlar soniga teng, chunki massivni qayta yig‘ish uchun har bir bo‘lishga bitta birlashtirish kerak. Har bir birlashtirishda esa birlashtirilgan natija saralangan bo‘lishi uchun qism massivlardagi qiymatlar o‘zaro taqqoslanadi.

Ikki qism massivni birlashtirishda eng ko‘p taqqoslashni keltirib chiqaradigan eng yomon holat — qism massivlarning bir xil kattalikda bo‘lishi. [1,4,6,9] va [2,3,7,8] ni birlashtirishni ko‘rib chiqaylik. Bu holatda quyidagi taqqoslashlar kerak bo‘ladi:

1. 1 va 2 taqqoslanadi, natija: [1]
2. 4 va 2 taqqoslanadi, natija: [1,2]
3. 4 va 3 taqqoslanadi, natija: [1,2,3]
4. 4 va 7 taqqoslanadi, natija: [1,2,3,4]
5. 6 va 7 taqqoslanadi, natija: [1,2,3,4,6]
6. 9 va 7 taqqoslanadi, natija: [1,2,3,4,6,7]
7. 9 va 8 taqqoslanadi, natija: [1,2,3,4,6,7,8]

Birlashtirish oxirida bitta massivda faqat 9 qiymati qoladi, boshqa massiv esa bo‘sh, shuning uchun oxirgi qiymatni qo‘yish uchun taqqoslash kerak emas va natijaviy birlashtirilgan massiv [1,2,3,4,6,7,8,9] bo‘ladi. Ko‘rib turibmizki, 8 ta qiymatni (boshlang‘ich qism massivlarning har birida 4 tadan qiymat) birlashtirish uchun 7 ta taqqoslash kerak. Umuman olganda, eng yomon holatda \(n\) ta qiymatdan iborat birlashtirilgan massivni olish uchun \(n-1\) ta taqqoslash kerak bo‘ladi.

Soddalik uchun, \(n\) ta qiymatni birlashtirishda \(n-1\) o‘rniga \(n\) ta taqqoslash kerak deb hisoblaylik. \(n\) katta bo‘lganda va Big O notatsiyasi yordamida yuqori chegarani hisoblamoqchi bo‘lganimizda bu maqbul taxmin.

Demak, birlashtirish amalga oshadigan har bir darajada \(n\) ta taqqoslash kerak, lekin darajalar nechta? Xo‘sh, \(n=16\) uchun \(n=16=2^4\), ya’ni birlashtirishning 4 ta darajasi bor. \(n=32=2^5\) uchun birlashtirishning 5 ta darajasi bor va har bir darajada \(n\) ta taqqoslash kerak. \(n=1024=2^{10}\) uchun birlashtirishning 10 ta darajasi kerak. 2 ning qaysi darajasi 1024 ni berishini aniqlash uchun 2 asosli logarifmdan foydalanamiz. Javob — 10. Matematik ko‘rinishda bu shunday yoziladi: \( \log_{2}1024=10\).

Yuqoridagi rasmdan ko‘rib turganimizdek, har bir darajada \(n\) ta taqqoslash kerak va \( \log_{2}n\) ta daraja bor, shuning uchun jami \( n \cdot \log_{2}n\) ta taqqoslash amali bajariladi.

Vaqt murakkabligini bo‘lish amallari soni va birlashtirish amallari soni asosida hisoblash mumkin:

\[ \begin{equation} \begin{aligned} O( (n-1) + n \cdot \log_{2}n) {} & = O( n \cdot \log_{2}n ) \end{aligned} \end{equation} \]

Bo‘lish amallari soni \((n-1)\) ni yuqoridagi Big O hisobidan olib tashlash mumkin, chunki katta \( n\) uchun \( n \cdot \log_{2}n\) ustunlik qiladi, shuningdek algoritmlarning vaqt murakkabligini qanday hisoblashimiz ham shunga imkon beradi.

Quyidagi rasmda \(n\) ta qiymatli massivda Merge Sort ishga tushirilganda vaqt qanday ortib borishi ko‘rsatilgan.

Merge Sort uchun eng yaxshi va eng yomon holatlar orasidagi farq boshqa ko‘plab saralash algoritmlaridagidek katta emas.

---

Merge Sort simulyatsiyasi

Simulyatsiyani massivdagi turli miqdordagi qiymatlar uchun ishga tushiring va Merge Sort \(n\) ta elementli massiv uchun bajaradigan amallar soni \(O(n \log n)\) ekanini ko‘ring:

Agar qiymatlar soni \(n\) ni o‘zgarmas qoldirsak, "Tasodifiy", "Kamayish tartibida" va "O‘sish tartibida" variantlari uchun kerak bo‘ladigan amallar soni deyarli bir xil bo‘ladi.

Merge Sort har safar deyarli bir xil ishlaydi, chunki massiv allaqachon saralangan bo‘lsa ham, bo‘lmasa ham, u bo‘linadi va taqqoslash yordamida birlashtiriladi.

---

---