Арапайым айырбастау әдісі

Қ арапайым таң дау ә дісі арқ ылы сұ рыптау кез келген массивке қ олдануғ а болады. Ә діс массивті жоғ арыдан тө мен тізбектеп қ арау арқ ылы орындалады жә не кө рші элементтердің орынын ауыстырады, I< j, а a[I]> a[j].

Алғ ашқ ы екі жұ п элементтер a[1] жә не a[2] қ арастырамыз, егер бірінші элемент екіншісінен ү лкен болса, онда орындарын ауыстырамыз, басқ а жағ дайда ө згеріссіз қ алдырамыз. Сосын екінші жұ п элементтерін a[2] жә не a[3] қ арастырамыз. Егер a[2] > a[3], онда орын ауыстырамыз жә не т.с.с. Бірінші қ адамда I ү шін 1 ден n-1-ге дейінгі a[I] жә не a[I+1] массивінің элементтерінің барлық жұ птары тексеріледі. Нә тижесінде массивтің ең ү лкен элементі массив соң ына қ ойылады. Ең ү лкен элемент ө з орынында тұ рғ андық тан, массивтің бө лігін онсыз қ арастырамыз, яғ ни (n-1)-ші элементке дейін. Тура алдың ғ ы сияқ ты қ айталаймыз. Бұ л жағ дай қ ашан кезекті массив бө лігінің элементтері екіге дейін азайғ анша жалғ аса береді. Бұ л жағ дайда соң ғ ы салыстыруды орындаймыз жә не соң ғ ы екі элементті реттейміз. Сұ рыптау кезінде массивті N-1 рет кө реміз, сосын барып массив сұ рыпталады.

Кө піршік ә дісінін сұ рыптау анализі.

Қ арапайым ауыстыру алгоритмінде салыстырулар саны мынағ ан тең:

Орын ауыстырулардың (элементтер игеру) минималды, орташа жә не максималды мө лшері мынағ ан тең:

Тез сұ рыптау ә дісі

Кірістіру жә не таң дау принципіне негізділген сұ рыптаудің жетілген екі ә дісін айтып болғ аннан соң, біз ауыстыру принципіне негізділген жақ сартылғ ан ә дісті ең гізіміз. Сұ рыптау кө піршік ә дісімен орташа шамада қ арапайым сұ рыптаудің ү ш алгоритімінің арасында ең кемді нә тижесі болғ анын ескере отырып, біз едә уір жақ саруды талап етуіміз керек. Ө те жақ сы деген мінездемеге ие болғ ан. Оны ойлап тапқ ан К. Хоор оны тез сұ рыптау деп атағ ан.

Жетістіктің ең жоғ ары дә режесін элементтерді ү лкен аралық та жасау дұ рыс болар еді. Тез сұ рыптау бұ л фактіге сү йенеді. Бізге кері тә ртіпке орналасқ ан n элемент кілтпен берілді деп елестейік. Барлығ ы n/2 ауыстыруды орындай отырып, оларды сұ рыптауғ а болады, бірақ егер де ең алдымен ең сол жә не ең оң элементтерді орынмен ауыстыра отырып, ептеп екі шеттен ортасына жылжытса ғ ана. Ә рине бұ л, элементтер кері тә ртіппен орналасқ ан жағ дайда ғ ана мү мкін екені бізге белгілі. Бірақ бұ л мысал бізді басқ а ойғ а салады.

Келесі алгоритмді қ арастырып кө рейік: кездейсоқ тү рде бір элементті (оны х деп атайық) алып, массивін кө ріп, а_і > х элементін таппағ анғ а дейін солдан онғ а қ арай жылжимыз. Содан соң а_і < х элементін таппағ анғ а дейін, оны оннан солғ а қ арай қ арап шығ амыз. Енді осы екі элементті орындарымен ауыстырамыз жә не «ауыстырумен қ арап шығ у» ү рдісін жалғ астырамыз. Екі рет қ арап шығ уда массивтің ортасында кездеспейді. Нә тижесінде массив екіге бө лінеді: солғ а - х-ке қ арағ анда ә р кемімен, жә не онғ а – кілтпен ү лкен х-пен. Енді бұ л бө ліну ал/горитмін бағ дарламасындағ ы дай процедура тү рінде жазып аламыз. > жә не < қ атынасы ≥ жә не ≤ - қ а ауыстырылды. Оның мойындамауы оператордың циклында бұ л < жә не > деген сө з басысымен осындай орын ауыстыруда кө рініс ү шін х курьер ретінде қ ызмет етеді.

procedure partition;

var w, x: item;

begin

i: = l;

j = n;

{кездейсоқ х элементті таң дау}

repeat

while a [ i ]. key < x. key do i = i + 1;

while x. key < a [j ]. key do j = j - 1;

if i ≤ j then begin

w: = a [ i ];

a [i ]: = a [j ];

a [j ]: =w;

i: = i +1;

j: = j – 1

end

until i > j

end

Мысалы, егер де

44 55 12 42 94 06 18 67,

кілттердің массивінен 2-ге тең болатын х ретінде орташа кілтті таң дайтын болсақ, онда массивті бө лу ү шін і = 5 жә не j =3 индекстің негізгі мә ніне екі таң дау талап етіледі.

a[i], …, а[і – 1] кілті кем немесе х = 42 кілтіне тең, a[j + 1],..., a[n] кілті артық немесе х-ке тең. Сондық тан біз екі массивті алдық

ak. key ≤ x. key k = 1,..., i – 1

ak. key ≥ x. key k = j + 1,..., n

ал кейін,

ak. key = x. key k = j +1,..., i – 1 алдық.

Бұ л алгоритм ө те қ арапайым жә не нә тижелі, ө йткені і, j жә не х салыстырмасында қ атысатып негізгі шамасын қ арағ ан уақ ытта тез регистрда сақ тауғ а болады. Бірақ ол n/2 ауысып орындалатын, n бірдей кілті бар мысалдағ ыдай қ олайсыз болуы мү мкін. Бұ л қ ажетсіз ауыстыруда онай алып тастауғ а болады. Кө рудің операторын келесімен орын басуғ а болады.

while a [ i ]. key ≤ x. key do i: = i +1;

while x. key ≤ a [ j ]. key do j: = j - 1;

Бірақ онда массивта орналасқ ан, салыстыру алынғ ан х элементі екі ә ртү рлі бағ ытталғ ан кө ру ү шін барьер ретінде қ ызмет етуін тоқ татады. Массивта барлық кілттер бірдей болғ ан жағ дайда аяқ таудың кү рделі шарттарын қ олданбаса кө рулер шектен шығ ып кетеді. Келтірілген процедурадағ ы шарттардың қ арапайымдылығ ы артық ауыстыруды ақ тайды. Дегенмен ол «кездейсоқ» массивтар ү шін орташа шамасында айтарлық тай сирек болады. Бірақ ү лкен емес экономиканы і ≤ j – пен бірге i < j ауыстыруда басқ аратын шартты ө згерте отырып алуғ а болады. Дегенмен бұ ндай ө згерісті

i: = i + 1; j: = j – 1

оператордың ауыстыруына таратуғ а болмайды. Сондық тан ә ртү рлі шарттарды қ олдану талап етіледі. і ≤ j шартының қ ажеттілігін х =2-мен келесі мысалды келтіріп жіберуге болады:

1 1 1 2 1 1 1

Бірінші кө ру жә не ауыстыру

1 1 1 1 1 1 2 – ні береді, ә рі і = 5, j = 6.

Екінші кө ру массивті ө згертпейді жә не i = 7, j = 6-ғ а аяқ талады. Егер ауыстыру i ≤ j шартына бағ ынбағ анда, онда а6 жә не а7 қ ате ауысу пайда болар еді.

Бө ліну алгоритімінің дұ рыстылығ ында циклдық оператордың варианттары бола алады деген екі пікіріне сү йене тоырып кө з жеткізуге болады. Алғ ашқ ыда i = 1 жә не j =n қ асында олар сірә шынайы, ал i > j амалын тапқ ан кезде олар керекті нә тиже алынды деп ұ йғ арады.

Енді бізге басты мақ сат – тек қ ана элементтің шығ ушы массивтін ү лкенге жә не кішіге болу емес, сонымен қ атар оны іріктеу керек екендігін еске тү сіруіміз керек. Дегенмен, бө луден іріктеуге дейін не бары бір кішкентай адым: ә рбір бө ліктің қ ұ рамында тек бір элемент болмағ анғ а дейін массивті бө ле отырып, алынғ ан бө лшекті, сосын осы бө лшектің бө лшегімен соны қ айтадан істеу керк. Бұ л тә сіл 2.10 программасында кө рсетілген.

Soft процедурасы ө з-ө зін рекурсивті тү рде шығ арады. Алгоритмда рекурсияны осылай қ олдану - ө те кү шті қ ұ рал. Біз оны кейін талқ ылаймыз.

procedure guicksoft;

procedure soft (l, r: index);

var i, j: index; x, w: item;

begin i: = l; j: = r;

x: = a [(l + r) div 2];

repeat

while a [ i ]. key do i: = i + 1;

while x. key < a [ j ]. key do j: = j - 1;

if i ≤ j then begin

w: = a [ i ];

a [ i ]: = a [ j ];

a [ j]: = w;

i: = i + 1;

j: = j – 1

end

until i > j;

if l < j then soft (l, j);

if i < r then soft (i, r)

end;

begin soft (l, n)

end {guicksort}

Ескі ү лгіде бағ дарлаудың кейбір тілінде рекурсия кейбір техникалық себептер бойынша тыйым салынады. Қ азір біз сол алгоритмді рекурсивті емес процедура тү рінде кө рсете аламыз. Сірә, бұ л жағ дайда рекурсия итерия сияқ ты ұ сынылады. Бұ нда ақ парат сақ тау ү шін кейбір қ осымша операциялар қ ажет.

Итеративті шешімнің негізі – ол бө лінуге сұ раныс тізімін жү ргізу, оны ә лі орындау керек. Ә рбір адымнан кейін екі кезекті бө луді жасау керек. Тек олардың біреуін ғ ана келесі итерацияда тікелей орындау қ ажет. Басқ ағ а деген сұ раныс тізімге тіркеледі. Ә рине, тізімдегі сұ раныс кері жұ йелілікте орындалу қ ажет. Тізімге ең гізілген бірінші сұ раныс ең соң ғ ы болып жә не керісінше орындалады; тізім ө зін тамыр соғ ушы стек сияқ ты жү ргізеді. Бө лшектің шегін анық тайтын тез іріктеудің келесі рекурсивті емес хабарында ә р сұ раныс сол жә не он индекстармен кө рсетілген кейін оны бө луге тура келеді. Сонымен, біз stask деп аталатын ө згергіш – массивті жә не осы стекта ең соғ ы жазуды кө рсететін S индексін ең гіземіз (2.11 программаны қ араныз) m стегінің қ андай болуы керектігін тез іріктеудің талдағ анда талқ ылаймыз.

Тез іріктеудің қ асиетің талдау ү шін, біз ең алдымен бө лу ү рдісімен танысуымыз қ ажет. Бө лу ү рдісіне шегін таң дағ ан соң барлық массив тү сіріледі. Осығ ан орй n салыстыру орындалады. Ауыстырудың санын келесі ойлау ық тималдылының кө мегімен бағ алауғ а болады.

Бө луге келетін кө птеген мә ліметтер n кілттерден 1,..., тұ рады. Сндық тан біз х-ті шек ретінде таң дадық. Бө лгеннен соң х, массивта х позициясын басады. Ауыстыруды талап ететін сан х – 1 сол бө лігіндегі элементке тең. Ол ауыстыруды қ ажет ететін ық тималдылық қ а кө бейтілген.

Егерде кілт х-тен кем болмаса, онда ол ауысады. Бұ ның ық тималдылығ ы (n – х + 1) n –ғ а тең.

Ауыстырудың саны барлық шекті таң даудың мү мкіншіл варианттарын қ оса отырып жә не осы қ осындыны n-ғ а бө ле отырып анық талады.

М =

Сондық тан ауыстырудан кү тетін сан n – 6 шамасына тең болады.

Шек ретінде медиананы алатын болсақ, онда ә р бө лініс массивті жә не ө тудің санын екі тең бө лшекке бө леді. Ол іріктеу ү шін ө те қ ажет жә не ол ℓ оgn – тең. Салыстырудың жалпы саны n ·ℓ оgn қ ұ райды, ал ауыстырудың жалпы саны (n/6) ℓ оgn қ ұ райды. Ә рине, біз ә рқ ашанда медианағ а тү семіздеп кү туге болмайды. Іс жү зінде бұ ның ық тималдылығ ы 1/n – ге тең. Егерде шек кездейсоқ тү рде тандалса, тез іріктеудің нә тижелігі орташа шамада 2 ·ℓ n2 рет ү йлесімдіден жаманырақ. Орташа орындалу уақ ыты O(n log n).

procedure guicksort l;

const m = 12;

var i, j, l, r: index;

x, w: item;

s: 0.. m;

stack: array [ l.. m ] of

recordl, r: index end;

begin s: = l; stack [ l ].l: =1; r: = n;

repeat

l: = stack [ s ]. l; r: = stacks; s: = s -1;

repeat {split a [ l ]... a[ r ]}

i: = l; j: = r; x: = a [(l + r) div 2];

repeat

while a [ i ]. key < x. key do i: = i + 1;

while x. key < a [ j ]. key do j: = j - 1;

if i ≤ j then begin

w: = a [ i ];

a [ i ]: = a [ j ];

a [ j ]: = w;

i: = i + 1; j: = j – 1

end

until i > j;

if i < r then begin {он жақ бө лікті іріктеу сұ ранысының стекне жазу }

s: = s + 1;

stack [ s ]. l: = i;

stack [ s ]. r: = r

end;

r: = j.

until l ≥ r

until s = 0

end {guicksort}