Mavzu: Jamlab saralash algoritmi Merge Sort

Mavzu: Jamlab saralash algoritmi Merge Sort

• Ma’ruzachi: Sh.Farmonov

"Dasturlashning eng asosiy muammosi — bu murakkablik. Murakkablikni hal qilishning faqatgina bitta asosiy yo'li bor: Bo'lib tashla va hukmronlik qil"

• Bjarne Stroustrup

Merge Sort va uning ishlash prinsipi

• Merge Sort bu saralanmagan arrayni taqqoslashga asoslangan holda saralovchi algoritm bo'lib, uning ishlash prinsipi to'liq bo'lib tashla va hukmronlik qil g'oyasiga asoslangan. Merge sort asosiy ikkita qismdan iborat:
• 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.
• Hosil bo'lgan arraylarni qaytib birlashtirib chiqish va bir vaqtni o'zida hosil bo'luvchi array saralangan bo'lishini ta'minlash.

Merge sort algoritmi qadamlari

• Merge Sort funksiyasiga array va uning boshlang'ich (begin) va oxirgi nuqtalari (end) beriladi.
• Arraynining o'rtasi hisoblanadi: medium = (begin + end)/2. Bu narsa uni teng ikkiga bo'lish uchun kerak bo'ladi.
• Merge sortni rekursiv holda birinchi va ikkinchi qismlar uchun chaqiriladi.
• 2- va 3-qismlarda hosil bo'lgan arraylar birlashtirib chiqiladi. 

Baxolash

• 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.

Dastur umumiy ko’rinishi:

Dastur qismlari:

Dastur qismlari:

Dastur qismlari: