Mavzu:Merge sort Reja: 1.Merge sort haqida nazariy ma’lumot 2.Algoritmi 5.Misollar 6.Xulosa Merge sort tarkibiy qismlari - Bo’lib tashlash bosqichi. Bunda bosh masala huddi shu masalaga o’xshash kichikroq masalalarga bo’lib chiqiladi.
- Hukmronlik bosqichi. Asos holatimizga mos kelib qolgan qism masalalar huddi u kabi yechiladi.
- Birlashtirish bosqichi. Bu bosqichda yechilgan kichik qism masalalar qaytib birlashtirib chiqiladi va bu bosh masala yechimi bo’ladi.
Merge sort haqida nazariy ma’lumotlar 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 Merge sort algoritmi 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 vaqtning o’zida hosil bo’luvchi array saralangan bo’lishini ta’minlash. Merge sort qanday ishlashini tasavvur qilish uchun quyidagi rasmni ko’rishingiz mumkin. Oddiy, bittagina qadamdan iborat bo’lib tashla va hukmronlik qil algoritmi qanday ishlashini ko’raylik: Agar biz qadamlar sonini oshiradigan bo’lsak, paradigma tasviri quyidagicha ko’rinish oladi: Algoritmi 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.
- 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.
- 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.
Merge sortning afzalliklari - qiyin masalalarni osonlik bilan yechishga imkon beradi
- bu paradigmaga asoslangan algoritmlar oddiy yechimlardan ko’ra tezroq ishlaydi. Masalan: oddiy saralash bo’lgan Bubble Sortning tezligi O(n²) bo’lsa, MergeSortniki O(n*logn)
- bunday algoritmlarni parallel hisoblovchi sistemalarda hech qanday o’zgarishsiz ishlatish mumkin
- bunday algoritmlarni qo’llashda xotira keshidan unumli foydalanish mumkin. Chunki masalalar bo’linish jarayonida shunday kichik qismlarga ajraladiki, ularni keshni o’zida turib yechish mumkin bo’ladi.
- haqiqiy sonlar uchun bunday algoritmlar aniqroq ishlaydi, chunki qism yechimlardagi haqiqiy sonlar ustidagi amallar aniqroq bajariladi (masalan, ko’paytirish algoritmlarida)
Merge sortning kamchiliklari - bunday paradigma asosida ishlaydigan algoritmlar rekursiyadan foydalanadi va bu narsa ularni ishlashini ma’lum miqdorga sekinlashtiradi. Buning ustiga kichik bir xato yechimni cheksiz takrorlanishga tushirib qo’yishi mumkin.
- asos shartni tanlashda yo’l qo’yilgan xato barcha qism masalalarda xatolik va ortiqcha xotira ishlatilishiga olib keladi
Dastur kodi: Davomi: Dastur natijasi: Xulosa Merge sort bizga malumotlarni tez saralab beradi va xotiradan kam joy egallaydi. E’tiboringiz uchun raxmat! Tayyorladi:To’ymurodov Abrorbek
Do'stlaringiz bilan baham: |
