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

Қадамларнинг самарадорликка таъсири
Шелл усули учун қадамлар кетма-кетлигини танлаш ҳал қилувчи таъсирни кўрсатиши мумкин, аммо оптимал қадамларни қидириш дастлабки натижага олиб келмади. Мумкин бўлган барча вариантлар ўрганилди ва уларнинг натижаси қуйида келтирилади.
Агар ўтишлар ҳаммаси иккита бўлса, у ҳолда биринчи ўтишда қийинликка ва иккинчи ўтишда қийинликка эга бўламиз.
Бошқа мумкин бўлган қадамлар тўплами барча j лар учун шаклга эга ва ҳолда. Бу қийматлар ва тенгликлар билан таъминланади, шунинг учун улардан энг каттасини аниқлаб қолганларини формула билан ҳисоблашимиз мумкин. бундай қадамлар кетма-кетлиги алгоритмга қийинлик беради.
Яна бир вариант рўйхат узунлигидан кичик бар ча қийматларини ҳисоблашни кўриб чиқишдир (ихтиёрий бутун i ва j да); қийматларни ҳисоблаш камайиш тартибида амалга оширилади. Масалан, N–40 да қадамларнинг қуйидаги кетма-кетлиги бўлади: 36(2²3²), 32(2⁵3⁰), 27(2⁰3³), 24(2³3²), 18(2¹3²), 16(2⁴3⁰), 12(2²3¹), 9(2⁰3²), 8(2³3⁰), 6(2¹3¹), 4(2²3⁰), 3(2⁰3¹), 2(2¹3⁰), 1(2⁰3⁰). Бундай кетма-кетлик ёрдамида Шелл усули қийинлиги O(N(logN))га қадар камаяди. Сезиш керакки, ўтишларнинг катта сони кераксиз сарфларни кўпайтиради, шунинг учун бу кетма-кетликларни кичик рўйхатларда қўллаш самара бермайди.
Шелл усули — бу саралашнинг умумий шакли бўлиб, параметрларни танлаш унинг самарадорлигига сезиларли таъсир кўрсатади.


2.2.4. Пирамида усули билан саралаш алгоритми
Пирамидали саралашнинг асосида пирамида деб аталувчи бинар дарахтнинг махсус тури ётади; бундай дарахтдаги исталган қисм дарахт илдизининг қиймати унинг авлодалари қийматидан катта бўлади. Бевосита ҳар бир тугун авлодлари тартибланмаган, шунинг учун баъзида чап авлод ўнгидан кичик бўлади, баъсида бунинг тескариси бўлади. Пирамида ўзида янги даражани тўлдириш фақат олдинги даража тўлиқлигича тўлдирилгач бошланадиган ва бир даражада тугунлар чапдан ўнгга тўлдириладиган тўлиқ дарахтни намоён қилади.
Саралаш пирамидани қуришдан бошланади. Бунда максимал элемент дарахт учида жойлашади, чунки унинг авлодлари кичик бўлиши керак. Кейин илдизга рўйхатнинг охирги элементи ёзилади, ўчирилган максимал элементли пирамида эса қайта тузилади. Натижада илдизда катталиги бўйича иккинчи элемент пайдо бўлади, у рўйхатга кўчирилади ва бу жараён барча элементлар рўйхатга қайтгунча давом эттирилади. Мос келувчи алгоритм қуйидагича:
пирамидани тузиш
for i=1 to N do
пирамида илдизини рўйхатга кўчириш
пирамидани қайта тузиш
end for
Бу алгоритмдаги айрим жиҳатларни аниқлаштириш керак. Дастлаб пирамидани тузиш ва қайта тузиш қанақа жараёндан иборатлигини аниқлашимиз керак: бу алгоритм самарадорлигига таъсир кўрсатади.
Бизни алгоритм иши қизиқтиради. Бинар дарахтни қуришга кетадиган қўшимча харажатлар рўйхат ўсиши билан ўсади. Аммо банд рўйхат ўрнидан фойдаланиш мумкин. рўйхатни пирамидага «қайта қуриш» мумкин, агар ҳар бир ички тугунда икки бевосита авлод бўлса, мустасно ҳолда, охиргидан олдинги даражада битта тугунда битта бўлади. Кейинги кўриниш талаб қилинган пирамидани шакллантиришга имкон беради. i рақамли элементнинг бевосита авлодларини 2i ва 2i + 1 ўринларга ёзамиз. Сезамизки, натижада барча авлодлар ҳолати турлича бўлади. Биламизки, агар 2i > N бўлса, у ҳолда i тугун япроқ бўлади, агар 2i = N бўлса, у ҳолда i тугунда битта авлод бўлади. 3.3-расмда пирамида ва унинг рўйхат кўриниши тасвирланган.

3.3-расм. Пирамида ва унинг рўйхат кўриниши