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

Ўртача ҳол таҳлили
Ўртача ҳолни таҳлил қилиш учун ноодатий усулни қўллаймиз. Дастлаб массивдаги қийматлар тескари тартибда жойлашган энг яхши ҳолдан бошлаймиз. Бундай жойлашиш автоматик тўғри пирамидани беришини текшириш қийин эмас. Шу сабабли ҳар бир FixHeap процедуранинг чақирилишида элементлар тўғри жойлашганлигини тасдиқловси икки солиштириш бажарилади. FixHeap процедураси тахминан элементлар ярми учун чақирилади ва ҳар бир чақирув икки солиштириш талаб қилади. Пирамидани қуриш босқичида худди ёмон ҳолдаги каби N солиштириш бажарилади.
Элементларнинг дастлабки жойлашишидан қатъий назар биринчи босқич натижаси доим пирамида бўлади. Шунинг учун исталган ҳолда цикл for ёмон ҳолдаги каби марта бажарилади: Сараланган рўйхатни ҳосил қилиш учун пирамидадан ҳар сафар уни қайта шакллантириб барча элементларни олишимиз керак. шу туфайли энг яхши ҳолда пирамидали саралаш қарийб N + NlogN солиштириш бажаради, яъни энг яхши ҳол қийинлиги га тенг.
Демак, пирамидали саралаш учун энг яхши ва энг ёмон ҳолдаги қийинлик бир хил ва улар га тенг. Бу эса ўртача ҳол қийинлиги ҳам га тенглигини билдиради.
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