Сұрыптау әдістері реферат
Жоспар - www.topreferat.com.kz
Кіріспе
Негізгі бөлім
Сұрыптау әдістері:
Таңдау арқылы сұрыптау.
Алмастыру арқылы сұрыптау.
Индекстері арқылы сұрыптау.
Енгізу арқылы сұрыптау.
Біріктіру арқылы сұрыптау.
Қорытынды
Пайдаланылған әдебиеттер
Жұмыс түрі: [b]Реферат[/b]
Пәні: [b]Соңғы қосылған рефераттар[/b]
Жұмыс көлемі: [b]- бет[/b]
[b]-----------------------------------------------------------------------------------[/b]
[b][/b]
[b]РЕФЕРАТТЫҢ ҚЫСҚАРТЫЛҒАН МӘТІНІ[/b]
ЖОСПАР
Кіріспе
Негізгі бөлім
Сұрыптау әдістері:
Таңдау арқылы сұрыптау.
Алмастыру арқылы сұрыптау.
Индекстері арқылы сұрыптау.
Енгізу арқылы сұрыптау.
Біріктіру арқылы сұрыптау.
Қорытынды
Пайдаланылған әдебиеттер
КІРІСПЕ
Қарапайым типтер қатарына жататын стандартты (Integer,
Бір типтес берілгендерден құралып, барлық элементтеріне
Массив сипаттамалары:
Типі – массив элементтерінің жалпы типі;
Көлемі – массив индекстерінің саны;
Шектелімі - әрбір индекстердің шектеу бойынша
Пішімі – көлем және шектеулер жиындары.
Массивтер элементтерімен жұмыс жасау барысында, массив
Массивтерді қолдану үшін оларды типтер (type)
Жалпы жазылу түрі:
Type
Массив типінің атауы = array [индекс
Var
Массив атауы:массив типінің атауы
Мұндағы:
Массив типінің атауы – массив элементтерінің
Индекс типі – тізбектелген немесе шектелген
Элемент типі – массив элементтерінің типін
Берілген массивтің кез – келген элементтеріне
Turbo Pascal программалау тілі бiр өлшемдi
Екi өлшемдi немесе көп өлшемдi массивтермен
Екi өлшемдi массивтi var бөлiмiнде сипаттаудың
var
Массив атауы: array [a1..an,b1..bn] of элемент
Екі өлшемді массивтi type бөлiмiнде сипаттаудың
type
Массив типінің атауы = array [a1..an,b1..bn]
Var
Массив атауы: массив типінің атауы;
Мұндағы,a1..an,b1..bn – екі өлшемді массивтің көлемі:
a1 және an – массив қатарының
b1 және bn – массив бағанының
Массивтің элементтерін белгілі бір заңдылықпен орындарын
СҰРЫПТАУ ӘДІСТЕРІ
Тізімді реттеу
Сұрыптау кез – келген түрдегі кестелерді
Мысал 1:
Элемент нөмірі
Кестенің бастапқы түрі
Өсу бойынша реттелген кесте
Мысал 2:
Элемент нөмірі
Кестенің бастапқы түрі
Өсу бойынша реттелген кесте
Мұндағы индекстер бір мәнді элементтердің ретін
Литерлік кестені сұрыптау әдетте ондағы мәндерді
Мысал 3:
Элемент нөмірі
Кестенің бастапқы түрі
Өсу бойынша реттелген кесте
Егер реттеген кезде бірдей мәнді элементтердің
Сұрыптауды өзіндік жұмыс деп те (мысалы,
Жедел жадыда орналасқан ,бізге мәлім, сұрыптау
1.Элементтерді таңдау арқылы сұрыптау
Бұл сұрыптаудың өте қолайлы түрі, әдетте
Алгоритмі:
Өлшемі n болатын А массивін толтыру
i:=1;
Индексі i-ден басталатын массив элементтерінің ішінен
A[i] және A[j] элементтерінің орндарын ауыстыру;
i:=i+1 мәні үшін i:=n болғанға дейін
Сұрыпталған A массивін экранға шығару;
1
7 13
1
1 13
1
1 3
1
1 3
1
1 3
1
1 3
1
1
1
1 3
1.1 сурет
Program Prost_1.2;
Const n=8;
type MasType = array [1..n]
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]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
Readln;
End.
Бұл программада берілген массив бөлігінің ең
2.Элементтерді алмастыру арқылы сұрыптау
Қайтсе де сұрыптаудың кез – келген
Алгоритмі:
Өлшемі n болатын А массивін толтыру
i:=1;
Егер А[i]>A[i+1] болса, онда олардың орындарын
i:=i+1 мәні үшін i:=n болғанға дейін
Ең болмағанда бір алмастыру орындалса,екі қадамнан
Сұрыпталған A массивін экранға шығару;
Қайталау реті Массив Алмастыру саны
7 13 20 3 9 18
1 7 13 3 9 18
2 7 3 9 13 4
3 3 7 9 4 1
4 3 7 4 1 9
5 3 4 1 7 9
6 3 1 4 7 9
7 1 3 4 7 9
8 1 3 4 7 9
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
Readln;
End.
3.Массивті индекстері арқылы сұрыптау
n элементтен тұратын A сандар массиві
Алгоритмі:
Өлшемі n болатын А массивін толтыру
Өлшемі n болатын IDX массивін 1-
i:=n;
j:=i-1;
Егер А[j]>A[i] болса, онда IDX[j]:=IDX[j]+1, әйтпесе
j:=j-1 мәні үшін j=2 болғанша 5
i:=i-1 мәні үшін i=1 болғанша 4,5,6
IDX массивін экранға шығару;
Қайталау реті 20 27 36 17
1 1 1 1 1 1
1 2 2 2 2 2
2 3 3 3 2 3
3 3 3 4 2 3
4 3 4 5 2 5
5 4 5 6 2 5
6 4 5 8 2 5
7 4 6 8 2 5
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]IDX[i]:=IDX[i]+1;
Writeln; Writeln(‘Өсуіне қарай сұрыптау индекстері:’);
For i:=1 to n do
Readln;
End.
4.Элементтерді енгізу тәсілімен сұрыптау
Бұл тәсілдің мәні массивтің сұрыпталмаған бөлігінен
Алгоритмі:
Өлшемі n болатын А массивін толтыру
i:=2;
j:=i-1;
Егер А[j+1]=A[j] болса, онда олардың орындарын
j:=0 болғанша 4 қадамды қайталау;
i:=i+1;
i=n болғанша 3,4,5,6 қадамдарды қайталау;
Program Prost_4.2;
Const n=8;
var A: array [1..n] of
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]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
Readln;
End.
1
25 13 20 3 9 18
1
1
13 25 20 3 9 18
1
13 20 25 3 9 18
1
3 13 20 25 9 18
1
3 9 13 20 25 18
1
3 9 13 18 20 25
1
3 4 9 13 18 20
1
1 3 4 9 13 18
4.1 сурет
5. Біріктіру тәсілімен сұрыптау
Бұл тәсіл бойынша:
берілген массив бірнеше бөліктерге (кіші массивтерге)
бірінші және екінші бөліктен сұрыпталған бір
осы процесс соңғы екі бөлік біріккенге
Массивті бөліктерге бөліп, бөлек-бөлек сұрыптау оқушыға
Алгоритмі:
А және B массивтерін толтыру және
i:=1; j:=1; k:=0; (i,j және k
k:=k+1;
Егер А[i]i>m немесе j>n болғанша 3,4 қадамдарды
Егер i>m болса,онда B массивінің қалған
Егер j>n,онда А массивінің қалған элементтерін
C массивін экранға шығару;
5.1 суретте осы алгоритмді пайдаланғандағы, өлшемдері
i=1
1 қадам А массиві 4 10
C массиві 4
B массиві 6 8 15 17
i=2
2 қадам А массиві 4 10
C массиві 4 6
B массиві 6 8 15 17
i=2
3 қадам А массиві 4 10
C массиві 4 6 8
B массиві 6 8 15 17
i=2
4 қадам А массиві 4 10
C массиві 4 6 8 10
B массиві 6 8 15 17
i=3
5 қадам А массиві 4 10
C массиві 4 6 8 10
B массиві 6 8 15 17
i=4
6 қадам А массиві 4 10
C массиві 4 6 8 10
B массиві 6 8 15 17
i=4
7 қадам А массиві 4 10
C массиві 4 6 8 10
B массиві 6 8 15 17
i=4
8 қадам А массиві 4 10
C массиві 4 6 8 10
B массиві 6 8 15 17
i=5
9 қадам А массиві 4 10
C массиві 4 6 8 10
B массиві 6 8 15 17
i=6
10 қадам А массиві 4 10
C массиві 4 6 8 10
B массиві 6 8 15 17
i=6
11 қадам А массиві 4 10
C массиві 4 6 8 10
B массиві 6 8 15 17
i=6
12 қадам А массиві 4 10
C массиві 4 6 8 10
B массиві 6 8 15 17
i=7
13 қадам А массиві 4 10
C массиві 4 6 8 10
B массиві 6 8 15 17
i=7
14 қадам А массиві 4 10
C массиві 4 6 8 10
B массиві 6 8 15 17
5.1 сурет
Program Prost_5.2;
Const m=6;n=8;
var A:
B: array [1..n] of integer;
C: array [1..m+n] of integer;
i, j, k:integer;
begin
Randomize;Write(‘A массиві:’);
For i:=1 to m do
Begin
if i=1 then A[i]:=Random(8)+1
else A[i]:=A[i-1]+Random(9)+1;
Write(A[i]:4);
End;
Writeln;Write(‘B массиві:’)
For i:=1 to n do
Begin
if i=1 then B[i]:=Random(8)+1
else B[i]:=B[i-1]+Random(9)+1;
Write(B[i]:4); end;
i:=1; j:=1; k:=1;
While (iBegin
If A[i]then begin C[k]:=A[i]; inc(i); end
else begin C[k]:=B[j]; inc(j); end;
inc(k); end;
While iWhile jWriteln; Write(‘С массиві:’);
For i:=1 to m+n do
Write(C[i]:4);
Readln;
End.
ҚОРЫТЫНДЫ
Деректерді реттеудің практикалық жағынан алғандағы проблемасы:
сұрыптаудың әр түрлі әдістерінің тиімді және
Сұрыптау бағдарламалаудың кез-келген саласында қолданылады, тіпті
Сұрыптаудың әрбір алгоритмін үш бөлікке бөліп
салыстыру, қос элементтің реттелуін анықтайды;
алмастыру, қос элементтің орнын ауыстырады;
өздігінен сұрыпталу алгоритмі,тізбектің барлық элементтері реттеліп
Біз салыстырғалы отырған алгоритмдерді сұрыптаудың келесі
Көпіршікті әдіс.
(әдіс сонымен қатар таңдау арқылы алмастыру
Бұл әдістің мәні оның атауында жатыр.
Шейкерлі әдіс.
Бұл әдіс автор атынан Donald Lewis
Хоор әдісі.
Бұл әдісті 1962 жылы Charles Antony
элементтерге.Бұл әдісті көптеген жолдармен іске асыруға
ПАЙДАЛАНЫЛҒАН ӘДЕБИЕТТЕР:
Бурин Е.А. Программирование на
Вирт Н. Алгоритмы иструктуры
Досмайлов Т.К. Программалау тілі
Кнут Теория алгоритмов.
Матросов В.Л. Теория алгоритмов.
Нақысбеков Б.,Халыкова Б. Паскаль
Новиков В.С.,Парфилова Н.И. Паскаль.
Семашко Г.Л., Салтыков Г.Л.
2
16
1
2
3
4
5
6
7
1
3
5
6
7
[/b]
