O’zbekiston Aloka va Axborotlashtirish agentligi

Тез саралаш. О(n log n) вақтда бажариладиган, ички саралаш усулларининг энг самарадори бўлиб ҳисобланган тез тартиблашни кўриб чиқамиз. Бу алгоритмда массивнинг А[1],...,А[n] элементларини тартиблаш учун бу элементлардан массив элементлари унга нисбатан тартибланадиган таянч элемент сифатида v калитнинг қандайдир қиймати танланади. Қулайлик учун, таянч элемент сифатида калит қийматлари тақсимотининг медианага энг яқин бўлганини танлаб олиш зарур. Чунки, таянч элемент калит қийматларини деярли тенг икки қисмга ажратади.
Кейин массив элементлари шундай жойлаштириладики, қандайдир j индекс учун барча A[1], ..., А[j] келтирилган элементлар υ дан кичик калит қийматларга, А[j+1], ..., А[n] барча элементлари υ га тенг ёки катта калит қийматларга эга бўлади. Кейин тез тартиблаш процедураси A[1], .... А[j] ва A[j+1], ..., А[n] элементлар тўпламига бу тўпламларни алоҳида тартиблаш учун рекурсив ишлатилади. Биринчи тўпламнинг калит қийматлари иккинчи тўпламнинг калит қийматларидан кичик бўлгани учун бошланғич массив тўғри тартибланади.

1-расм. Тез тартиблаш алгоритми этаплари.

Мисол. 8.1-расмда 3, 1, 4, 1, 5, 9, 2, 6, 5, 3 бутун сонлар кетма-кетлиги устида бажариладиган тез тартиблаш алгоритмининг бажарилиш қадамлари келтирилган. Ҳар бир қадамда υ нинг қиймати энг чапдаги турли хил иккита элемент-соннинг каттаси сифатида танланади. Тартиблаш процедурани рекурсив чақириш жараёнида алоҳида қисм тўпламлар бир хил калитдан ташкил топганда тугатилади. 1-расмда ҳар бир этап икки қадамда кўрсатилган: аввал ҳар бир алоҳида қисм тўплам учун ўзининг қиймати танланади ва кейин бу қисм тўпламнинг элементлари танланган қийматга мос равишда жойлаштирилади, ва худди шундай тартиблаш процедураси рекурсив ишлатиладиган яна иккита қисм тўпламга бўлинади.

Энди quicksort процедурасидан ташқарида аниқланган А массив элементлари билан ишлайдиган quicksort рекурсив процедурасини ишлаб чиқишни бошлаймиз. Quicksort(i,j) процедураси А[1], ..., А[n] элементларни тартиблаши керак. Бу процедуранинг алгоритми 8.2-дастурда киритилган.
8.2-дастур. Тез тартиблаш усули процедураси
(1) if A[i], ..., A[j] иккита турли хил калитларга эга бўлса then begin
(2) v — топилган иккита турли хил калитларнинг каттаси бўлсин;
(3) А[х], ..., A[j] элементлар шундай жойлаштириладики, қандайдир k, i+l(4) quicksort{i, k-1) ,-
(5) quicksort{к, j)
end
Энди тез тартиблаш алгоритмининг эскизини (8.2-дастур) ҳақиқий quicksort дастурига айлантирамиз. Бу дастурнинг коди 8.3-дастурда келтирилган. аггау[1..n] of recordtype туридаги А массивни саралаш учун quicksort(l, n) процедурасини чақириш керак.
8.3-дастур. Тез тартиблаш усули процедураси
procedure quicksort ( i, j: integer );
{А ташқи массивнинг A[i],...,A[j] элементларини тартиблайди}
var
pivot: keytype;
pivotindex: integer;
{калити pivot га тенг бўлган А массив элементи}
к: integer;
{калит>pivot бўлган элементлар гуруҳининг бошланғич индекси}
begin
(1) pivotindex:= findpivot{i, j) ;
(2) if pivotindex <> 0 then begin
{агар барча калитлар тенг бўлса, ҳеч нарса бажариш керак эмас}
(3) pivot:= Alpivotindex] .key;
(4) к:= portition(i, j, pivot);
(5) quicksortd, k-1) ;
(6) quicksort{k, j)
end
end; {quicksort}
Ўрта ҳолатда k-тартибли статистикани топиш учун тез тартиблаш усулига асосланган процедурани рекурсив ишлатилади. Бу процедурани select (танлаш) деб номлаймиз. select(l, j, k) процедураси қандайдир катта А[1], ..., А[n] массивдан олинган A[i], ..., A[j] элементлар орасидан k – элементни топади. select процедураси қуйидаги ҳаракатларни бажаради.
1. Таянч элементни танлаш, масалан υ.
2. partition процедурасини ишлатиб, A[i], ..., A[j] элементларни икки гуруҳга бўлиш. Биринчи A[i], ..., А[m-1] гуруҳда барча ёзувларнинг калит υ дан кичик, иккинчи А[m], ..., A[j] гуруҳда—υ га тенг ёки катта.
3. Агар k≤m-i бўлса, у ҳолда k-элемент биринчи гуруҳда жойлашади ва унга яна select(i, m-1, k) процедураси қўлланилади. Агар k>m-i бўлса, у ҳолда select(m, j, k-m+ i) процедураси чақирилади.
Бир хил қийматлардаги калитларга эга бўлган A[i], ..., A[j] элементлар учун select(i, j, k) процедураси эртами-кеч чақирилади (ва шунинг учун i=j бўлади). Бу элементларнинг калитлари изланаётган k-тартибли статистика қиймати бўлади.
Тез тартиблаш усулидагидек, select процедураси энг ёмон ҳолатда Ω(n²) дан кам бўлмаган вақт талаб қилади. Масалан, агар энг кичик элементни топишда таянч элемент сифатида ҳар доим калит қийматларидан энг каттасини олиш керак, у ҳолда бу процедура учун бажарилиш вақти О(n²) тартибда бўлади. Лекин ўрта ҳолатда select процедураси тез тартиблаш алгоритмига нисбатан тез ишлайди, ўртача у О(n) вақтда бажарилади. Бу алгоритмлар орасидаги фарқ шундан иборатки, тез тартиблаш процедураси икки марта чақирилганда, select процедураси бир марта чақирилади. Select процедурасининг таҳлили тез тартиблаш процедурасининг таҳлилидек бўлади. Бу процедура аввалги қадамда чақирилган тўпламнинг бир қисми бўлиб ҳисобланган қисм тўпламда ўзини такроран чақиради. Бу процедуранинг ҳар бир чақирилиши процедуранинг аввалги чақирилиши амалга оширилган тўпламнинг 9/10 қисмидан иборат бўлган элементлар тўпламида амалга оширилади. У ҳолда, агар Т(n) орқали n та элементдан иборат тўпламда select процедурасига кетган вақтни белгиласак, қандайдир ўзгармаслар учун қуйидагиларга эга бўламиз:
Т(n)≤Т(9/10* n) + сn (8.14)
(8.14) Т(n) = О(n) тенг бўлишини кўрсатиш қийин эмас.
Тартибли статистикани топишнинг чизиқли усуллари. Select процедурасида ёмон ҳолатда бажарилиш вақти О(n) тартида бўлишини кўрсатиш учун чизиқли вақтда шундай таянч элементни танлаш керакки, ўлчами бошланғич тўпламнинг фиксирланган қисмидан катта бўлмаган иккита қисм тўпламга бўлинсин. Масалан, (8.14) тенгсизликни ечиш шуни кўрсатадики, агар таянч элемент (n/10)- тартибдаги элементдан кичик бўлмаса ва (9n/10)-тартибдаги элементдан катта бўлмаса 9/10 бошланғич тўпламдан ошмайдиган қисм тўпламларга бўлади, бу эса энг ёмон ҳолатда алгоритм чизиқли вақтда бажарилишини кафолатлайди.
«Яхши» таянч элементни қуйидаги икки қадам воситасида топиш мумкин.
1. n та элементни бошқа гуруҳга кирмаган 1-4 элементлар четга қўйиб, 5 та элементдан иборат гуруҳларга бўлиш. 5 та элементдан иборат ҳар бир гуруҳ ўсиш тартибида ихтиёрий алгоритм билан тартибланади ва ҳар бир гуруҳдан ўртача элемент олинади. Бундай ўртача элементлар жами бўлиб [n/5] бўлади.
2. select процедураси ишлатилиб, ўртача элементларнинг медианаси топилади. Агар [n/5] жуфт бўлса, ўртачага яқин бўлган элемент олинади. Ихтиёрий ҳолатда ўртача элементларнинг тартибланган рўйхатидаги [(n+5)/10] позицияда турган элемент топилади.
дастур. к- тартибли статистикани топишнинг чизиқли алгоритми
function select (i, j, к: integer ): keytype;
{ Функция А[i], ..., A[j] дан k- элементнинг калит қийматини қайтаради}
var
m: integer; {индекс сифатида ишлатилади }
begin
(1) if j-i<74 then begin
(2) A[i], ..., A[j] ни тартиблаш оддий алгоритм билан;
(3) return(A[i+k-1].key)
end
else begin { select рекурсив ишлатилади}
(4) for m:= 0 to (j-i-4) div 5 do
{5-та элементдан иборат гуруҳда ўртача элементларни топиш}
(5) гуруҳда катталиги бўйича 3-бўлган элементни топиш
A[i+5*m], ..., A[i+5*m+4] ва
уни с A[i+m] билан ўрнини алмаштириш;
(6) pivot:= select(i, i+(j-i-4) div 5,(j-i-4) div 10);
{ўртача элементларнинг медианасини топиш}
(7) m:= partition(i, j, pivot);
(8) if к<=m-i then
(9) return(select(i, m-1, k) )
else
(10) return(select(m, j, k-(m-i)))
end
end; { select }


Хулоса
Massiv - bu bitta turga mansub bir nechta o’zgaruvchilar to’plami. TYPE turidagi LENGTH ta yelementdan iborat a nomli massiv shunday ye’lon qilinadi: