Мундарижа Кириш

2.2.5. Бирлаштириб саралаш усули

Бирлаштириб саралаш – рекурсив саралашлардан биринчи учраган алгоритмдир. Унинг асосида сараланган икки рўйхатлар бирлашуви тез бажарилади деган фикр ётади. Бир элементдан иборат рўйхат сараланган, шунинг учун бирлаштириб саралаш рўйхатни бир элементли қисмларга ажратади, сўнгра қадамба-қадам уларни бирлаштиради. Шу туфайли барча фаолият икки рўйхатни бирлаштириш билан якунланади.

Бирлаштириб саралашни рекурсив юқорига ҳаракатланишни бажарувчи рекурсив алгоритм шаклида ёзиш мумкин. қуйида бериладиган алгоритмга қараб шуни кўриш мумкинки, у қисмдаги биринчи элемент рақами охирги элемент рақамидан кичик бўлгунга қадар рўйхатни иккига бўлаверади. Агар навбатдаги қисмда бу шарт бажарилмаса у ҳолда биз бир элементли рўйхатгача борганлигимиздан далолатдир. MergeSort процедурасининг икки марта чақилишидан сўнг бу икки рўйхатни бирлаштирувчи MergeLists процедураси чақирилади. Ейинги даражага қайтишда икки элементлт икки рўйхат тўрт элементли битта рўйхатга бирлаштирилади. Бу жараён то дастлабки чақирувга етгунимизга қадар давом эттирилади. Тушунарлики, MergeSort процедураси пастга рекурсив ҳаракатида рўйхатни иккига бўлиб боради, кейин тескари йўлда сараланган рўйхат қисмларини бирлаштирибкелади. Мана ўша алгоритм:

MergeSort(list,first,last)

list сараланадиган элементлар рўйхати

first сараланадиган рўйхат қисмининг биринчи элементи рақами

last сараланадиган рўйхат қисмининг охирги элементи рақами

if first

middle=(first+last)/2

MergeSort(list,first,middle)

MergeSort(list,middle+1,last)

MergeLists(list,first,middle,middle+1,last)

end if

Тушунарлики, барча ишни MergeLists функцияси бажаради. Энди у билан шўғулланамиз.

А ва В — ўсиш тартибида сараланган икки рўйхат бўлсин. Биз биламизки, икки рўйхатни биттага бирлаштиришда энг кичик элемент бирлашган рўйхатда ё А қисмда, ёки В қисмда биринчи ўринда келиши шарт, энг катта элемент эса бирлашган рўйхатда ё А қисмда, ёки В қисмда охирги ўринда келиши шарт. А ва В рўйхатларни бирлаштирувчи янги С рўйхатни тузишни А[1] ва В[1] элементлардан кичигини С[1] га қўйишдан бошлаймиз. Аммо С[2] га нима тушади? Агар А[1] элемент В[1] дан кичик бўлса уни С[1] га ёзамиз ва навбатдаги элемент В[1] ёки А[2] бўлиши мумкин. Ёки бошқача вариант ҳам бўлиши мумкин, биз фақат А[2] элемент А[1] дан катта ва А[3] дан кичиклигини биламиз, аммо бизга А ва В рўйхатлар катталиклари ўртасидаги муносабат номаълум. А ва В рўйхатлар учун биттадан кўрсаткич киритамиз ва қайси рўйхат элементи кичик бўлса мос кўрсаткични орттирамиз. Умумий процедура А ва В рўйхатнинг ҳали кўрилмаган қисмларидан энг кичикларини солиштиришни давом эттиради ва улардан кичигини С рўйхатга кўчиради. Қайсидир вазиятда А ва В рўйхатлардан бирининг элементлари тугайди. Бошқасида эса биринчи рўйхат охирги элементидан катта бўлган элементлар қолади. Биз бу қолган элементларни умумий рўйхатнинг охирига кўчириб ёзишимиз керак.

Булар жамланиб қуйидаги алгоритмга келинади:

MergeLists(list,start1,end1,start2,end2)

list сараланадиган элементлар рўйхати

start1 А рўйхат "боши"

end1 А рўйхат "охири"

start2 В рўйхат "боши"

end2 В рўйхат "охири"

// фараз қиламиз А ва В рўйхатлар элементлари

// list рўйхатда кетма-кет турибди

finalStart=start1

finalEnd=end2

indexC=1

while (start1<=end1) and (start2<=end2) do

if list[start1]

result[indexC]=list[start1]

startl=start1+1

else

result[indexC]=list[start2]

start2=start2+1

end if

indexC=indexC+1

end while

// рўйхат қолган қисмини кўчириш

if (start1<=end1) then

for i=start1 to end1 do

result[indexC]=list[i]

indexC=indexC+1

end for

else

for i=start2 to end2 do

result[indexC]=list [i]

indexC=indexC+1

end for

end if

// натижани рўйхатга қайтиши

indexC=1

for i=finalStart to finalEnd do

list [i]=result[indexC]

indexC=indexC+1

end for

MergeLists алгоритми таҳлили

Элементларни солиштириш билан фақат MergeLists процедураси шуғулланади, шунинг учун унинг таҳлилидан бошлаймиз. А рўйхат барча элементлари В рўйхат элементларидан кичик бўлган ҳолни қараймиз. MergeLists процедураси нима қилади? У А[1] ва В[1] элементларни солиштиради ва А[1] элемент кичиклигидан С рўйхатга кўчирилади. Кейин А[2] ва В[1] элементлар солиштирилади ва кичик А[2] элемент С рўйхатга кўчирилади. А рўйхат барча элементларини B[1] билан солиштириш жараёни рўйхат охиригача такрорланади. Бу шуни билдирадики, алгоритм N_A солиштириш бажаради, бунда N_A билан А рўйхатдаги элементлар сони белгиланган. Аксинча, агар В рўйхат барча элементлари А рўйхат элементларидан кичик бўлса, у ҳолда солиштиришлар сони N_B га, яъни В рўйхат элементлари сонига тенг бўлади.

Агар А рўйхатнинг биринчи элементи В рўйхатнинг биринчи элементидан катта, лекин А рўйхатнинг барча элементлари В рўйхатнинг иккинчи элементидан кичик бўлса нима бўлади? У ҳолда биз А[1] ва В[1] ларни солиштирамиз, В[1] элементни С рўйхатга кўчирамиз ва А рўйхат ҳар бир элементини В[2] билан солиштиргандан сўнг уни С га кўчирамиз. Бу ҳолда барча солиштиришлар сони N_A + 1 га тенг бўлади. Бошқа юқорида тавсифланган каби ҳолларда энг яхши ҳолат юз беради.

Биз кўрдикки агар А рўйхатнинг барча элементлари B[1] ва _-В [2] элементлар орасида бўлса, солиштиришлар сони А рўйхат барча элементлар В рўйхат элементларидан кичик бўлган ҳолдаги солиштиришлар сонидан кўп бўлади. Агар А ва В рўйхат элементлари қийматлари «бирин-кетин» жойлашган бўлса нима бўлишини қараймиз. Бошқача айтганда, агар А[1] элемент В[1] ва В[2] орасида жойлашса, А[2] элемент В[2] ва В[3] лар орасида жойлашса, А[3] элемент В[3] ва В[4] орасида ва ҳ.к. жойлашса нима бўлади. Натижада ҳар бир солиштиришда А ёки В рўйхатлардан бирининг элементи С га кўчирилади. Бу тартиблашда А рўйхатнинг охирги элементидан ташқари икки тўпламдаги барча элементлар бирин кетин кўчирилади. Натижада бу энг ёмон ҳол солиштиришлари N_A+N_B-1 га тенг.

MergeSort алгоритми таҳлили

MergeLists алгоритми қийинлиги ҳақидаги маълумотларни олгач, энди MergeSort алгоритмига мурожаат қиламиз. Сезиш мумкинки, бу функция ўзгарувчи first қиймати ўзгурувчи last қийматидан кичик ҳолларда рекурсив чақирилаверади. Бу шуни кўрсатадики, агар бу қийматлар тенг ёки first қиймати last дан катта бўлса, рекурсив чақирув бажарилмайди. Агар first ва last тенг бўлса, у ҳолда рўйхат узунлиги бирга тенг, агар first қиймати last дан катта бўлса, у ҳолда нол узунликдаги рўйхатга эга бўламиз. Бу икки ҳолда ҳам алгоритм ҳеч нарса бажармайди ва солиштиришлар сони нолга тенг.

Рўйхатни икки қисмга бўлиш middle қийматини ҳисоблашда рўй беради. Бу ҳисоблаш солиштириш бажармайди ва бўлиш қисмида солиштиришлар нолга тенг. Ўзгарувчи middle нинг қиймати first ва last ўртаси аниқлигида жойлашган, шунинг учун ҳар бир рўйхат узунлиги бутун рўйхат ярмига тенг. N элементдан иборат рўйхатнинг ҳар икки рўйхати N/2 элементлардан тузилган. MergeLsits ал­горитм натижасидан, бирлаштириш босқичида яхши ҳолатда N/2 солиштириш бажарилади, ёмон ҳолда эса солиштиришлар N/2+ N/2 - 1 - N – 1 га тенг. Бу барча катталикларни тўплаб ёмон ҳол учун (W) ва яхши ҳол учун (В) рекуррент муносабатларни ҳосил қиламиз:

W(N) = 2W(N/2)+ N-1,

W(0)= W(1)= 0;

B(N) = 2B(N/2)+ N/2,

B(0) = B(1) = 0.

Энди бу рекуррент муносабатларни § 1.6 бўлим усулларидан фойдаланиб ечамиз. Ёмон ҳолдан бошлаймиз:

W(N/2)= 2W(N/4) + N/2 - 1;

W(N/4)= 2W(N/8) + N/4- 1;

W(N/8) = 2W(N/16)+ N/8 - 1;

W(N/16)= 2W(N/32)+ N/16- 1.

Энди алмаштиришларни бажарамиз:

W(N) = 2W(N/2)+ N - 1

= 2(2W(N/4)+ N/2 - 1) + N - 1

= 4W(N/4) + N - 2 + N-1

= 4(2W(N/8)+ N/4 - 1) + N - 2 + N-1

= 8W(N/8) + N - 4 + N - 2 + N-1

= 8(2W(N/16)+ N/8 -1) +N-4+ N-2 + N-1

= 16W(N/16) +N-8 +N-4 + N-2+N-1

= 16(2W(N/32)+N /16 -1)+N-8+N-4 +N - 2 +N -1

= 32W(N/32) + N - 16 + N-8 + N - 4 + N-2 + N - 1.

Кўриниб турибдики, W олдидаги коэффициент алмашувчи тезлигида ўсади. Охир оқибатда бу аъзо W(1)га тенг бўлади, яъни нолга ва бу қўшилувчи йўқолади. Сезиш мумкинки, ҳар бир алмаштиришда N қўшилувчи қўшилади ва иккининг навбатдаги даражаси айрилади. Натижа қандай бўлади? Охирги тенгликнинг ўнг қисмида 5 та N қўшилувчи ва икки даражалари йиғиндиси нолдан (1 = 2°) то тўртгача (16=2⁴), яна W(N/32)=W(N/2⁵). Шунинг учун охирги тенгликка етганимизда тенглик қуйидаги ёпиқ шаклга эга бўлади:



Бу шуни билдирадики, W(N) = O(N log N). W(N)дан B(N)га ўтиш фарқи шуки, N ни N/2 билан алмаштирилади. N нинг алмаштиришлардаги аҳамиятини ўрганиб, ҳосил қилиш мумкинки , шу туфайли энг яхши ҳол учун ҳам B(N)=(N log N) ўринли.

Бу шуни кўрсатадики, бирлаштириб саралаш ҳатто энг ёмон ҳолда ҳам жуда самарадор, аммо бирлаштириш процедураси MergeLists учун қўшимча хотира талаб қилинади.