4-маъруза Саралаш вақтининг қуйи чегараси

4-маъруза

Саралаш вақтининг қуйи чегараси

Аввалги тўртта маърузада кўриб ўтилган саралаш алгоритмлари саралаш калитидан фойдаланишига эътибор қаратадиган бўлсак, улар саралаш тартибини белгилаб беришини кўриш мумкин. Бу вақтда калит жуфтликлари солиштирилади. Улар қабул қилаётган барча қарорлар «агар мазкур элементнинг саралаш калити бошқа элементнинг саралаш калитидан кичик бўлса, у ҳолда ----, акс ҳолда эса бирор иш бажариш ёки умуман иш бажармаслик керак» кўринишида бўлади.
Яна қандай қарорлар қабул қилиши мумкин?
Саралаш коидалари
Мисол.
Дейлик, сараланаётган элементлар ҳақида 2 та маълумотга эгамиз: ҳар бир саралаш калити ёки бирга, ёки иккига тенг ва элементлар саралаш калитларидан ташкил топган, яъни қўшимча маълумотларга эга эмас.
Ишни барча элементлардан ўтиб чиқиш ва нечта бирга тенг эканлигини санашдан бошлаймиз, мисол учун k элемент бўлсин. У ҳолда массивдан қайтадан ўтиб чиқамиз ва биринчи k позицияларга 1 қийматини ўрнатиб чиқамиз, сўнгра эса қолган n-k позицияларга 2 қийматини ўрнатамиз.
Саралаш коидалари
Саралаш коидалари

Таккослаш йўли билан саралашнинг куйи чегераси
Энг ёмон ҳолатда таққослаш йўли билан ихтиёрий саралаш алгоритми n Ω (n lg n) та элементлар жуфтлигини солиштиради. Бу қуйи чегара экзистенциал қуйи чегара деб аталади, чунки у Ω (n lg n) та саралашни талаб этувчи кириш маълумотлари мавжудлигини англатади. Қуйи чегаранинг бошқа тури – универсал қуйи чегара деб аталади ва убарча кириш маълумотлари учун тегишли бўлади. Агар саралашнинг ягона универсал қуйи чегараси Ω(n) бўлса, биз ҳар бир элементга ҳеч бўлмаганда бир маротаба мурожаат қилишимиз лозим.

Таккослаш йўли билан саралашнинг куйи чегераси

Қуйи чегара аниқ алгоритмга боғлиқ эмас, фақат бу алгоритм таққослаш йўли билан саралаш алгоритми бўлса бас. Таққослаш йўли билан саралаш алгоритмининг қуйи чегараси қанчалик содда ёки мураккаб бўлишидан қатъий назар, барча алгоритмларга нисбатан қўлланилади.

Хисобли саралаш
Бу ҳолатда, бизга саралаш калитининг барча мумкин бўлган қийматлари учун, қайси элементнинг калити қиймати кичиклиги ва нечта элемент худди шундай қийматли калитга эканлигини билиш лозим. Кейинги слайдда келтирилган расмда А массивдаги элементни В массивга силжитиш процедураси кўрсатилган бўлиб, натижада улар В массивда сараланган тартибда жойлашиши керак.
Расмнинг юқори қисмида less, next, А ва В массивлари циклнинг 1-итерациясидан аввалги 3 қадами қўрсатилган, қолган қисмларида эса next, А ва В массивлари ҳар бир итерациядан кейинги ҳолати кўрсатилган.
Кул ранг элементлар В массивга нусҳа олинганлигини кўрсатади.

Хисобли саралаш

Хисобли саралаш
Ҳисобли саралаш битта муҳим хоссага эга – турғунлик.
Турғун саралаш ҳолатида бир хил саралаш калитига эга бўлган элементлар, чиқиш массивида, айнан кириш массивидаги каби тартибда жойлашади. Бошқа сўз билан айтганда, бир хил калитга эга иккита элемент учраганда, кўпмаънолик масаласи ҳал бўлади, бунда киришда биринчи турган элемент, чиқишда ҳам биринчи бўлиб жойлашади.

Разрядли саралаш
Разрядли саралаш- бу шундай саралаш турики, унда ҳар сафар калит сифатида ҳар бир символ ишлатилади.
Масалан. Иккита символдан ташкил топган тасдқилаш кодини разрядли саралаш лозим бўлсин.
Ҳар бир символ 36 та қиймат олиши мумкин (26 та ҳарф ва 10 та рақам). Ҳар бир код учун конкрет сон ҳосил қилиш учун, 36 символнинг ҳар бирини 0 дан 35 гача бўлган сонли кодга айлантириш лозим.
Биз уни икки маротаба ишлатамиз. Биринчи марта счаралаш калити сифатида ўнг символ, сўнгра эса натиждани яна бир марта саралаймиз, фақат энди саралаш калити сифатида чап символ ишлатилади.

Разрядли саралаш
Демак, биз навбатма-навбат ўнгдан чапга қараб ҳар бир рақам учун турғун саралашни амалга оширамиз.
Разрядли саралаш ҳар бир рақам бўйича тартиблаш учун ҳисобли саралашни қўллаганда, у ҳеч вақт иккита саралаш калитини бир-бири билан солиштирмайди. У ҳисобли саралашда массивларни индексациялаш учун алоҳида рақамларни ишлатади. Шунинг учун ҳисобли саралаш таққослаш йўли билан саралашнинг қуйи чегараси Ω (n lg n) дан ортиб кетади.

Эътиборингиз учун рахмат