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

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