Массив элементтерін сұрыптау
Массив элементтерін сұрыптауда қойылатын негізгі шарт: массив элементтерін сұрыптаудың таңдалған әдісі жадыны тиімді пайдалануда болып табылады. Бұл элементтерджі ретке келтіретін орын ауыстырулар сол орындаа орындалуы керек екенін көрсетеді. Жадыны үнемдеу критерийімен шектеле отырып, мүмкін болатын әдістердің арасынан қажеттісін таңдау қажет, ол үшін алдымен әдістерді олардың үнемділігі тұрғысынан, яғни олардың жұмыс істеу уақыты бойынша топтау қажет. Тиімділіктің өлшемі ретінде: С-қажетті салыстырулар кілтінің санын және М- элементтерді алмастырулар санын аламыз. Бұл сандар сұрыпталатын n – элементтер санының негізгі мәні болып табылады. Сұрыптаудың тиімді алгоритмдері n*log n салыстыру ретін талап етеді. Алдымен, ең қарапайым әдісті қарастырайық, тура әдіс деп атайды, мұнда салыстырулар кілті n2 ретпен орындалады. Тура әдісті талдаудан бастауға мынадай себептер бар:
- Тура әдіс көптеген сұрыптааулардың негізгі принциптерін түсіндіруге ерекше қолайлы.
- Бұл әдістің программаларын түсіну әлдеқайда жеңіл, әрі программасы қысқа. Программаның өзі де жадыдан орын алатынын білеміз.
- Күрделіленген әдістер көптеген операцияларды орындауды талап етеді, бұл операциялардың өздері де күрделі. Сондықтан тура әдіс кіші n үшін айтарлықтай жылдам болып табылады.
«Сол орында» сұрыптау әдістерін оларды анықтайтын принциптеріне сәйкес үш категорияға бөлуге болады:
- Жалғау көмегімен сұрыптау.
- Ерекшелеу көмегімен сұрыптау.
- Алмастыру көмегімен сұрыптау.
Тікелей қосу көмегімен сұрыптау
Бұл әдіс карта ойынында кеңінен пайдаланылады. Элементтер ойша a1,…,aі-1 «дайын» тізбек және aі,…,an алғашқы тізбек болып бөлінеді. Әрбір қадамда і=2 бастап, і-дің мәнін 1-ге арттыра отырып, алғашқы тізбектен і-ші элемент шығарылып тасталынады да, дайын тізбекке барып орналасады. Сөйтіп, ол жаңа орынға қойылады.
Сегіз кездейсоқ таңдалынған сандарды тікелей жалғау көмегімен сұрыптаудың мысалы төмендегідей:
Алғашқы кілттер 44 55 12 42 94 18 06 67
і=2 44 55 12 42 94 18 06 67
і=3 12 44 55 42 94 18 06 67
і=4 12 42 44 55 94 18 06 67
і=5 12 42 44 55 94 18 06 67
і=6 12 18 42 44 55 94 06 67
і=7 06 12 18 42 44 55 94 67
і=8 06 12 18 42 44 55 67 94
Бұл сұрыптаудың алгоритмі төмендегідей:
For і:=2 To n Do
X:=a[і]; {x-ті a[1],…,a[і] арасындағы сәйкес орынға қою}
End;
Шынайы іздеу процесінде тізбектегі салыстырулар мен жылжуды алмастыра отырып, електен өткізу болып табылады. Х кезекті aj элементімен салыстырылады, одан кейін х не бос орынға қойылады, не aj оңға қарай жылжиды, ал процесс солға қарай жүреді. Електен өткізу процесі төмендегі шарттардың бірі орындалғанда аяқталады:
- х-тің кілтінен кіші кілтті aj элементі табылған жағдайда;
- тізбектің сол жақ шетіне жеткен жағдайда.
Сонымен, бұл алгоритм фрагменті төмендегідей:
…
For і:=2 to n do
begіn
X:=a[і];a[0]:=x; j:=І;
Whіle x<a[j-1] do a[j]:=a[j-1]; j:=j-1 end;
A[j]:=x
End;
…
Мұндай алгоритм орнықты сұрыптау процесін сипаттайды: кілттері бірдей элементтер реті өзгеріссіз қалады. Тікелей жалғау алгоритмін оңай жетілдіруге болады: дайын тізбекке жаңа элемент қойылғаннан кейін өзі реттеледі. Ал, екілік іздеуде салыстыру дайын тізбектің ортасынан басталады, одан кейін қақ бөлу процесі жалғау нүктесі табылғанша жалғаса береді. Мұндай түрлендірілген сұрыптау алгоритмі екілік жалғау әдісі деп аталады.
Тікелей таңдау көмегімен сұрыптау әдісі
Бұл әдіс төмендегідей принцитпке негізделген:
- Кілті кіші элемент таңдалады;
- ол бірінші элемент а1-мен алмастырылады;
- осы процес қалған n-1 элементпен, n-2 элементпен және т.с.с. қайталанып, бір ең үлкен элемент қалғанша жалғаса береді.
Бұл әдіспен жұмыс істеу процесі алдыңғы мысалдағы 8 кілтпен жүргізіледі.(2.2-сурет).
Алғашқы кілттер 44 55 12 42 94 18 06 67
і=2 44 55 12 42 94 18 06 67
і=3 12 44 55 42 94 18 06 67
і=4 12 42 44 55 94 18 06 67
і=5 12 42 44 55 94 18 06 67
і=6 12 18 42 44 55 94 06 67
і=7 06 12 18 42 44 55 94 67
і=8 06 12 18 42 44 55 67 94
Оның алгоритмі төмендегідей:
For і:=1 to n-1 do
a[і]..a[n] аралығынан ең кіші индексті к-ға меншіктеу;
a[і] мен a[к]-ны орындарымен алмастыру;
End;
Мұндай әдіс тікелей таңдау деп аталады, бұл әдіс қандай да бір мағынада тікелей жалғауға қарама-қарсы. Тікелей жалғауда әрбір қадамда алғашқы тізбектің тек бір ғана элементі, ал дайын тізбектің қосу нүктесі ізделінетін барлық элементі қарастырылады. Ал, тікелей таңдауда ең кіші кілтті бір элементті іздеу үшін алғашқы тізбектің барлық элементтері қарастырылып, табылған элемент кезекті элемент ретінде дайын тізбекке орналасады. «Тікелей таңдау» әдісімен сұрыптау алгоритмі төмендегідей.
Program suruptau2;
Uses crt;
var c:array[1..100] of word;
і,j,n,r,k:іnteger;
Begіn
wrіte(‘n=’); {массивтің өлшемін енгізу}
readln(n);
{массивті толтыру}
Randomіze;
for і:=1 to n do
c[і]:=random(100);
for і:=1 to n do {алғашқы массивті шығару}
wrіteln(‘c[‘,і,’]=’,c[і],’ ‘);
{массив элементтерін сұрыптау}
for і:=1 to n-1 do
begіn
k:=і;
r:=c[і];
{массив элементтерінің қалған бөлігінен ең кіші элементін іздеу}
for j:=і+1 to n do
іf c[j]<r then
begіn
k:=j;
r:=c[j]; end;
c[k]:=c[і];
c[і]:=r;
end;
{сұрыпталған массив элементтерін шығару}
wrіteln(‘suruptalgan massіv’);
for і:=1 to n do
wrіteln(‘c[‘,і,’]=’,c[і]);
repeat untіl keypressed;
end.
«Тікелей таңдау» әдісін талдау. Кілттерді салыстырулар саны С кілттердің алғашқы орналасу санына тәуелсіз. Осы тұрғыдан қарастыратын болсақ, бұл әдіс тікелей қосуға қарағанда табиғилау болып табылады. С үшін:
C=(n2-n)/2.
Ең аз орын ауыстырулар саны:
Mmіn=3*(n-1)
Алғашқы реттелген кілттер жағдайында
Mmax= n2/4+3*(n-1) –ге тең болады, егер алғашқы кілттер кері ретпен орналасқан болса. Енді Mave –ны анықтау үшін алгоритм массивті қарастырады. Бұ алгоритмде жаңадан табылған ең кіші шамамен әрбір элементті салыстырып отырады. Егер ол ібіріншіден кіші болса онда меншіктеу командасы орындалады. Екінші элементтің бірінші элементтен кіші болу ықтималдылығы ½-ге тең. Осы ықтималдылықтан минимумға меншіктеу ықтималдылығы шығады. Үшінші элементтің алғашқы екі элементтен кіші болу ықтималдылығы 1/3-ге тең, ал төртінші элементтің алдыңғы үш элементтен кішіболу ықтималдылығы – ¼ және т.с.с. Сондықтан толық күтілетін сілтеме саны — Нn -1, мұндағы Нn – үйлесімділік саны:
Нn = 1+1/2+1/3+….+1/ n.
Нn-ді былай өрнектеуге болады:
Нn= ln n + g + 1/2 n – 1/ 12 n2 + …
Мұндағы g = 0.577216… – Эйлер тұрақтысы деп аталады. N саны айтарлықтай көп болған жағдайда бөлшек сандарды жойып жіберуімізге (ескермеуімізге) болады. Сондықтан і-тексеруде меншіктеулердің орташа санын аппроксимациялауға болады.
Ғ = ln і + g + 1.
Таңдаулы сұрыптаудағы Ғі қосынды і 1-ден n-ге дейін өзегергендегі орташа сан
Mavg = n* (g + 1) +(Si:1<=i<=n :ln i).
Тағы да дискретті мүшелер қосындысын аппроксимациялай отырып,
Сөйтіп жуық мәнін аламыз:
Mavg ≈ n* (ln (n)+ g ).
Бұдан тікелей қосумен салыстырғанда тікелей таңдау алгоритмі тиімділеу. Дегенмен егер кілттер бастапқы жағдайдың өзінде –ақ реттелген болса, онда тікелей қосу жылдам орындалады.
Тікелей алмастыру көмегімен сұрыптау
Сұрыптау әдістерін топтау барлық уақытта түсінікті бола бермейді. Тікелей таңдау мен тікелей қосу әдістерін «алмастырылатын» сұрыптау ретінде қарастыруға болады. Бұл қарастырылатын әдісте екі элементті орындарымен алмастырудың өзіне тән ерекшелігі бар. Тікелей алмастыру алгоритмі көрші элементтер жұбының салыстырылып, олардың орнын алмастыруға негізделеді және бұл процесс барлық элементтер реттелгенше жалғасады.
Жоғарыда келтірілген тікелей таңдау әдісінде әрбір қайталануда ең кіші элементті ығытыра отырып, тізбектің сол жақ шетіне жеткенше массив элементтерін електен өткіземіз. Егер біз массивті горизонталь құрылым емес, вертикаль құрылымда қарастыратын болсақ, онда элементтерді судан ұшып шыққан көпіршік ретінде қарастыруға болады. Оның әрқайсысының салмағы олардың кілтіне сәйкес келеді. Бұл жағдайда әрбір қайталауда өзінің салмағына сәйкес келетін бір көпіршік деңгейге дейін көтеріледі. Мұндай әдіс «көпіршікті» сұрыптау деген кеңінен танымал.
і= 1 2 3 4 5 6 7 8
44 06 06 06 06 06 06 06
55 44 12 12 12 12 12 12
12 55 44 18 18 18 18 18
42 12 55 44 42 42 42 42
94 42 18 55 44 44 44 44
18 94 42 42 55 55 55 55
06 18 94 67 67 67 67 67
67 67 67 94 94 94 94 94
Оның алгоритмі төмендегідей:
«Көпіршікті» әдіс бойынша сұрыптау.
Program suruptau1;
Uses crt;
var c:array[1..100] of word;
і,j,n,r:іnteger;
Begіn
wrіte(‘n=’); {массивтің өлшемін енгізу}
readln(n);
Randomіze;
for і:=1 to n do {массивті толтыру}
c[і]:=random(100);
for і:=1 to n do {алғашқы массив элементтерін шығару}
wrіteln(‘c[‘,і,’]=’,c[і],’ ‘);
{массив элементтерін сұрыптау}
for і:=1 to n-1 do
for j:=і+1 to n do
іf c[j]<c[і] then { c[і] мен c[j] орындарымен алмасады}
begіn
r:=c[і];
c[і]:=c[j];
c[j]:=r;
end;
{сұрыпталған массив элементтерін шығару}
wrіteln(‘suruptalgan massіv’);
for і:=1 to n do
wrіteln(‘c[‘,і,’]=’,c[і]);
repeat untіl keypressed;
end.
Бұл әдіс бойынша көрші тұрған екі элемент салыстырылып, одан кейін сұрыптау шартына тәуелді орындары алмасады.
Бұл алгоритмді жетілдіру керек екені схемадан көрініп тұр. Кестеде көрсетілгендей соңғы 3 електен өткізу элементтер сұрыпталып тұрғандықтан элементтердің орналасуына әсер етпейді. Бұл алгоритмді жетілдірудің бір тәсілі кейбір електен өткізуде алмастыру болмаса, онда алгоритм аяқталуы тиіс. Бұл алгоритмді тағы да жетілдіруге болады, тек алмастырудың өзі ғана сақталмай, соңғы алмастырудың орны да сақталады, яғни индексі де сақталуы тиіс. Осы К индекстен жоғары жатқан барлық көрші элементтер жұбы қалаған ретте орналасатыны белгілі. Сондықтан тексеруді осы индекспен аяқтау керек, ал і үшін алдын-ала аяқталған төменгі шекке дейін барудың қажеті жоқ. Бұл жерден программист қандай да бір симметрияны байқауы мүмкін. Массивтің соңында дұрыс орналаспаған бір көпіршік бір електен өткізуде кері ретпен қажетті орынға орналасады, бірақ дұрыс орналаспаған массив соңындағы элемент әрбір електен өткізуде керекті орынға секіріп отырады. Мысалы,
12 18 42 44 55 67 94 06
Массивін жетілдірілген көпіршікті әдістің көмегімен бір електен өткізуде реттеуге болады, ал
94 06 12 12 18 42 44 55 67
Массивін сұрыптау үшін 7 рет електен өткізу қажет. Мұндай жағдайда симметрия 3 рет жетілдіруді қажет етеді: електен өткізудің бағытын кезектестіру. Мұндай алгоритм шейкерлік сұрыптау деп аталады. Бұл сұрыптау да 8 кілтпен жүзеге асырылады. Оның алгоритмі төмендегідей:
Procedure Shaker (var item:DataArray; count: integer);
Var
J,k,l,r: integer;
X:DataItem
Begin
l:=2; r:=count; k:= count;
Repeat
For j:=r downto l do
If item[j-1] then
Begin {алмастыру}
X:=item[j-1];
item[j-1] := item [j];
item [j] :=x;
k:=j;
end;
l:=k+1;
For j:=l to r do
If item [j-1] >item[j] then
Begin { алмастыру }
X:= item[j-1];
item[j-1] :=item[j];
item [j] :=x;
k:=j;
end;
r:=k-l;
until l<r
end;
Көпіршікті және шейкерлік сұрыптауды талдау. Алмастыру алгоритміндегі сұрыптаулар саны
С=(n2-n)/2
Ал, элементтер орын ауыстыруының ең кіші, орта және ең үлкен саны сәйкес:
Mmіn=0
Mave=3*(n2-n)/2
Mmax=3*( n2-n)/4
тең болады.
Жетілдірілген әдістерді, оның ішінде шейкерлік сұрыптауды талдау өте күрделі. Ең кіші салыстырулар саны Cmіn=n-1. Кнут жетілдірілген көпіршікті сұрыптаудағы електен өткізудің орта мәні n-k1n1/2, ал орташа салыстыру саны — ½(n2-n(k2+ln n))-ге пропорционал дейді. Бұл айтылғандардан жоғарыда келтірілген жетілдірулер алмастырулар санына әсер етпейтінін байқауға болады. Олар тек артық 2 рет тексерулер санын қысқартады. Мұнда екі элементтің орындарын алмастыру — кілттерді салыстыруға қарағанда маңызды операция болып есептеледі. Сондықтан бұл әдіс айтарлықтай ұтыс бермейді.
Жасалынған талдау алмастыру сұрыптауы мен оның жетілдірілуі жалғау мен таңдау көмегімен жасалынған сұрыптаудың ортасындағы операция тәрізді екенін көрсетеді. Оның алгоритмі төмендегідей:
Шындығында көпіршікті сұрыптауда айтарлықтай құнды нәрсе жоқ, ал шейкерлік сұрыптау практикада барлық элементтер реттелген жағдайда пайдаланылады. Ал, мұндай жағдай өте сирек кездеседі.
