63
4-§ Birlashtirib saralash algoritmlari
Merge sort algoritmi. Birlashtirib saralash (Merge sort) –
tartiblashning tezkor bajariladigan algoritmlaridan biri. Ushbu tartiblash
―boʻlib tashla va hukmronlik qil‖ prinsipining yaxshi namunasidir.
Birinchidan, vazifa bir nechta kichik topshiriqlarga boʻlinadi.
Keyin
ushbu vazifalar rekursiv chaqiruv yordamida yoki toʻgʻridan-toʻgʻri
ularning hajmi yetarlicha kichik boʻlsa hal qilinadi. Nihoyat, ularning
yechimlari birlashtirilib, asl muammoning echimi olinadi.
Algoritmning bajarilishi. Saralash
muammosini hal qilish uchun
uch bosqich quyidagicha boʻladi:
1. Saralanadigan massiv taxminan bir xil oʻlchamdagi ikki qismga
boʻlinadi;
2. Olingan qismlarning har biri alohida saralanadi (masalan, xuddi
shu algoritm boʻyicha saralanadi);
3. Yarim kattalikdagi ikkita saralangan massivlar birlashtiriladi.
Bu eng mashhur saralash algoritmlaridan biri boʻlib, rekursiv
algoritmlarni yaratishda ishonchni rivojlantirishning
ajoyib usuli
hisoblanadi.
“Boʻlib tashla va hukmronlik qil” strategiyasi. ―Boʻlib tashla va
hukmronlik qil‖ strategiyasi yordamida muammoni qismiy jarayonlarga
ajratamiz. Har bir kichik topshiriq uchun yechimga ega boʻlsak, pastki
vazifalarni yechish uchun pastki vazifalardan
olingan natijalarni
"birlashtiramiz".
Aytaylik, biz A massivni saralashni xohladik. Kichik vazifa bu p
indeksidan
boshlanib, r indeksida tugagan, A [p..r]
bilan belgilangan
kichik qismini ajratishdir.
“Boʻlib tashlash”. Agar q qiymati p va r orasida boʻlsa, biz A
[p..r] massivni ikkita A [p..q] va A [q + 1, r]
kichik massivlarga
boʻlishimiz mumkin.
“Hukmronlik qilish”. ―Hukmronlik qilish‖ bosqichida biz ikkala
A [p..q] va A [q + 1, r] kichik massivlarni saralashga harakat qilamiz.
Agar hali ham boshlangʻich darajaga yetib bormagan boʻlsak, yana
ikkala quyi qismni ajratib, ularni saralashga harakat qilamiz.
