Kompyuter injiniringi ” fakulteti “dasturiy injiniring” kafedrasi

Қадамнинг самарадорликка таъсири
Қадамлар кетма-кетлигини танлаш Шелл саралаш алгоритмининг муракканлигига ҳал қилувчи таъсир кўрсатиши мумкин, лекин қадамлар кетма-кетлигининг оптимал вариантини излаш керакли натижага олиб келмади. Бир нечта вариантлар ўрганиб чиқилди; қуйида изланишлар натижаси келтирилган:
Агар ўтишлар фақатгина иккита бўлса, 1-ўтишда 1,72 тартибли қадам ва 2-ўтишда 1, бунда O(N^5/3) саралаш мураккаблигини ҳосил қиламиз.
Бошқа қадамлар тўплами барча j лар учун кўринишга эга бўлади, h_jj нинг бу қийматлари ва тенгликлар билан қаноатлантиради, шунинг учун улардан каттасини аниқлаб, қолганларини формула бўйича ҳисоблашимиз мумкин. Бундай қадамлар кетма-кетлиги O(N^3/2) алгоритм мурккаблигига олиб келади.
Яна бир вариант 2ⁱ 3^j нинг рўйхат узунлигидан кичик бўлган барча қийматларини ҳисоблашни кўриб чиқади, (I ва j лар бутун сонлар); ҳисобланган қийматлар қадамлар қиймати сифатида камайиш тартибида фойдаланилади. Масалан, N=40 да қуйидаги кетма-кетлик ўринли бўлади: 36(2² 3²)… 1(2⁰ 3⁰). Бундай кетма-кетлик ёрдамида Шелл саралашининг мураккаблиги O(N(logN)²) гача камаяди.
Шелл саралаши – бу умумий саралашнинг бир кўриниши, лекин параметрларни танлаш унинг самарадолигига таъсир кўрсатиши мумкин.


7–маъруза: Тезкор саралаш. Тезкор саралаш тавсифи. Массивлврни бўлаклаш. Тезкор саралаш самарадорлиги. Балансланган бўлаклаш. Режа:

1. 
   Тезкор саралаш. Тезкор саралаш тавсифи;
   
2. 
   Массивлврни бўлаклаш;
   
3. 
   Тезкор саралаш самарадорлиги;
   
4. 
   Балансланган бўлаклаш;
   

Тезкор саралаш алгоритми
Тезкор саралаш нафақат ўқитиш учун балки амалиётда ҳам кенг тарқалган саралаш алгоритми. Одатда, тезкор саралаш алгоритмида катта ҳажмдаги қийматларни ҳисоблаш учун мўлжалланган O (n log n) мураккаблик мавжуд. Бу саралаш алгоритми деярли оддий, агар буни англаган бўлсангиз тезкор саралашни ҳам пуфакчали саралаш каби тез ёза оласиз. Бўлиш ва таққослаш стратегияси қўлланилган. Қуйида рекурция қадами тасвирланган.

1.