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.
