Курстық жұмыс: Технология | Дүкен (чегі) » ZHARAR

[quote]

Кіріспе
1. Есептің қойылымы
2. Қолданылған әдістер
3. Есептің алгоритмі
4. Бағдарламаның баяндалуы
4.1 Жалпы мағлұматтар
4.2 Функциялдық тағайындалуы (қолдануы)
4.3 Логикалық құрылымның баяндалуы
4.4 Шақыру және жіктеу
4.5 Қажетті техникалық жабдықтар
4.6 Кіріс мәліметтер (енгізу)
4.7 Шығыс мәліметтер (шығару)
5. Қортынды
6. Қолданылған әдебиеттер

2. Қолданылған әдістер

Сұрыптау алгоритмдерi

Сұрыптаудың ең қарапайым есебi массив элементтерiнiң өсу не кему ретiмен орналастыру болып табылады. Басқа есеп болып, берiлген белгiлер бойынша массив элементтерiн реттеу. Әдетте мұндай белгi ретiнде аргументi массив элементтерi болып табылатын белгiлi функция мәнi болып табылады. Бұл функцияны реттеушi функция деп атау қабылданған.
Сұрыптаудың әр түрлi тәсiлдерi бар. Әрбiр тәсiлдi N бүтiн сандардан өспелi массивтi сұрыпттау мысалында көрсетемiз.
Таңдау арқылы сұрыптау
Тәсiл идеясы массивтiң максималды элементiн тауып, оны соңғы элемент (N номерлi) орнымен ауыстырылады. Содан кейiн максималды элемент N-1 орынға дейiн iзделiп, сол N-1 орынға қойылады және т.с.с. Максимум емес, минимум элемент iзделiп, оны бiрiншi, екiншi және т.с.с. орынға қоюға болады. Сонымен қатар бұл әдiстiң модификацияланған түрi – бiр мезетте максимум және минимум элементтердi iздеу қолданылады. Бұл жағдайда сыртқы циклдың қадамдар саны N div 2.

Мысалы: a массивiнiң N бүтiн сандарының өсуi бойынша таңдау арқылы сорттау.

Program Sort_Tandau1;
Var a:array[1..20] of integer;
N,i,m,k,x : integer;
Begin
write(‘Массив элементтерiнiң саны’);
read(N);
For i:=1 to n do
writeln(‘Массивтi енгiзiңiз’);
read(a[i]);
For k:=n downto 2 do { k – max-ты iздеуге қажеттi элементтер саны }
begin
m:=1; { m — max орны}
For i:=2 to k do if A[i]>A[m] then m:=i;
{ m және k номерлi элементтердi орындарымен ауыстырамыз}
x:=a[m]; a[m]:=a[k]; a[k]:=x;
end;
for i:=1 to n do write(a[i],’ ‘); {реттелген массив}
end.

Мысалы: Жоғарыдағы есеп, бiрақ бiр мезеттегi max пен min таңдау арқылы.

Program Sort_Tandau2;
Var a :array[1..100] of integer;
N,i,m,k,x,p : integer;
Begin
write(‘Массив элементтерiнiң саны’);
read(N);
For i:=1 to n do
writeln(‘Массивтi енгiзiңiз’);
read(a[i]);
For k:=1 to n div 2 do { k — max және min жұбының орны }
Begin
m:=k; { m — max орны }
p:=k; { p – min орны }
{max және min k-дан n-k+1 элементтер арасында iзделедi }
For i:=k+1 to n-k+1 do
if a[i]>a[m] then m:=i
else if a[i]a[i+1] then
{көршiлес элементтердi орындарымен ауыстырамыз}
Begin x:=a[i]; a[i]:=a[i+1]; a[i+1]:=x;
End;
For i:=1 to n do
write(a[i],’ ‘); {реттелген массив}
end.
Шейкерлi сұрыптау

Бұл алгоритм негiзiнен айырбас арқылы сұрыптаудың модификациясы болып табылады. Айырмашылығы айырбас арқылы сұрыптауда өтулер бiр жақты ғана болса, мұнда бағыт әрбiр рет сайын өзгерiп отырады. Сонымен қатар шейкерлi сұрыптауда айырбас фактi мен айырбастың соңғы орнын анықтауға болады. Негiзгi алгоритмде екiлiк өтулер саны N div 2-ге теi.

Мысалы: N бүтiн сандардан құралған А массивiн Шейкерлi сорттау арқылы өсу ретiмен орналастыру.

Program Shaker;
Var a:array[1..20] of integer;
N,i,k,x,j,d : integer;
Begin
write(‘Массив элементтерiнiң саны’);
read(N);
For i:=1 to n do
writeln(‘Массивтi енгiзiңiз’);
read(a[i]);
d:=1; i:=0;
For k:=n-1 downto 1 do { k – салыстырылатын жұптар саны }
Begin
i:=i+d;
For j:=1 to k do
Begin
If (a[i]-a[i+d])*d>0 then
{көршiлес элементтердi орындарымен ауыстыру}
Begin x:=a[i]; a[i]:=a[i+d]; a[i+d]:=x; end;
i:=i+d;
end;
d:=-d;
{қозғалыс бағытын қарама-қарсыға өзгертемiз}
end;
For i:=1 to n do write(a[i],’ ‘); {реттелген массив}
end.

Қосу арқылы сұрыптау

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

Мысалы: N бүтiн сандардан құралған А массивiн сызықты iздеуi бар қосу арқылы сұрыптау арқылы өсу ретiмен орналастыру.

Program Sort_Include1;
Var a:array[1..20] of integer;
N,i,k,x : integer;
Begin
write(‘Массив элементтерiнiң саны ‘);
read(N);
writeln(‘Массивтi енгiзiңiз’);
read(a[1]); {For i:=1 to n do read(a[i]);}
{k – массивтiң реттелген бөлiгiндегi элементтер саны}
For k:=1 to n-1 do
Begin
read(x); {x:=a[k+1];}
i:=k;
while (i>0)and(a[i]>x) do
begin
a[i+1]:=a[i];
i:=i-1;
end;
a[i+1]:=x;
end;
For i:=1 to n do write(a[i],’ ‘); {реттелген массив}
end.

Мысалы: N бүтiн сандардан құралған А массивiн екiлiк iздеуi бар қосу арқылы сұрыптау арқылы өсу ретiмен орналастыру.

Program Sort_Include2;
Var a :array[1..20] of integer;
N,i,k,x,c,left,right : integer;
Begin
write(‘Массив элементтерiнiң саны’);
read(N);
writeln(‘Массивтi енгiзiңiз’);
read(a[1]); {For i:=1 to n do read(a[i]);}
{k — массивтiң реттелген бөлiгiндегi элементтер саны }
For k:=1 to n-1 do
Begin
read(x); {x:=a[k+1];}
left:=1; right:=k;
{iздеуге керектi фрагменттiң оң және сол шекарасы}
while left=a[c] then left:=c
{ортасы мен оң жағын аламыз}
else right:=c-1; {ортасыз сол жағын аламыз}
end;
if x>=a[left] then left:=left+1;
{х қосылуға орын босата отырып, массивтi 1 орынға оңға жылжытамыз}
for i:=k downto left do a[i+1]:=A[i];
a[left]:=x;
end;
For i:=1 to n do write(A[i],’ ‘); {реттелген массив}
end.

Хоар сұрыптауы

Бұл сұрыптауды жылдам сұрыптау деп те атайды. Әдiстi 1962 жылы Оксфорд университетiнiң профессоры К.Хоар жасаған болатын. N бүтiн сандардан құралған А массивiн өсу ретiмен орналастыру принципiнiң жұмысын қарастырайық.
Қандай да бiр элементтiң мәнi (әдетте ортаңғы) Х айнымалысына жазылады. Массив элементтерi қарастырылады. Солдан-оңға қарай жылжығанда Х-тан үлкен не оған тең элемент iздеймiз. Ал оңнан-солға қарай жылжығанда Х-тан үлкен не тең элемент iздеймiз.Табылған элементтер орындарымен ауыстырылады және қарама-қарсы iздеу жалғастырылады.
Содан кейiн массив екiге бөлiнедi. Бiрiншiсiнде Х-тан кiшi не тең элементтер, ал оң жағында Х-тан үлкен не тең элементтер орналасады. А массивiн сұрыптаудағы алғашқы есептi алынған массив бөлiктерiн сұрыптаудағы екi есепшеге бөлуге болады.
Берiлген рекурсивтi алгоритмнiң бiр шақырылуының есептеу қиындығы сұрыпталатын массив үзiндiсiндегi элементтер санына пропорционал.
Мысалы: N бүтiн сандардан құралған А массивiн жылдам сұрыптау арқылы өсу ретiмен орналастыру.

Program Quick_Sort;
Var a:array[1..20] of integer;
N,i : integer;
{Процедураға сұрыпталатын үзiндiнiң оң және сол шекаралары берiледi}
Procedure QSort(L,R:integer);
Var X,y,i,j:integer;
Begin
X:=a[(L+R) div 2];
i:=L; j:=R;
while i