12-Ma’ruza: Algoritmlar murakkabligining o’sish tezligi

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

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:

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

Merge Sort funksiyasiga array va uning boshlang’ich (left) va oxirgi nuqtalari (right) beriladi.

Arraynining o’rtasi hisoblanadi: mid = (left + right)/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. (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

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

E’TIBORINGIZ UCHUN RAHMAT!