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

ЖОСПАР

Кіріспе

Негізгі бөлім

Сұрыптау әдістері:

1. Таңдау арқылы сұрыптау.
2. Алмастыру арқылы сұрыптау.
3. Индекстері арқылы сұрыптау.
4. Енгізу арқылы сұрыптау.

1. Біріктіру арқылы сұрыптау.

Қорытынды

Пайдаланылған әдебиеттер

КІРІСПЕ

Қарапайым типтер қатарына жататын стандартты (Integer, real) және қолданушылар (тізбектелген тип) типтерінде бір айнымалыны сақтау үшін, негізінен компьютер жадысының бір ғана ұяшығы қолданылады. Бірақ көптеген программалау есептерінің шешімін табу барысында әрбір элементтің деректерін жеке айнымалыға сақтау анағұрлым тиімді болып табылады.

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

Массив сипаттамалары:

• Типі - массив элементтерінің жалпы типі;
• Көлемі - массив индекстерінің саны;
• Шектелімі - әрбір индекстердің шектеу бойынша сәйкестігі;
• Пішімі - көлем және шектеулер жиындары.

Массивтер элементтерімен жұмыс жасау барысында, массив атауынан кейін міндетті түрде тік жақшаға алынған индекс көрсетіледі. Индекс ретінде сандар қолданылады.

Массивтерді қолдану үшін оларды типтер (type) немесе айнымалыларды сипаттау (var) бөлімінде хабарлану қажет.

Жалпы жазылу түрі:

Type

Массив типінің атауы = array [индекс типі] of элемент типі;

Var

Массив атауы:массив типінің атауы

Мұндағы:

Массив типінің атауы - массив элементтерінің жиынын сипаттайды;

Индекс типі - тізбектелген немесе шектелген типтерді көрсету;

Элемент типі - массив элементтерінің типін көрсету.

Берілген массивтің кез - келген элементтеріне арифметикалық операцияларды, салыстыру және меншіктеу операторларын қолдануға болады. Сонымен қатар, массивтерге Turbo Pascal программалау тіліндегі айнымалы типіне сәйкес келетін барлық стандартты процедуралар және фунциялар қолданылады.

Turbo Pascal программалау тілі бiр өлшемдi массивтермен қатар екi өлшемдi және көп өлшемдi массивтердi қолдануға мүмкiндiк бередi.

Екi өлшемдi немесе көп өлшемдi массивтермен жұмыс iстеу үшiн, олар сипаттау бөлiмiнде көрсетiлуi тиiс.

Екi өлшемдi массивтi var бөлiмiнде сипаттаудың жалпы түрi:

var

Массив атауы: array [a1. . an, b1. . bn] of элемент типі;

Екі өлшемді массивтi type бөлiмiнде сипаттаудың жалпы түрі:

type

Массив типінің атауы = array [a1. . an, b1. . bn] of элемент типі;

Var

Массив атауы: массив типінің атауы;

Мұндағы, a1. . an, b1. . bn - екі өлшемді массивтің көлемі:

a1 және an - массив қатарының алғашқы және соңғы мәні;

b1 және bn - массив бағанының алғашқы және соңғы мәні.

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

СҰРЫПТАУ ӘДІСТЕРІ

Тізімді реттеу

Сұрыптау кез - келген түрдегі кестелерді (массивтерді) өңдеу алгоритміне жатады. Бұның мәні мынада: кесте элементтерін белгілі бір ретпен орналастыру. Сандық кестені сұрыптау - ондағы элементтерді оның нөмірінің өсуі мен мәнінің өсу немесе кему ретімен орналастыру.

Мысал 1:

Элемент нөмірі 1 2 3 4 5

Кестенің бастапқы түрі 7 12 1 49 3

Өсу бойынша реттелген кесте 1 3 7 12 49

Мысал 2:

Элемент нөмірі 1 2 3 4 5

Кестенің бастапқы түрі 4 2 17 2 17

Өсу бойынша реттелген кесте 2 2 4 17 17

Мұндағы индекстер бір мәнді элементтердің ретін көрсетеді.

Литерлік кестені сұрыптау әдетте ондағы мәндерді алфавит бойынша орналастыру дегенді білдіреді.

Мысал 3:

Элемент нөмірі 1 2 3 4 5

Кестенің бастапқы түрі мир сон тур кол ель

Өсу бойынша реттелген кесте ель кол мир сон тур

Егер реттеген кезде бірдей мәнді элементтердің реті өзгермесе сұрыптаудың бұл түрі тұрақты деп аталады.

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

Жедел жадыда орналасқан, бізге мәлім, сұрыптау алгоритмдері түрлі болып келеді. Оларды зерттеу оқыту жағынан өте пайдалы, себебі оларда түрлі қиындықтағы алгоритмдерді құрастырудың барлық дерлік әмбебап қабылдаулары қолданылады. Н. Вирттің айтуынша:«Тек қана сұрыптау есептерінің мысалдарын ала отырып бағдарламалаудың толық курсын құрастыруға болатындай сезім туады». Сонымен қатар бұл алгоритмдердің қызық бір жері, онда бағдарламалаудың бай мүмкіндіктерін пайдаланып, яғни неше түрлі жолдармен бір мақсатқа, реттелген кестені алу сияқты, жетуге болатыны көрсетіледі. Сұрыптау алгоритмдерінің көптігі жағдайында, егер негізгі тиімділігі жадыны үнемдеу және тез іске асуды жоғарылату болса, алгоритм сапасын бағалаудың қажеттігі белгілі болады.

1. Элементтерді таңдау арқылы сұрыптау

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

Алгоритмі:

1. Өлшемі n болатын А массивін толтыру және экранға шығару;
2. i:=1;
3. Индексі i-ден басталатын массив элементтерінің ішінен ең кішісін (индексі j) таңдап алу;
4. A[i] және A[j] элементтерінің орндарын ауыстыру;
5. i:=i+1 мәні үшін i:=n болғанға дейін 3 және 4 қадамдарды қайталау;
6. Сұрыпталған A массивін экранға шығару;

1 2 3 4 5 6 7 8

1 2 3 4 5 6 7 8

1 2 3 4 5 6 7 8

1 2 3 4 5 6 7 8

1 2 3 4 5 6 7 8

1 2 3 4 5 6 7 8

1 2 3 4 5 6 7 8

1 2 3 4 5 6 7 8

1. 1 сурет

Program Prost_1. 2;

Const n=8;

type MasType = array [1. . n] of integer;

var i, idx, k:integer;

A: MasType;

Function MinMas(j: integer) : integer;

Var p, min: integer;

Begin

For p:=j to n do

If (p=j) or (A[p] <A[min] ) then min:=p;

MinMas:=min;

End;

Begin

Randomize; Writeln(‘берілген сандар массиві:’) ;

For i:=1 to n do

Begin A[i] :=Random(30) ; Write(A[i] :4) ; end;

For i:=1 to n-1 do

Begin

idx:=MinMas(i) ;

k:=A[i] ; A[i] :=A[idx] ; A[idx] :=k;

end;

Writeln; Writeln(‘өсуіне қарай сұрыптау нәтижесі:’) ;

For i:=1 to n do Write(A[i] :4) ;

Readln;

End.

Бұл программада берілген массив бөлігінің ең кіші элементінің индексін (рет нөмірін) табатын Minmas(j) функциясы пайдаланылған. Функцияның j параметрінің мәні массив бөлігінің бірінші элементінің рет нөмірін (соңғысы n ) көрсетеді.

2. Элементтерді алмастыру арқылы сұрыптау

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

Алгоритмі:

1. Өлшемі n болатын А массивін толтыру және экранға шығару;
2. i:=1;
3. Егер А[i] >A[i+1] болса, онда олардың орындарын ауыстыру;
4. i:=i+1 мәні үшін i:=n болғанға дейін 3 қадамды қайталау;
5. Ең болмағанда бір алмастыру орындалса, екі қадамнан кері бастау;
6. Сұрыпталған A массивін экранға шығару;

2. 1 сурет

Program Prost_2. 2;

Const n=8;

var

A: array [1. . n] of integer;

i, j, k:integer; p: boolean;

begin

Randomize;

Writeln(‘Берілген сандар массиві:’) ;

For i:=1 to n do

Begin A[i] :=Random(25) ;

Write(A[i] :4) ; end;

Repeat

p:=true;

For i:=1 to n-1 do

If A[i] >A[i+1] ;

then begin k:=A[i] ; A[i] :=A[i+1] ; A[i+1] :=k;

p:false;

end;

until p;

Writeln;

Writeln(‘Өсуіне қарай сұрыптау нәтижесі:’) ;

For i:=1 to n do Write(A[i] :4) ;

Readln;

End.

3. Массивті индекстері арқылы сұрыптау

n элементтен тұратын A сандар массиві берілген. Массивті индекстері (индекстер массивін жасақтау) арқылы элементтерінің өсуі бойынша сұрыптайық(3. 1 сурет) .

Алгоритмі:

1. Өлшемі n болатын А массивін толтыру және экранға шығару;
2. Өлшемі n болатын IDX массивін 1- мен толтыру;
3. i:=n;
4. j:=i-1;
5. Егер А[j] >A[i] болса, онда IDX[j] :=IDX[j] +1, әйтпесе IDX[i] :=IDX[i] +1;
6. j:=j-1 мәні үшін j=2 болғанша 5 қадамды қайталау;
7. i:=i-1 мәні үшін i=1 болғанша 4, 5, 6 қадамдарды қайталау;
8. IDX массивін экранға шығару;

3. 1 сурет

Program Prost_3. 2;

Const n=8;

var A, IDX:array[1. . n] of integer;

i, j, k:integer;

Begin

Randomize;

Writeln(‘Берілген сандар массиві:’) ;

For i:=1 to n do

Begin A[i] :=Random(40) ; IDX[I] :=1; Write(A[i] :4) ;

end;

For i:=n downto 2 do

For j:=i-1 downto 1 do

If A[i] <A[j] then IDX[j] :=IDX[j] +1 else

IDX[i] :=IDX[i] +1;

Writeln; Writeln(‘Өсуіне қарай сұрыптау индекстері:’) ;

For i:=1 to n do Write(IDX[i] :4) ;

Readln;

End.

4. Элементтерді енгізу тәсілімен сұрыптау

Бұл тәсілдің мәні массивтің сұрыпталмаған бөлігінен сұрыпталған бөлігіне элементтерді бір-бірлеп енгізу. Енгізілген элемент массив бөлігінің сұрыпталуын бұзбауы қажет. Ол үшін енгізілетін элемент өз орнын тапқанша, сұрыпталған бөлігінің элементтерімен орын ауыстырып отыруы тиіс. Мысалы, n элементтен тұратын A сандар массиві берілген. Элементтерді енгізу тәсілін пайдаланып массивті элементтерінің өсуі бойынша сұрыптайық(4. 1 сурет) .

Алгоритмі:

1. Өлшемі n болатын А массивін толтыру және экранға шығару;
2. i:=2;
3. j:=i-1;
4. Егер А[j+1] =A[j] болса, онда олардың орындарын ауыстырамыз және j:=j-1, әйтпесе j:=0;
5. j:=0 болғанша 4 қадамды қайталау;
6. i:=i+1;
7. i=n болғанша 3, 4, 5, 6 қадамдарды қайталау;

Program Prost_4. 2;

Const n=8;

var A: array [1. . n] of integer;

i, j, k:integer;

Begin

Randomize;

Writeln(‘берілген сандар массиві:’) ;

For i:=1 to n do

Begin A[i] :=Random(30) ; Write(A[i] :4) ; end;

For i:=2 to n do

Begin

j:=i-1;

Repeat

If A[j+1] <=A[j]

Then begin k:=A[j] ; A[j] :=A[j+1] ; A[j+1] :=k;

j:=j-1; end

else j:=0;

until j=0;

end;

Writeln; Writeln(‘өсуіне қарай сұрыптау нәтижесі:’) ;

For i:=1 to n do Write(A[i] :4) ;

Readln;

End.

1 2 3 4 5 6 7 8

1

1 2 3 4 5 6 7 8

1 2 3 4 5 6 7 8

1 2 3 4 5 6 7 8

1 2 3 4 5 6 7 8

1 2 3 4 5 6 7 8

1 2 3 4 5 6 7 8

1 2 3 4 5 6 7 8

4. 1 сурет

5. Біріктіру тәсілімен сұрыптау

Бұл тәсіл бойынша:

1. берілген массив бірнеше бөліктерге (кіші массивтерге) бөлініп, бөлек-бөлек сұрыпталады;
2. бірінші және екінші бөліктен сұрыпталған бір бөлік жасақталады; пайда болған бөлік пен үшінші бөлік және тағы сол сияқты біріктіріліп сұрыпталады;
3. осы процесс соңғы екі бөлік біріккенге дейін жалғастырылады.

Массивті бөліктерге бөліп, бөлек-бөлек сұрыптау оқушыға қиындыққа түспейді. Сондықтан, сұрыпталған екі массивті біріктіріп сұрыптау алгоритмін қарастырайық. Мысалы, өсуі бойынша сұрыпталған m элементтен тұратын A және n элементтен тұратын B сандар массивтері берілген. A және B массивтерінің элементтерінен, өсуі бойынша сұрыпталған C массивін жасақтайық(5. 1 сурет) .

Алгоритмі:

1. А және B массивтерін толтыру және экранға шығару;
2. i:=1; j:=1; k:=0; (i, j және k сәйкес, A, B және C массивтерінің кезекті элементтерінің индекстері) ;
3. k:=k+1;
4. Егер А[i] <B[j] болса, онда C(k) :=A[i] және i:=i+1, әйтпесе C(k) :=B[j] және j:=j+1;
5. i>m немесе j>n болғанша 3, 4 қадамдарды қайталау;
6. Егер i>m болса, онда B массивінің қалған элементтерін ретін сақтай отырып C массивіне тіркеу;
7. Егер j>n, онда А массивінің қалған элементтерін ретін сақтай отырып C массивіне тіркеу;
8. C массивін экранға шығару;

5. 1 суретте осы алгоритмді пайдаланғандағы, өлшемдері m=6 және n=8 болатын A және B массивтерінің элементтерінен С массивінің жасақталу қадамдары көрсетілген.

i=1 j=1 4<6 C[1] =4

i=2 j=1 10>6 C[2] =6

i=2 j=2 10>8 C[3] =8

i=2 j=3 10<15 C[4] =10

i=3 j=3 11<15 C[5] =11

i=4 j=3 18>15 C[6] =15

i=4 j=4 18>17 C[7] =17

i=4 j=5 18<26 C[8] =18

i=5 j=5 22<26 C[9] =22

i=6 j=5 30>26 C[10] =26

i=6 j=6 30>29 C[11] =29

i=6 j=7 30<34 C[12] =30

i=7 j=7 i>m C[13] =34

i=7 j=8 i>m C[14] =38

5. 1 сурет

Program Prost_5. 2;

Const m=6; n=8;

var A: array [1. . m] of integer;

B: array [1. . n] of integer;

C: array [1. . m+n] of integer;

i, j, k:integer;

... жалғасы

Информатика пәнінен лекциялық сабақтардың тезистері

Сұрыптау есептері, сұрыптау алгоритмдері туралы ақпарат

Ауыстыру арқылы сұрыптау

Егістік жұмыстардың технологиясы себу, күтіп-баптау, сұрыптау, жинау және есептеу

Сұрыптау есептері, қою арқылы сұрыптау

Программалауда массивтерді сұрыптау

Өсімдіктер, жануарлар мен микроағзалар селекциясы. Селекцияның генетикалық негіздері

Биотехнология ғылымы

Массив

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

• Іс жүргізу
• Автоматтандыру, Техника
• Алғашқы әскери дайындық
• Астрономия
• Ауыл шаруашылығы
• Банк ісі
• Бизнесті бағалау
• Биология
• Бухгалтерлік іс
• Валеология
• Ветеринария
• География
• Геология, Геофизика, Геодезия
• Дін
• Ет, сүт, шарап өнімдері
• Жалпы тарих
• Жер кадастрі, Жылжымайтын мүлік
• Журналистика
• Информатика
• Кеден ісі
• Маркетинг
• Математика, Геометрия
• Медицина
• Мемлекеттік басқару
• Менеджмент
• Мұнай, Газ
• Мұрағат ісі
• Мәдениеттану
• ОБЖ (Основы безопасности жизнедеятельности)
• Педагогика
• Полиграфия
• Психология
• Салық
• Саясаттану
• Сақтандыру
• Сертификаттау, стандарттау
• Социология, Демография
• Спорт
• Статистика
• Тілтану, Филология
• Тарихи тұлғалар
• Тау-кен ісі
• Транспорт
• Туризм
• Физика
• Философия
• Халықаралық қатынастар
• Химия
• Экология, Қоршаған ортаны қорғау
• Экономика
• Экономикалық география
• Электротехника
• Қазақстан тарихы
• Қаржы
• Құрылыс
• Құқық, Криминалистика
• Әдебиет
• Өнер, музыка
• Өнеркәсіп, Өндіріс