Dərs vəsaiti baki -2018 azərbaycan döVLƏt neft və SƏnaye universiteti

2) Birləşdirmə ilə nizamlama üsulu. Bu üsulu bəzən “ardıcıllığı yarıya bölüb birləşdirmə üsulu” adlandırırlar. Bu üsul yerinə yetirilən zaman verilmiş ardıcıllıq iki bərabər hissəyə bölünür. Elementlərin sayı cüt olduqda verilmiş ardıcıllığı iki bərabər hissəyə bölmək mümkündür, amma tək olduqda bu mümkün deyil . Ona görə də parçalanma əməliyyatı hissələrdən birinin ölçüsü ( yəni elementlərinin sayı) digərindən bir vahid artıq olmaqla yerinə yetirilə bilər. Növbəti addımda hissələrdən hər biri iki “bərabər hissəyə” bölünür və s. Bölünmə əməliyyatı o məqama qədər davam edir ki, nəhayət, hər hissədə yalnız bir element qalmışdır. Bu üsul əsasında verilmiş ardıcıllığın parçalanması prosesini yüxarıda şərh olunmuş “sürətli nizamlama” üsulunda olduğu kimi ağac modeli ilə təsvir etmək olar. Sonra yadda saxlanılmış həmin ağac modeli əsasında aşağıdan yuxarıya parçaların birləşdirilməsi əməliyyatı yerinə yetirilir. Ancaq birləşdirmə əməliyyatı konkatenasiya əməliyyatı ilə eyni deyil. Konkatenasiya birləşdirmənin xüsusi halıdır, belə ki, konkatenasiya prosesində birləşdirilən parçalardan birincinin maksimal elementi ikincinin minimal elementindən böyük olmur (bizim baxdığımız misallarda, sadəlik üçün, kiçik olur). Birləşdirmə əməliyyatında isə bu hal müşahidə olunmaya bilər. Birləşdirilən parçaların hər biri nizamlanmış olur. Birlədirmədə iki parça iştirak etdiyini fərz edək. Hər addımda parçaların birinci elementləri müqayisə olunur: bunlardan hansı kiçikdirsə, olduğu yerdən silinir və yeni yaradılan ardıcıllığın növbəti xanasına, yəni sonuna yazılır. Birləşdirmə əməliyyatını misalla izah edək:

Baxdığımız misalda yeni siyahı başlanğıcda boş olduğuna görə buraya əvvəlcə “2” yazılıb, ikinci addımda “3” yazılıb və s. Beləliklə, bu üsul o zaman əlverişlidir ki, verilmiş ardıcıllıqda nizamlanmış müəyyən fraqment (fraqmentlər) olsun. Əgər belə fraqmentlər olarsa, bunların ən böyüyündən başlayaraq ardıcıllığın digər hissələrini buna birləşdirməyə cəhd etmək lazımdır. Qeyd edək ki, müəyyən fraqment əksinə nizamlanmış olduqda bunu düzünə (artma ilə) nizamlayıb digər fraqmentlərlə birləşdirmə əməliyyatı da əlverişli hesab olunur. İş burasındadır ki, əksinə nizamlama əməliyyatı heç bir müqayisə olunmadan yerinə yetirilir, ona görə də əlverişli əməliyyat hesab olunur. Verilmiş ardıcıllıqda əlverişli fraqmentlər olmadıqda yuxarıda qeyd olunduğu kimi, verilmiş ardıcıllığı parçalamaqdan başlamaq lazımdır. Aşağıda qurulan ağac modelində yuxarıda baxılan ardıcıllığın yarıya bölmə üsulu ilə parçalanmasına baxılmışdır. Qeyd edək ki, yarıya bölmə əməliyyatının sonuncu səviyyəsində bir sıra fraqmentləri yarıya bölməmək olardı: {10,18}, {5,20}, {4,16}, {8,19} fraqmentlərinin hər biri artıq nizamlanmışdır.
1 ) {10,18} U {5,20} {5},
2 ) {10,18} U {20} {5, 10},
3 ) {18} U {20} {5, 10, 18},
4 ) Ø U {20} {5, 10, 18, 20}.

Eyni qayda ilə {4,16} U {12} əməliyyatııını yerinə yetirərək {4,12,16} nizamlanmış ardıcıllığını qurmaq mümkündür. {5, 10, 18, 20} U {4,12,16} əməlıyyatı nəticəsində {4,5,10,12,16, 18, 20} ardıcıllığı qurulur və s.

10,18,5,20,4,16,12,8,19,6,15,14,9

1 0,18,5,20,4,16,12 8,19,6,15,14,9

1 0,18,5,20 4,16,12 8,19,6 15,14,9

1 0,18 5,20 4,16 12 8,19 6 15,14 9

10, 18, 5, 20, 4, 16, 8, 19 15, 14

Birləşdirmə ilə nizamlama üsulunun prosedurunu BN ilə işarə edək. Cari siyahının sol, orta və sağ elementlərini müvafiq surətdə l,m,r ilə işarə edək. Bundan başqa birləşdirmə prosedurunu daxil edək və onu BP ilə işarə edək.

BN(l,r) proseduru:
l olarsa, yerinə yetir: m:= ;
BN(l,m) prosedurunu çağır;
BN(m+1,r) prosedurunu çağır;
BP(l,m,r) prosedurunu çağır;
BN(l,r) prosedurunun sonu.
BP(l,m,r) prosedurunu ümumi şəkildə qurmaq üçün qaydanı şərh edək. Tutaq ki, verilmiş A=(a_l, a_l+1,...,a_m) və B=(a_m+1,...,a_r) siyahılarını birləşdirib nəticədə yeni C siyahısını qurmaq tələb olunur.
BP(l,m,r) proseduru:
A və B siyahıları boş deyilsə, bunların birinci elementlərini müqayisə et, kiçik olan elementi olduğu siyahıdan çıxart C siyahısının sonuna yaz;
A və B siyahılarından hər hansı biri boşdursa, digər boş olmayan siyahını (A və ya B) bütövlükdə C siyahısının sonuna yaz;
C siyahısının elementlərini (a_l, a_l+1,...,a_r) ilə işarə et;
BP(l,m,r) prosedurunun sonu.