|
Birlashtirish orqali saralash (Merge sort)
|
| bet | 3/3 | | Sana | 23.11.2023 | | Hajmi | 179,43 Kb. | | #104055 |
Bog'liq Pufaksimon saralashBirlashtirish orqali saralash (Merge sort)
Merge Sort bu saralanmagan arrayni taqqoslashga asoslangan holda saralovchi algoritm bo'lib, uning ishlash prinsipida “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.
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.
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.
Birlashtirish bosqichi.
Merge sort algoritmining eng muhim qismi birlashtirish jarayonidir.
Birlashtirish bosqichi bitta katta tartiblangan ro'yxatni (massiv) yaratish uchun ikkita tartiblangan ro'yxatni (massivlarni) birlashtirishning oddiy muammosini hal qilishdan iboratdir.
Algoritm ishlash tezligi O(n*logn) bo’lib tezligi O(n²) bo’lgan oddiy Bubble, Selection Sortlardan ancha tez ishlaydi. O’zi umuman olganda, taqqoslash asosida ishlaydigan algortmlarning eng tez ishlash holati O(n*logn) 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.
|
| |
