Toshkent axborot texnologiyalari universiteti samarqand filiali mustaqil ish

Merge Sort va uning ishlash prinsipi

Merge Sort bu saralanmagan arrayni taqqoslashga asoslangan holda saralovchi algoritm bo’lib, uning ishlash prinsipi “Bo’lib tashla va hukmronlik qil” paradigmasi asosiga qurilgan. Agar bu paradigma haqida hali bilmasangiz, ushbu maqoladan o’qib ma’lumot olishingiz mumkin.

Algoritm realizatsiyasida rekursiya muhim rol o’ynaydi. Shuning uchun agar ulgurmagan bo’lsangiz VI bo’lim bo’lgan Rekursiya bo’limini ko’rib chiqishni tavsiya etamiz.

Demak, merge sort algoritmi asosiy ikkita qismdan iborat:

1. 
   Berilgan arrayni rekursiv holda teng ikkita qismlarga bo’lib chiqish. Bu qadam, qism arraylar uzunligi 1 ga (yoki undan kichik) teng bo’lib qolguncha davom etadi.
   
2. 
   Hosil bo’lgan arraylarni qaytib birlashtirib chiqish va bir vaqtning o’zida hosil bo’luvchi array saralangan bo’lishini ta’minlash.
   

Merge sort qanday ishlashini vizual tasavvur qilish uchun quyidagi ajoyib animatsiyani ko’rishingiz mumkin.

I

Bu animatsiyadan algoritm realizatsiyasini to’liq tasavvur qilish qiyin bo’lishi mumkin. Shuning uchun quyidagi rasmni ham keltirib o’tamiz. U yerda algoritm qanday ishlashi qadamma-qadam ko’rsatilgan:

Image source: Baeldung

Ko’rib turganingizdek algoritm ishlash prinsipini tushunish uchun unchalik ham murakkab emas. Va yana e’tibor bergan bo’lsangiz, birinchi bo’linishdan keyingi arrayning chap va o’ng qismlarida asosiy array bilan bir xil amal ketmoqda, ya’ni bizning masalamizning qism masalasi ham bosh masala bilan bir xilda ishlaydi.

Endi esa algoritmni implementatsiya qilish uchun qadamma-qadam nima qilish kerakligiga o’tamiz