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

КІРІСПЕ

Қарапайым типтер қатарына жататын стандартты (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. Бурин Е.А. Программирование на языке Турбо Паскаль. А.,2000.
2. Вирт Н. Алгоритмы иструктуры данных.
3. Досмайлов Т.К. Программалау тілі Паскаль. А.,1996.
4. Кнут Теория алгоритмов.
5. Матросов В.Л. Теория алгоритмов.
6. Нақысбеков Б.,Халыкова Б. Паскаль тілінің негіздері. А.,1998.
7. Новиков В.С.,Парфилова Н.И. Паскаль. М.,1994.
8. Семашко Г.Л., Салтыков Г.Л. Программирование на языке Паскаль М.,1988.

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

ЖОСПАР

Кіріспе

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

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

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
7 13 20 3 9 18 4 1

1 2 3 4 5 6 7
8
1 13 20 3 9 18 4 7

1 2 3 4 5 6 7
8
1 3 20 13 9 18 4 7

1 2 3 4 5 6 7
8
1 3 4 13 9 18 20 7

1 2 3 4 5 6 7
8
1 3 4 7 9 18 20 13

1 2 3 4 5 6 7
8
1 3 4 7 9 18 20 13

1 2 3 4 5 6 7
8
1 3 4 7 9 13 20 18

1 2 3 4 5 6 7
8
1 3 4 7 9 13 18 20

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.Элементтерді алмастыру ... жалғасы

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