“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.
64
Birlashtirish bosqichi . Birlashtirish bosqichi asosiy pogʻonaga
yetib borganida va biz A [p..r] massivi uchun ikkita tartiblangan A [p..q]
va A [q + 1, r] kichik massivlarni olsak, natijalarni A [p..r] massiviga
birlashtiramiz. Bu ikkita tartiblangan A [p..q] va A [q + 1, r]
massivlarning birlashmasidir (12-rasm).
Birlashtirib saralash algoritmi. MergeSort funksiyasi massivni
ketma-ket ikki qismga ajratadi, biz 1-darajali ichki massivda MergeSort-
ga oʻtishga harakat qiladigan bosqichga yetguncha ya‘ni p == r
boʻlguncha.
Shundan soʻng, birlashtirish funksiyasi ishga tushadi, bu
tartiblangan massivlarni butun massiv birlashguncha katta massivlarga
birlashtiradi.
12-rasm. Merge Sort algoritmining ishlash prinsipi
65
1.
MergeSort(A, p, r)
2.
If p > r
3.
return;
4.
q = (p+r)/2;
5.
mergeSort(A, p, q)
6.
mergeSort(A, q+1, r)
7.
merge(A, p, q, r)
Butun massivni saralash uchun MergeSort (A, 0, length (A) -1) ga
murojaat qilishimiz kerak.
13-rasmda koʻrsatilgandek, birlashtirib saralash algoritmi 1
elementli massivning asosiy holatiga kelgunimizcha massivni rekursiv
ravishda ikkiga boʻladi. Soʻngra birlashtirish funksiyasi saralangan ichki
massivlarni tanlaydi va butun qatorni asta-sekin saralash uchun ularni
birlashtiradi.
13-rasm. Merge Sort algoritmida massivni qismlarga boʻlish jarayoni
66
Algoritmning eng muhim qismi bu "birlashtirish" bosqichidir.
Birlashish bosqichi - ikkita katta roʻyxat (massiv) yaratish uchun ikkita
tartiblangan roʻyxatni (massivlarni) birlashtirish boʻyicha oddiy
muammoning yechimi.
Ikkinchi massivda boshqa elementlar qolmaganligi va ikkala
massiv ham ishga tushirilganda saralanganligini bilganimiz uchun
qolgan massivlarni toʻgʻridan-toʻgʻri birinchi massivdan nusxalashimiz
mumkin.
