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

Энг ёмон ҳолат таҳлили
N элементли рўйхатда PivotList процедура чақирилганда у N-1 солиштириш бажаради, яъни PivotValue қиймати барча қолган элементлар билан солиштирилади. Тез саралаш ўзида бўлаклаш ва бошқариш шаклидаги алгоритмни намоён қилади, шунинг учун энг яхши ҳолда PivotList бир хил ўлчамли иккита қисм тузади. Унда энг ёмон ҳолда рўйхатлар ўлчами максимал тенг бўлмаслиги керак. Рўйхатлар ўлчамининг энг катта фарқига PivotValue нинг қиймати рўйхатнинг барача қолган элементларидан ё катта ёки кичик бўлганда эришилади. Бу ҳолда рўйхатлардан бирида ҳеч қандай элемент бўлмайди, бошқасида эса N - 1 элемент бўлади. Агар бундай вазият барча рекурсив чақирилишларда содир бўлса, унда ҳар сафар битта элемент (PivotValue) ўчирилиши юз беради. Бу шуни билдирадики, солиштиришлар сони қуйидаги формула орқали берилади

Элементларнинг қандай дастлабки тартиби бундай натижага олиб келади? Агар ҳар бир ўтишда биринчи элемент танланса унда бу элемент энг кичик (ёки энг катта) бўлиши керак. Сараланган рўйхат энг ёмон саралашга олиб келади. Юқорида кўрган саралаш алгоритмларида энг ёмон ва ўртача ҳолатлар нисбатан яқин қийинликка эга эди. Тез саралаш усули учун эса бундай эмас.
Ўртача ҳол таҳлили
Эслатиб ўтамиз, Шелл усули таҳлили ҳар бир солиштириш натижасида йўқоладиган инверсиялар сонига асосланган эди. Биз шунда пуфакча ва қўйиш усуллари ўртача ҳолда ўзларини ёмон тутишини, яни ҳар бир солиштиришда биттадан инверсия йўқотишини белгилагандик.
Тез саралаш инверсияларни қандай йўқотади? PivotList алгоритми ишлайдиган N элементдан иборат рўйхатни қараймиз. Фараз қиламиз PivotValue рўйхатнинг қолган барча элементларидан катта бўлсин. Бу шуни кўрсатадики, процедуранинг бажарилиш охирида PivotPoint нинг қиймати N га тенг ва шу туфайли ўзгарувчи PivotValue рўйхатнинг биринчи элементини эмас, балки охирги элементини кўрсатади. Рўйхатнинг охирги элементи унинг энг кичиги бўлиши мумкин. Шу сабабли бу икки қийматнинг алмаштирилиши энг катта элементни биринчи ўриндан охирги ўринга, энг кичигини эса–охиридан бошига жўнатади. Агар энг катта элемент биринчи турса, у ҳолда у рўйхатнинг бошқа элементлари билан N-1 инверсияга киради, охирида турган энг кичик элемент ҳам рўйхатнинг бошқа элементлари билан N-1 инверсия ташкил қилади. Шундай қилиб, чегаравий икки элементлар алмашинуви 2N - 2 ин­версияларни йўқотади. Айнан мана шу сабаб туфайли тез саралашнинг ўртача ҳоли энг ёмон ҳолидан тубдан фарқ қилади.
PivotList алгоритми ишнинг асосий қисмини бажаради, шунинг учун ўртача ҳол таҳлилини ундан бошлаймиз. Дастлаб PivotList алгоритми бажарилгандан сўнг N ўриндан исталган бири PivotValue ни сақлаши мукинлигини белгилаймиз.
Ўртача ҳол таҳлили учун бу ҳар бир имкониятларни қараймиз ва натижаларни ўртача кўрсатамиз. Энг ёмон ҳолат таҳлилидан кўрдикки, PivotList процедураси N элементли рўйхатни бўлишда N-1 солиштириш бажаради. Бу рўйхатларни бирлаштириш ҳеч қандай ҳаракат талаб қилмайди. Ниҳоят, қачонки PivotList Р қиймат қабул қилса, Р-1 ва N - Р узунликдаги рўйхатларда Quicksort процедураси рекурсив чақирилиши юз беради. Бизнинг ўртача ҳолдаги таҳлилимиз N нинг барча Р имкониятларини ҳисобга олиши керак. Охир оқибат рекуррент муносабатга эга бўламиз
N>2 учун,
А(1)=А(0)=0.
Агар йиғиндига диққат билан қарасак, унда биринчи қўшилувчи аргументи 0 дан то N-1 қийматлардан ўтади, иккинчи қўшилувчи аргументи эса— худди шундай қиймат, фақат камайиш тартибида.
Бу шуни кўрсатадики, ҳар бир А(i) қўшилувчилардан бири йиғиндида икки марта учрайди ва формулани соддалаштириш мумкин:
учун
А(1) =А(0) = 0.
Бундай шаклдаги муносабат жуда мураккаб кўринади. Бу мураккабликни икки усул билан бартараф этиш мумкин. Биринчи усул ўзининг тайёргарлигидан фойдаланиб, тўғри формулани қидириб топиш ва кейин у рекуррент муносабатни қаноатлантиришини исботлаш керак. Иккинчи усул икки формулага биргаликда қарашни таъкидлайди: A(N) ва A(N - 1) лар учун. Бу икки ифода айрим аъзолари билан фарқ қилади.
Касрлардан қутулиш учун A(N)·N ва A(N–1)·(N–1) ларни ҳисоблаймиз.
Ҳосил қиламиз

Иккинчи тенгликдан учинчи тенгликни айирамиз ва айрим соддалаштиришлар бажариб, ҳосил қиламиз

Охирги тенгликнинг ҳар иккала қисмига A(N–1) • (N–1) ни қўшилиши қуйидагни беради

бундан якуний рекуррент муносабатни келтириб чиқарамиз

A(1) = А(0) = 0.
Уни ечиш қийин эмас ва етарлича таҳлил тенгликни беради. Шундай қилиб тез саралаш алгоритмининг ўртача қийинлиги га тенг.