Mavzu: Merge sort va bubble sort saralash algoritmlari Bajardi: 111-20 guruh talabasi Baratboyev Jamshid Tekshirdi: Qayumov Oybek Achilovich Jizzax-2021

MIRZO ULUG’BEK NOMIDAGI O’ZBEKISTON MILLIY UNIVERSITETI JIZZAX FILIALI AMALIY MATEMATIKA FAKULTETI AMALIY MATEMATIKA VA INFORMATIKA KAFEDRASI
Kompyuter ilmlari va dasturlash texnologiyalari 111-20 guruh talabasi
Baratboyev Jamshidning

Mustaqil ishi
ALGORITMIK TILLAR VA DASTURLASH FANIDAN.
Mavzu: Merge sort va bubble sort saralash algoritmlari


Bajardi: 111-20 guruh talabasi
Baratboyev Jamshid
Tekshirdi: Qayumov Oybek Achilovich

Jizzax-2021

Mavzu:Merge sort va bubble sort saralash algoritmlari.
Reja:

1. 
   Merga sort saralash algoritmi.
   
2. 
   Bubble sort saralash algoritmi.
   

Merge sort (Birlashtirib saralash)

Sizlar bilan elementar va sodda saralash algoritmlarini ko’rib chiqqanmiz. Ular esa amalda kam qo’llaniladi. Endi murakkabroq saralash algoritmlaridan biri bo’lgan Merge sort haqida o’rganamiz . 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. Demak, merge sort algoritmi 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 vaqtning o’zida hosil bo’luvchi array saralangan bo’lishini ta’minlash. Merge sort qanday ishlashini vizual tasavvur qilish uchun quyidagi ajoyib animatsiyani ko’rishingiz mumkin.


Bu animatsiyadan algoritm realizatsiyasini to’liq tasavvur qilish qiyin bo’lishi mumkin. Shuning uchun quyidagi rasmni ham keltirib o’tamiz. U yerda algoritm qanday ishlashi qadamma-qadam ko’rsatilgan:


Birinchi bo’linishdan keyingi arrayning chap va o’ng qismlarida asosiy array bilan bir xil amal ketmoqda, ya’ni masalaning 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. 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. Bubble sort (Pufakchali saralash)

Saralash bo’limining yana bir eng sodda saralash algoritmlaridan biri bo’lgan Bubble sort algoritmini ko’rib chiqamiz. Bubble sort algoritmi g’oyasi Bubble sort algoritmi juda ham oddiy ishlaydi. U shunchaki array boshidan yurib ikkita qo’shni elementlarni ularning katta kichikligiga qarab joyini almashtiradi. Bu orqali har bir to’liq yurib chiqishdan keyin arraydagi eng katta (yoki eng kichik) element arrayning eng oxiriga o’tib qoladi. Ushbu xusiyatiga ko’ra bu algoritm ba’zida Sink sort (Cho’kib saralash) deb ham ataladi.