5-ma’ruza. Bo'lish va boshqarish algoritmlari asosiy tushunchalar. Bo’lib tashla va hukmronlik qil

Merge sort (Birlashtirib saralash)

"Dasturlashning eng asosiy muammosi — bu murakkablik. Murakkablikni hal qilishning faqatgina bitta asosiy yo'li bor: Bo'lib tashla va hukmronlik qil" — Bjarne Stroustrup
Bo'lib tashla va hukmronlik qil.
O'tgan darsimizda sizlar bilan ikkilik qidirish (binary search) algoritmi va uning implementatsiyasini ko'rib chiqdik. Bu darsimizda ham "Bo'lib tashla va hukmronlik qil bo'limi"ni davom ettirgan holda, uning eng mashhur saralash algoritmlaridan biri bo'lgan Merge Sort (Birlashtirib saralash) haqida gaplashamiz.
Merge Sort va uning ishlash prinsipi
Merge Sort bu saralanmagan arrayni taqqoslashga asoslangan holda saralovchi algoritm bo'lib, uning ishlash prinsipida to'liq bo'lib tashla va hukmronlik qil g'oyasini uchratish mumkin. Demak, merge sort 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 vaqtni o'zida hosil bo'luvchi array saralangan bo'lishini ta'minlash.
   

Merge sort qanday ishlashini vizual tasavvur qilish uchun quyidagi rasmga e'tiboringizni qaratmoqchiman. Unda amallar tartibi ham ko'rsatib qo'yilgan

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
Merge sort algoritmi qadamlari

1. 
   Merge Sort funksiyasiga array va uning boshlang'ich (left) va oxirgi nuqtalari (right) beriladi.
   
2. 
   Arraynining o'rtasi hisoblanadi: mid = (left + right)/2. Bu narsa uni teng ikkiga bo'lish uchun kerak bo'ladi.
   
3. 
   Merge sortni rekursiv holda birinchi va ikkinchi qismlar uchun chaqiriladi.
   
4. 
   2- va 3-qismlarda hosil bo'lgan arraylar birlashtirib chiqiladi. (Array mavzusidagi ikkita arrayni birlashtirish masalasini ko'rib chiqing)
   

Algoritm ishlash tezligi O(nlogn) bo'lib tezligi O(n²) bo'lgan oddiy Bubble, Insertion, Selection Sortlardan ancha tez ishlaydi. O'zi umuman olganda, taqqoslash asosida ishlaydigan algortmlarning eng tez ishlash holati O(nlogn) bo'lishi isbotlangan.
Merge sort turg'un saralash hisoblanadi, ya'ni saralamagan arrayda bir nechta bir xil elementlar kelgan bo'lsa, ularning tartibi saralangan massivda ham o'zgarib ketib qolmaydi.
Algoritm ishlashi uchun xotiradan qo'shimcha O(n) joy talab qiladi.