Ma’lumotlar tuzilmasi va algoritmi

TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI SAMARQAND FILIALI

MUSTAQIL ISH


FANNING NOMI:”Ma’lumotlar tuzilmasi va algoritmi”
Bajardi : Namozov
MAVZU:

Birlashtirish orqali (MERGE SORT) algoritmi orqali Respublikamizdagi viloyatlar maydonini o’sish tartibida joylashtiring .(Foydalangan saralash algoritmingiz haqida nazariy ma’lumot bering?

Birlashmali saralash (Merge Sort)

Birlashmali saralash (Merge Sort) algoritmi asosiy beshta saralash algoritmlari (pufakchali saralash, tezkor saralash va boshqalar) dan biri bo`lib, chiziqli saralash algoritmlaridan farqli ravishda "bo`lib tashla va hukmronlik qil" tipidagi algoritm hisoblanadi.
Bu tipdagi algoritmlar katta hajmdagi masalalarni nisbatan kichik bo`lgan va oson yechiladigan qismlarga ajratgan holda bajaradi. Bunday algoritmlar masalalarni hal qilishda vaqtdan katta yutuq qilish imkonini beradi.
Birlashmali saralashda biz berilgan massivni uzunligi faqat 1 elementga teng bo`lgan qismlar qolmaguncha o`rtasidan ajratamiz. Keyin bu qismlar to`g`ri tartibda birlashtiriladi.


“Algoritm — bu dasturchilar o’zlari nima qilayotganliklarini boshqalar bilmasligini xohlagan paytida ishlatadigan so’zlari” — Unanonymous.
Oldingi darslarimizda sizlar bilan elementar va sodda saralash algoritmlarini ko’rib chiqqan edik. Ular esa amalda kam qo’llaniladi. Bugungi darsimizdan boshlab murakkabroq saralash algoritmlaridan biri bo’lgan Merge sort haqida gaplashamiz.

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. Agar bu paradigma haqida hali bilmasangiz, ushbu maqoladan o’qib ma’lumot olishingiz mumkin.
Algoritm realizatsiyasida rekursiya muhim rol o’ynaydi. Shuning uchun agar ulgurmagan bo’lsangiz VI bo’lim bo’lgan Rekursiya bo’limini ko’rib chiqishni tavsiya etamiz.
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.

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

Image source: Baeldung
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