Merge sort - Birlashtirish saralash algoritmi eng mashhur saralash algoritmlaridan biri boʻlib, “Boʻl va zabt et” algoritmiga asoslangan.
- Bu yerda muammo bir nechta kichik muammolarga bo'linadi. Har bir kichik muammo alohida hal qilinadi. Nihoyat, yakuniy yechimni shakllantirish uchun kichik muammolar birlashtiriladi.
- “Bo‘l va zabt et” texnikasidan foydalanib, masalani kichik muammolarga ajratamiz. Har bir kichik muammoning yechimi tayyor bo'lgach, biz asosiy muammoni hal qilish uchun kichik muammolardan olingan natijalarni "birlashtiramiz".
- Faraz qilaylik, biz A massivni saralashimiz kerak edi. Kichik muammo bu massivning p indeksidan boshlanib, r indeksi bilan tugaydigan, A[p..r] deb belgilangan kichik bo‘limini saralash bo‘ladi.
- Agar q p va r o‘rtasidagi yarim yo‘l nuqtasi bo‘lsa, u holda A[p..r] pastki massivni ikkita A[p..q] va A[q+1, r] massivlarga ajratishimiz mumkin.
- Zabt etish bosqichida biz A[p..q] va A[q+1, r] pastki massivlarni ham saralashga harakat qilamiz. Agar biz hali ham asosiy holatga etib bormagan bo'lsak, biz yana ikkala pastki qatorlarni ajratamiz va ularni saralashga harakat qilamiz.
- Zabt etish bosqichi asosiy bosqichga yetganda va biz A[p..r] massiv uchun ikkita tartiblangan A[p..q] va A[q+1, r] pastki massivlarni olamiz, natijalarni tartiblangan A massivini yaratish orqali birlashtiramiz. A[p..q] va A[q+1, r] ikkita tartiblangan pastki massivlardan [p..r].
Do'stlaringiz bilan baham: |
