“Крест пен ноль” ойыны

Пән: Информатика, Программалау, Мәліметтер қоры
Жұмыс түрі: Курстық жұмыс
Тегін: Антиплагиат
Көлемі: 26 бет
Таңдаулыға:

Мазмұны

1. Кіріспе . . . 3

2. Есептің қойылымы . . . 4

3. Теориялық мағлұматтар . . . 4

3. 1 Сұрыптау . . . 4

3. 2 Сұрыптау тәсілдері . . . 4

4. Ішкі сұрыптау . . . 5

4. 1 Таңдау сұрыптауы . . . 5

4. 1. 2 Есептеуішпен берілген сызықтық таңдау . . . 6

4. 2 Көпіршік тәсілі . . . 7

4. 3 Енгізу тәсілі . . . 10

4. 3. 1 Модификацияланған енгізу тәсілі . . . 11

4 . 4 Шелл тәсілі . . . 12

4. 5 Бөлу сұрыптауы . . . 15

4. 6 Бірігу тәсілі . . . 15

5. Сыртқы сұрыптау . . . 16

5. 1 Тура бірігу . . . 16

5. 2 Кәдімгі бірігу . . . 17

6. Есептің мақсаты . . . 18

7. Программаның баяндалуы . . . 19

7. 1 Жалпы мағлұматтар . . . 19

7. 2 Функционалдық қолдануы . . . 19

8. Программаның алгоритмі . . . 20

9. Блок-схема

10. Қолданылған техникалық жабдықтар . . . 26

11. Шақырылуы және жүктелуі . . . 26

12. Қорытынды . . . 27

13. Әдебиеттер тізімі . . . 28

Кіріспе

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

1980 жылдары барлық ойындар және оқытатын программалар MS-DOS операциялық жүйеге арнап жазылған болатын, оның себебі - графикалық редакторлардың әлсіздігі және де жадының жетіспеушілігі. Кейін жаңа WINDOWS операциялық жүйелері пайда болды да, олардың графикалық редакторлары мықты болып, оқытатын программалар барлық ғылыми және техникалық мекемелерде пайда болды, сонымен қатар кішкентай балаларды оқытатын ойын программалары пайда болды.

Қазіргі таңда компьютерлік ойындарды жасау кең орын алып отыр. TGF және The Pie GCS сияқты программаларда ойындарды санаулы сағаттар ішінде жасай алады. Бұл программаларда осындай мүмкіндікті тұрғызатын құралдар өте жоғары деңгейде дамыған. Ол жерде ойын жасап жүрген шеберлер өздерінің барлық мүмкіндіктерін көрсете алады, жас бағдарламаушылар да тез меңгеріп кетеді.

2. Есептің қойылымы

Бұл программаны орындау үшін Паскаль тілінің мүмкіндіктерін қолданамыз. Бұл ойын “Крест пен ноль” деп аталады. Негізінде осы ойынның ешқандай қиындығы жоқ. Ойынды бастаудан бұрын берілген инструкциясын оқыңыз.

Есептің шарты:

Алаңшада компьютер мен ойыншы ойнайды. Баған немесе жол бойынша крест немесе нольді тізіп қойып шыққан ойыншы жеңеді. Және олар бір-біріне солай қойып шығуына бөгет жасай отырып, өз мақсаттарына жету керек.

3. Теориялық мағлұматтар

3. 1. Сұрыптау

Сұрыптау барлық программалау саласында қолданылады. Сұрыптау бұл ақпараттық объекттердің мәндерін өсу немесе кему бойынша реттелуін іске асыратын процесс. Мысалы, егер i<=i<=…<=i болса, онда n - элементтеріндегі і тізімдері өсу бойынша сұрыпталады. Сұрыптау алгоритімнің екі түрі бар: операциялық жадыда немесе дискідегі файл түрінде орналастырылған массивтердің сұрыпталуы және магниттік ленталардағы немесе дисктерде орналасқан кезекті файлдардың сұрыпталуы. Мен тек қана сұрыптаудың бірінші түріне тоқталдым, себебі осындай сұрыптаудың тәсілдерімен басқаларға қарағанда программисттер жиі-жиі қолданады. Массивтерді және кезекті файлдарды сұрыптаудың негізгі ерекшелігі - массивтің әрбір элементі әр уақытта жеңіл беріледі. Ол әр уақытта массивтің кез келген элементі басқа бір массивтің элементімен салыстырылады да, массивтің кез-келген екі элементтері орындарымен ауыстырылуы мүмкін. Ал кезекті файлда әрбір уақытта тек қана бір элемент беріледі. Осындай айырмашылықтардан сұрыптаудың тәсілдерінде бір-бірінен үлкен өзгерістері бар.

3. 2. Сұрыптау тәсілдері

Кестелермен жұмыс істегенде - оның негізгі опреациялары - ол жазбаларды реттеу және берілген шарт бойынша жазба кестелерінде барлау жасау.

Сұрыптау - бұл кейбір критерийлері бойынша жазбаны кестелерде нақты бір тәртіппен реттеу операциясы. Сұрыптау барлық жазбалар кілттерінің мәндерімен сәйкес іске асады (мыс., алфавит бойынша аттарын реттеу немесе сандарды өсу бойынша реттеу) . Сұрыптаудың көптеген бір - бірінен айрықша тәсілдері бар. Егер де кесте бүтіндей ЭЕМ - нің жедел жадында орналасса, онда оның реттелуі ішкі деп аталады. Ал егер де реттелген мәліметтерді сақтау үшін сыртқы есте сақтау құрылғысы пайдаланса, онда бұндай реттелу сыртқы деп аталады. Операцияларды салыстырудың орташа саны, сұрыптаудың тәсілінен байланысты, және де рационалды тәсілді таңдаған кезде кейбіреулері минимумға жетеді. Ішкі сұрыптау тәсілдерін екі топқа бөлуге болады:

Разервтік жадыны қажет ететін тәсілдер
Резервтік жадыны қажет етпейтін тәсілдер

Бірінші топқа таңдау, енгізу, көпіршік (пузырька), Шелл тәсілдері жатса, екінші топқа квадраттық таңдау, қосылу тәсілі және т. б. жатады. Қарапайым сұрыптау тәсілдері (таңдау, енгізу, ауыстыру) шамамен n**2 салыстыруын талап етеді. Әдетте одан да қиынырақ алгоритмдер орташа n*log2(n) салыстыруларында нәтиженің берілуін қамтамасыз етеді. Бірақ та кез келген жағдайларда қолайлы сұрыптау жоқ, себебі олардың тиімділігі кестедегі кілттердің түріне және олардың алдын ала реттелуіне байланысты. Ішкі сұрыптаудың ең кең қолданылатын тәсілдерін қарастырайық.

4. Ішкі сұрыптау

4. 1 Таңдау сұрыптауы

(тік таңдау, сызықты таңдау)

Осы метод бойынша, кестедегі бірінші жазбадан бастап, ең кішкентай мәні бар кілттің элементтерін іздеуге болады. Осындай орын-ауыстырудың нәтижесінде, кілттің ең кішкентай мәні бар жазбаны кестедегі бірінші позицияға орналасытырады. Одан кейін кестедегі екінші элементтен бастап, екінші ең кіші мәні бар кілттің ізденуі жүзеге асады. Табылған элемент кестедегі екінші элементпен орын ауыстырады. Бұл процесс кілттің кодтары өсу реті бойынша реттелмейінше тоқтамайды. Осы тәсілдегі салыстыру саны n(n-1) /2 -ге тең, мұндағы n - кестедегі жазбалардың саны. Осындай сұрыптау кезінде орын ауыстырудың ең үлкен саны (n-1) - ге тең. Келесі кілттердің мәндері бар кесте үшін алгоритмдік қадамдарын мысал ретінде қарастырамыз:

23 11 4 56 9 35 7

Берілген кесте әртүрлі кезеңіндегі реттелуін көрсетеді

(орын ауыстыратын элементтердің асты сызылған) :

23 11 4 56 9 35 7
4 11 23 56 9 35 7
4 7 23 56 9 35 11
4 7 9 56 23 35 11
4 7 9 11 23 35 56

4. 1. 2 Есептеуішпен берілген сызықтық таңдау

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

Осы методты пайдалана отырып келесі мысалды қарастырайық:

Бастапқы кесте және есептеуіштің массиві:

Индекстер Кілттер Есептеуіштер

0 9 0

1 5 0

2 10 0

3 2 0

Қараулар нәтижесінде массивтің өзгеруін қарастырайық:

1-ші 2-ші 3-ші Нәтижелі кесте (кілттер)

2 2 2 2

0 1 1 5

1 2 3 9

0 0 0 10

4. 2 «Көпіршік» тәсілі

Осы тәсілді пайдаланған кезде (n-1) - дің ең үлкен өтулері керек. Кестенің бірінші өтуі кезінде бірінші және екінші жазбаның К1 және К2 кілттері салыстырылады, егер де олардың арасындағы тәртіп бұзылса, онда R1және R2 жазбалары орындарын ауыстырады. Содан кейін осы процесс R2 және R3, R3 және R4 т. с. с. үшін қайталанады. Осы тәсіл аз кілттері бар жазбаларды қозғалтуға және білінуге мәжбүр етеді. Бірінші өтүден кейін ең көп мәні бар жазбадағы кілт кестенің n-ші позициясында тұрады. Әрбір келесі өтулер кезінде ең көп мәндері бар келесі жазбалардағы кілттер n-1, n-2, …, 2 позицияларында орналасады, нәтижесінде сұрыпталған кесте шығады. Әрбір өтулерден кейін осы өтулер кезінде ауыстырулар болда ма, жоқ па деген тексеруді да істеуі мүмкін. Егер де ауыстырулар жоқ болса, онда ол кесте сұрыпталғаны екені және де одан арғы өтулерді қажет етпейтінін білдіреді. Сонымен қатар, соңғы ауыстырудың индексін есте сақтауға болады. Бұл келесі қадамдағы қарайтын қосалқы кестені кішірейтуге мүмкіндік береді. «Көпіршік» тәсілімен сұрыптағандағы сипаттамасы ең болмағанда n(n-1) /2 салыстыруларын және n(n-1) /2 ауыстыруларын құрайды. Салыстырудың және ауыстырудың орташа саны n**2 рет.

Паскаль тілінде «Көпіршік» тәсілін іске асыратын процедура төменде келтірілген:

Type
Rec=Record
f1 : char;
f2 : integer;
f3 : integer
End;
Table = Array[1. . 100] Of Rec;
procedure bubble(var T:Table;
n:integer) ;
{ T - кесте; n - оның өлшемі }
{ f3 ауданы бойынша сұрыптау}
var
i:integer;
temp:Rec;

witch:boolean;
begin
repeat

switch:=false;
for i:=1 to n-1 do
if T[i] . f3>T[i+1] . f3 then
begin
switch:=true;
temp:=T[i] ;
T[i] :=T[i+1] ;
T[i+1] :=temp
end
until not(switch)
end

Бұл тәсіл ауыстыру тәсілімен сұрыптауды пайдаланады. Ол салыстыру операцияларының циклында орындалуында және көршілес тұрған элементтерін ауыстыруға қажеттігіне негізделген. Оның аталуы сумен толтырылған резервуардағы көпіршіктердің қозғалу кезіндегі процесске ұқсас болғандықтан олай аталды. Әрбір көпіршік өз жиегін табады. Төменде көпіршік тәсілімен сұрыптаудың ең қарапайым программаның формасы көрсетліген:

{Көпіршік тәсілімен сұрыптаудың басталуы}

procedure Bubble(var item: DataArray; count:integer) ;
var
i, j: integer;
x: DataItem;
begin
for i := 2 to count do
begin
for j := count downto i do
if item[j-1] >item[j] then
begin
x := item[j-1] ;
item[j-1] := item[j] ;
item[j] := x;
end;
end;
end;

{ Көпіршік тәсілімен сұрыптаудың аяқталуы }

Бұл мысалда берілген «item» «Dataitem» элементінің массиві болып табылады. Ол сұрыпталады да, ал берілген «count» массивінде элементтердің саны бар.

Көпіршік тәсілімен сұрыптаудың екі циклі бар. Массив элементінің саны «count» айнымалымен берілгендіктен, сыртқы цикл count массивінің қаралуын ! рет ғана шақырады. Бұл процедура аяқталғаннан кейін әрбір элементтің өз позициясында тапқанын қамтамасыз етеді. Ішкі цикл салыстыру және ауыстыру операцияның шындығымен орындалатынына негізделген. Көпіршік тәсілімен сұрыптаудың осы версиясы символдық массивтегі элементтердің мәндерін өсу реті бойынша сұрыптай алады. Мысалы, келесі қысқа программа «test. dat» дисктік файлынан оқитын жолды сұрыптайды:

program SortDriver;
{бұл программа «test. dat» дисктік файлынан 80 немесе одан да аз символдарын сұрыптайды да, нәтижені экранға шығарады }

type
DataItem = char;
DataArray = array [1. . 80] of char;
var
test: DataArray;
t, t2: integer;
testfile: file of char;
{ Көпіршік тәсілімен сұрыптау}
procedure Bubble(var item: DataArray; count:integer) ;
var
i, j: integer;
x: DataItem;
begin
for i := 2 to count do
begin
for j := count downto i do
if item[j-1] >item[j] then
begin
x := item[j-1] ;
item[j-1] := item[j] ;
item[j] := x;
end;
end;
end;

begin
Assign(testfile, 'test. dat') ;
Reset(testfile) ;
t := 1;

{ сұрыптауға кететін символдарды оқу}

while not Eof(testfile) do begin
read(testfile, test[t] ) ;
t := t+1;
end;
t := t-2; {есептелген элементтердің санын дұрыстау }

Bubble(test, t) ; { массивті сұрыптау}

{ сұрыпталған сиволдық массивтің шығарылуы }
for t2 := 1 to t do write(test[t2] ) ;
WriteLn;
end.

Көпіршік тәсілімен сұрыптауының бір ерекшелігі бар: массивтің соңындағы өз орнында тұрмаған элемент (мысалы, «dcab» массивіндегі «а» элементі) бір өту арқылы өз орнына жетеді, ал массивтің басында орналасқан элемент (мысалы, «d» элементі), өз орнына өте баяу жетеді. Барлық қарауларын бір бағытта істеу міндетті емес. Оның орнына әрбір келесі қарауын қарама-қарсы бағытта істеуге болады. Бұл жағдайа өз орнынан қатты алыстап кеткен элементтер тез арада өз орнына жылжиды.

4. 3 Енгізу тәсілі

Бұл тәсіл келесі ереже бойынша жұмыс істейді: R[j] жазбаны қарастырғанға дейін алдағы R[1], R[2], …, R[j-1] жазбалар да реттелген және R[j] тиісті орнына енгізіледі. Кестенің сұрыпталуы екінші жазбадан басталады. Оның кілті бірінші жазбаның кілтімен салысытырылады да, егер де реттелуі бұзылса, онда R[1] және R[2] жазбалары орындарын ауыстырады. Одан кейін R[3] жазбаның кілті R[1] және R[2] жазбалардың кілттерімен салыстырылады. J-ші қадамда K[j] кезекпен K[j-1], K[j-2], …(K[1] <=K[2] <=…<=K[j-1] ) - мен K[j] <K[i] (i=j-1, j-2, . . . )

шарттары орындалғанда ғана немесе қосалқы кестенің (i=1, K[j] <K[1] ) реттелген сол жағындағы соңы жеткенде ғана салыстырылады.

K[j] >=K[i] шарты орындалғанда, бұл R[j] жазбаны R[i] және R[i+1] арасына енгізу керек екенін білдіреді. Онда R[i+1], R[i+2], . . . , R[j-1] жазбалары бір позицияға жылжиды да, R[j] жазбасы i+1 позициясына енгізіледі. Салыстыру және орын-ауыстыру операцияларын қосуға қолайлы. Төменде j-ші қадамның сұрыпталуы қалай іске асатынын көрсетіледі:

5 8 10 14 6 2 11 ¦ j=5, i=4, 6 < 14

<-~~ ¦
5 8 10 6 14 2 11 ¦ i=3, 6 < 10
<-~~ ¦
5 8 6 10 14 2 11 ¦ i=2, 6 < 8
<-~~ ¦
5 6 8 10 14 2 11 ¦ i=1, 6 > 5

Енгізу методы үшін салыстыру операциясының саны келесі формула арқылы есептеледі:

С=

Сұрыпталған кестедегі элементтердің саны көп болған жағдайда, мына формуланы қолдануға болады:

C=n**2/4

Осы методты пайдаланғанда орын-ауыстырудың максималды саны n**2/4 - ге тең. Енгізу тәсілімен реттелген кестенің ішіне жазбалар енгізгенде көп қолданылады. Жаңа жазба кестенің ішіне бар реттің ешбір өзгеріссіз енгізілуі керек.

4. 3. 1 Модификацияланған енгізу тәсілі (бинарлық кірістіру)

Тура қосу тәсілін жақсарту үшін, кестенің кезекті элементін реттелген қосалқы кестеге енгізу, оны бинарлық іздеу тәсілінің (дихотамикалық, екілік, логарифмдік) көмегімен жүзеге асыруға болады.

Сұрыптаудың j-ші қадамы:

5 6 8 10 14 18 9 2 ¦ i = 6/2 = 3; 9 > 8

~~~ ~~ ¦
тасталынады қарасытырлады ¦
--¬ ¦
. . . 10 14 18 9 2 ¦ i = (4+6) /2 = 5;
~~ ¦ 9 < 14
тасталынады қарасытырлады ¦
. . . 9 10 14 18 2 ¦ i = 4; 9 < 10

4. 4 Шелл тәсілі

Салыстырылатын элементтердің арасындағы ара-қашықтығын азайтатын принципті қолданып, енгізу сұрыптауын пайдаланатын жалпы тәсіл. 1 суретте «abcdef» массиві үшін Шелл сұрыптауы көрсетіліп тұр. Біріншіден бір-бірінен үш позицияға жылжыған барлық элементтер сұрыпталады. Одан соң екі позицияға жылжыған барлық элементтер сұрыпталады. Ең соңында барлық көрші элементтер сұрыпталады.

1-сурет . Шелл сұрыптауы

{ Шелл сұрыптауы }
procedure Shell(var item: DataArray; count:integer) ;
const
t = 5;
var
i, j, k, s, m: integer;
h: array[1. . t] of integer;
x: DataItem;
begin
h[1] :=9; h[2] :=5; h[3] :=3; h[4] :=2; h[5] :=1;
for m := 1 to t do
begin

k:=h[m] ;
s:=-k;
for i := k+1 to count do
begin
x := item[i] ;

j := i-k;
if s=0 then
begin
s := -k;
s := s+1;
item[s] := x;
end;
while (x<item[j] ) and (j<count) do
begin
item[j+k] := item[j] ;
j := j-k;
end;
item[j+k] := x;
end;
end;
end; { Шелл сұрыптауының соңы }

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

Салыстырлатын элементтердің арасындағы ара-қашықтық әртүрлі өзгеруі мүмкін. Ең соңғы қадам бірге тең екені міндетті болу керек. Мысалы, 9, 5, 3, 2, 1

Қадамдарының жүйелілігі жақсы нәтижені береді. Екінші дәрежелі жүйелерінен құтылу керек, себебі күрделі математикалық есептеулердің нәтижесінде, сұрыптау алгоритмнің эффектісі төмендейді.

Ішкі циклдің екі тексеру шарты бар. "х<item[j] " шарты, элементтерді реттеу үшін қажет. "j>0" және "j<= count" «item» массивінің шетіне шығуына кедергі жасайды. Осы қосымша тексеру бір жағынан Шелл сұрыптауын нашарлатады. Шелл сұрыптаудың жай ғана өзгертілген версиялары сұрыптауға берілген ақпараттың бөлігі емес болып табылатын басқару элементтері пайдаланылады. Басқару элементтері массив мәліметтерінің шекті мәндері бар, яғни ең үлкен және ең кіші мәндері. Осы жағдайда шеекті мәндерге тексеру жасау онша қажет емес. Алайда, осындай басқару элементтердің қолданылуы, сұрыптауға берілген ақпарат туралы белгілі бір

мәліметті талап етеді, бұл сұрыптау процедурассының универсалдығын төмендетеді.

Шелл сұрыптауының орындалу уақыты n**1. 2 - ге пропорционал. Бұл тәуелділік бұрын қарастырылған квадраттық тәуелділіктен анағұрлым жақсырақ. Алайда, Шелл сұрыптауын пайдаланбастан бұрын, жылдам сұрыптау одан да жақсы нәтижелерін беретінін ескеруге болады.

Қарастырылған сұрыптау алгоритмдерінде жазба тек бір позициясына ғана жылжығанын байқадық. Сонымен бірге жұмыстың орташа жұмыс уақыты n-ға пропорционал. Шелл (кему бойынша өзгеретін қадамның сұрыпталуы) тәсәлә дегеніміз - жай енгізулерді анағұрлым асып кететін, сонымен бірге жазбалар күрделі қадамдар жасап ауыстырылатын тәсілді айтамыз. Тәсілдің негізгі құрылысы - реттелген кесте элементтердің екі тобына бөлінеді де, олардың әрқайсысы енгізу тәсілі арқылы реттеледі. Реттелу процесінде осындай топтардың өлшемдері реттелген топтарға барлық элементтер кірмейінше артады. Кезекті реттелген топтың таңдауы және оның кесте ішіндегі орналасуы өткен реттелуін пайдалануға болатындай етіп іске асыруға болады. Кесте тобы дегеніміз - бұл элементтердің нөмірлері Һ қалдықпен арифметикалық прогрессияны құрайтын, осы элементтердің жүйелілігі. Реттелу процесстің басында кестенің өлшеміне тәуелді болатын һ1 тобының бірінші қадамы таңданады.

Шелл мынаны алуға ұсынды:

h1=[n/2], а hi=h((i-1) /2) .

Хиббардтың кейінгі жұмыстарында, процессті тездету үшін һ1 қадамын келесі формула бойынша анықтау ең қолайлы жолы деп санаған:

h1=2**k+1, мұндағы 2**k < n <= 2**(k+1) .

Һ1- ді енгізу тәсілі арқылы таңдағаннан кейін i, i+h1, i+2*h1, . . . , i+mi*h1 позицияларының нөмірлерінен тұратын элементтерінен құралатын топтар реттеледі. Сонымен бірге i+m[i] *hi <= n шартын қанағатандыратын i=1, 2, . . . , h1; m[i] - ең үлкен бүтін. Одан кейін h2<h1 қадамы таңдалады да, i, i+h2, . . . , i+m[i] *h2 позицияларының нөмірлерінен тұратын элементтерінен құралатын топтарды реттеу. Бұл процедура азайтылатын қадамдарымен кезекті h[1] қадамы бірге (h1>h2> . . . >hl) тең болғанға дейін жалғастырылады. Бұл ең соңғы кезең енгізу тәсілімен бүкіл кестенің реттелуін ұсынады. Негізгі кесте бөлек топтармен реттелгендіктен, онда салыстырудың жалпы саны енгізу методы кезінде n /4 - тен анағұрлым аз.

Салыстыру операцияларының саны n*(log2(n) ) **2 - ға пропорционал.

4. 5 Бөлу сұрыптауы

(Quicksort)

Бұл тәсіл ауыстыру тәсілінің дамуы болып табылады. Ол эффектілі болғаннан кейін, оны «тез сұрыптау тәсілі» (Quicksort) деп атаған. Оның негізгі идеясы Х массивінің кез-келген элементі таңданады да, осы массив a[i] (a[i] >X) элементі кездескенге дейін сол жағынан қарастырылады, одан кейін массив a[j] (a[j] <X) элементін кездескенге дейін оң жағынан қарастырылады. Осы екі элементтер орындарымен ауыстырылады да, қарау, салыстыру және ауыстыру процесстері Х элементке жеткенге дейін жалғастырылады. Нәтижесінде массив екі бөлікке бөлінеді: оң, оның кілттердің мәндері Х-тан кіші болады және сол, оның кілттерінің мәндері Х-тан үлкен болады. Осыдан кейін процесс рекурсивті түрде әрбір бөлікте бір ғана элемент болғанға дейін жалғастырылады.

Тез сұрыптау тәсіліне мысал 1-кестеде келтірілген:

... жалғасы

Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.