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

2.2.6. Тез саралаш (QuickSort) усули

Тез саралаш— рекурсив саралаш алгоритмларидан бири ҳисобланади. Тез саралаш рўйхатдан элементни танлаб, у ёрдамида рўйхатни икки қисмга ажратади. Биринчи қисмга танланган элементдан барча кичик элементлар, иккинчи қисмга эса катта элементлар жойлаштирилади. Бу алгоритм Quicksort деб ҳам аталади. Ўрта даражада бу алгоритм самарадор, лекин энг ёмон ҳолда унинг самарадорлиги худди қўйиш ва пуфакча усулларидагидек.

Тез саралаш рўйхатдан ўқ деб аталадиган элементни танлайди, сўнгра рўйхатни шунда қайта тартиблайдики, барча барча ўқдан кичик элементлар ундан олдинда жойлашади, катталари эса ундан кейин ўрнашади. Рўйхатнинг ҳар қайси қисми элементлари сараланмайди. Агар i — ўқ элементнинг охирги ўрни бўлса, у ҳолда биз маълумки, биринчидан то i- 1 ўриндаги қийматлар ўқдан кичик, i + 1 дан N гача қийматлар ўқдан катта. Кейин Quicksort алгоритми ҳар қайси икки қисм учун рекурсив чақирилади. Бир элементли рўйхатда рекурсив чақирилган Quicksort ҳеч нарса қилмайди, чунки бир злементли рўйхат ўзи сараланган.

Алгоритмнинг асосий иши ўқ элементни топиш ва кетма-кет элементларни алмаштиришдир. Quicksort алгоритмининг асосий процедураси икки қисм чегараларини кузатиши керак. калитларни силжиши рўйхатни бўлиш жараёнида амалга оширилади, алгоритмнинг бутун иши рекурсив қайтишда бажарилади.

Тез саралаш алгоритми қуйидагича:

Quicksort(list,first.last)

list сараланадиган элементлар рўйхати

first сараланадиган рўйхат қисмининг биринчи рақами

last сараланадиган рўйхат қисмининг охирги рақами

if first

pivot=PivotList(list,first,last)

Quicksort(list,first ,pivot-1)

Quicksort(list,pivot+1,last)

end if

Расщепление списка

PivotList функцияси ўқ элементни рўйхатнинг биринчи элементи сифатида олади ва pivot кўрсаткични рўйхат бошига ўрнатади. Кейин у рўйхат бўйича ўқ элементни рўйхатнинг қолган элементлари билан солиштириб ўтади. Ўқдан кичик элементга учрагач PivotPoint кўрсаткични орттиради, кейин яна топилган элементни PivotPoint билан алмаштиради. Рўйхат қисми ўқ элемент билан солиштирилгач, рўйхат тўрт қисмга ажралади. Биринчи қисм рўйхатнинг ўқ қийматидан ташкил топади. Иккинчи қисм first+1 ўриндан бошланиб PivotPoint ўринда тугайди ва барча кўрилган ўқдан кичик элементлардан таркиб топади. Учинчи қисм PivotPoint+1 қисмдан бошланиб циклнинг index параметри кўрсаткичида тугайди. Рўйхатнинг қолган қисми ҳали кўрилмаган элементлардан иборат бўлади. Мос бўлишлар 3.4-расмда тасвирланган.

3.4-расм. PivotList алгоритмидаги кўрсаткичлар қийматлари

Мана PivotList алгоритми.

PivotList(list, first,last)

list қайта ишланадиган рўйхат

first биринчи элемент рақами

last охирги элемент рақами
PivotValue=list [first]

PivotPoint=first

for index=first+1 to last do

if list [index]


PivotPoint=PivotPoint+1

Swap(list [PivotPoint] , list [index])

end if

end for

// ўқ қийматни керакли жойга кўчириш

Swap(list [first] , list [PivotPoint] )

return PivotPoint

Энг ёмон ҳолат таҳлили

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 учун,