Паскаль тілінің көмегімен сұрыптау және іздеу алгоритмдерін құрастыру

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

 

МЫСАЛ: N бүтін сандардан тұратын А массивін өсу реті бойынша сұрыптау.

 

program Sort_Vybor1;

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

N,i,m,k,x : integer;

begin

write('массив элементтерінің саны');  

read(N);

for i:=1 to n do read(A[i]);

for k:=n downto 2 do { k - max іздеу үшін элемент саны}

begin

m:=1; { m -  max орны}

for i:=2 to k do if A[i]>A[m] then m:=i;

 

{m нөмір мен k нөмірдегі элементтер орнын ауыстырамыз}

x:=A[m]; A[m]:=A[k]; A[k]:=x;

end;

for i:=1 to n do write(A[i],' '); {реттелген массив}

end.

 

МЫСАЛ: Бір мезгілде max және min табу есебі.

 

program Sort_Vybor2;

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

N,i,m,k,x,p : integer;

begin

write('массив элементі саны');

read(N);

for i:=1 to n do 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-ға дейінгі элементтер арасында ізделінеді}

for i:=k+1 to n-k+1 do

if A[i]>A[m] then m:=i

else if A[i]<A[p] then p:=i;

{p нөмірі мен k нөмірі элементтерін орындарымен ауыстырамыз}

x:=A[p]; A[p]:=A[k]; A[k]:=x;

if m=k then m:=p;

{егер max k орында тұрса, онда қазір ол p орында тұрады}

{m нөмірі мен n-k+1 нөмірі элементтерін орындарымен ауыстырамыз}

x:=A[m]; A[m]:=A[n-k+1]; A[n-k+1]:=x;

end;

for i:=1 to n do write(A[i],' '); {реттелген массив}

end.

2.2.2 Айырбастау бойынша сұрыптау («көбікше» әдісі)

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

 

МЫСАЛ: N бүтін сандардан тұратын А массивін өспелі бағытта айырбастау бойынша сұрыптау. (Базалық нұсқасы)

 

program Sort_Obmen1;

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

N,i,k,x : integer;

begin

write(' массив элементтерінің саны');

read(N);

for i:=1 to n do read(A[i]);

for k:=n-1 downto 1 do { k – салыстырылатын парлар саны }

for i:=1 to k do

if A[i]>A[i+1] then

{көршілес элементтермен орындарын ауыстыру}

begin  x:=A[i];  A[i]:=A[i+1];  A[i+1]:=x;  end;

for i:=1 to n do write(A[i],' '); {реттелген массив}

end.

 

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

 

МЫСАЛ: Ауыстыруларды тексеру арқылы айырбастау бойынша сұрыптау.

 

program Sort_Obmen2;

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

N,i,k,x : integer; p:boolean;

begin

write('массив элементтерінің саны');

read(N);

for i:=1 to n do read(A[i]);

k:=n-1; {бірінші сүзгі кезіндегі парлар саны}

p:=true; {логикалық айнымалы p ақиқат, егер алмастырулар

                болса, онда сұрыптауды жалғастыру}

while p do

begin

p:=false;

{Жаңа сүзгінің басталу. Әлі алмастырулар болған жоқ.}

for i:=1 to k do

if A[i]>A[i+1] then

begin

 

x:=A[i]; A[i]:=A[i+1]; A[i+1]:=x;

{элементтердің орындарын ауыстыру}

p:=true; {алмастыру жағдайын есте сақтау}

end;

k:=k-1;

{келесі сүзгі үшін парлар санын азайтамыз}

end;

for i:=1 to n do write(A[i],' '); {реттелген массив}

end.

 

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

 

МЫСАЛ: Соңғы алмастыру орнын есте сақтау арқылы айырбастау бойынша сұрыптау.

 

program Sort_Obmen3;

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

N,i,k,x,m : integer;

begin

write('массив элементтерінің саны');

read(N);

for i:=1 to n do read(A[i]);

k:=n-1; {бірінші сүзгі кезіндегі парлар саны}

while k>0 do

begin

m:=0;

{бұл сүзгі кезінде ауыстырулар болған жоқ, орын 0 тең}

for i:=1 to k do

if A[i]>A[i+1] then

begin

x:=A[i]; A[i]:=A[i+1]; A[i+1]:=x; {элементтер  орындарын ауыстырамыз} 

m:=i; {және алмастырған орындарды есте сақтаймыз}

end;

k:=m-1; {парлар саны соңғы ауыстырылған орынға байланысты}

end;

for i:=1 to n do write(A[i],' '); {реттелген массив}

end.

 

2.2.3 Мойындық (шейкерлі) сұрыптау

Бұл алгоритмнің негізгі мағынасы алмастыру бойынша сұрыптауға жатады. Айрымашылығы, алмастыру бойынша сұрыптау тек бір бағыт бойынша жүргізілетіндігін байқадық, ал бұл жағдайда бағыт әрбір рет өзгеріп тұрады. Мойындық сұрыптауда ауыстырулар туралы және соңғы алмастыру жасалған орынды есте сақтап отырады. Базалық алгоритмде екілік сүзгі саны N div 2 –ге тең. Мойындық сұрыптаудың есептелуі O(N*N).

 

МЫСАЛ: N нақты сандарынан тұратын А массивін өсу реті бойынша мойындық сұрыптау.

 

program Shaker;

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

N,i,k,x,j,d : integer;

begin

write('массива элементтерінің саны');

read(N);

for i:=1 to n do 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

{көршілес элементтерді орындарымен ауыстырамыз}

begin x:=A[i]; A[i]:=A[i+d]; A[i+d]:=x; end;

i:=i+d;

end;

d:=-d;

{қозғалыс бағытын кері бағытқа ауыстырамыз}

end;

for i:=1 to n do write(A[i],' '); {реттелген массив}

end.

2.2.4 Енгізу арқылы сұрыптау

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

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

Сызықтық іздеуді пайдалану кезінде есептелуі енгізу арқылы сұрыптауды қосқанда O(N*N), екілік іздеуді пайдалану кезінде - O(N*LogN) (2 негіздегі лографимдеу түрі қолданылады)

 

МЫСАЛ: N  нақты сандарынан тұратын А массивін өсу реті бойынша сұрыптауда сызықтық ісдеуді енгізуді пайдалану.

 

program Sort_Include1;

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

N,i,k,x : integer;

begin

write(' массива элементтерінің саны');

read(N);

read(A[1]); {for i:=1 to n do read(A[i]);}

{k - реттелген массив бөлігінің саны}

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 нақты сандарынан тұратын А массивін өсу реті бойынша екілік іздеуді енгізуді қолданып сұрыптау.

 

program Sort_Include2;

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

N,i,k,x,c,left,right : integer;

begin

write('массив элементтерінің саны');  read(N);

read(A[1]); {for i:=1 to n do read(A[i]);}

{k – массивтің реттелген бөлігіндегі элементтер саны}

for k:=1 to n-1 do

begin

read(x); {x:=A[k+1];}

left:=1; right:=k;

{ізделінетін бөліктің оң және сол шекарасы}

while left<right do

{соңғы енгізілу үшін екілік іздестіру}

begin

c:=(left+right+1) div 2;

{үлкен жағына қарай дөңгелектеген ортасы}

if x>=A[c] then left:=c

{ортаның оң жақ бөлігін аламыз}

else right:=c-1; {ортаны қоспағандағы сол жақ бөлігін аламыз} 

end;

 

if x>=A[left] then left:=left+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.

2.2.5 Хоар сұрыптамасы

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

Қандайда да бір элемент мәні, көбінесе ортаңғысын Х айнымалысына жазады. Массив элементтері қарастырылады. Солдан-оңға қарай қозғалыста Х элементіне тең немесе одан үлкен элементті іздейміз. Ал, оңнан-солға қарай қозғалыста Х-қа тең немсес одан үлкен элементті іздейміз. Табылған элементтер орындары ауыстырылады және қарсы іздеу жалғасытырылады.

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

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

 

МЫСАЛ: N нақты сандарынан тұратын А массивін өсу реті бойынша жылдам сұрыптау.

 

program Quick_Sort;

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

N,i : integer;

{Ішкі программаға сұрыпайтын бөліктің оң және сол жақ шекаралары  беріледі}

procedure QSort(L,R:integer);

var  X,y,i,j:integer;

begin

X:=A[(L+R) div 2];

i:=L; j:=R;

while i<=j do

begin

while A[i]<X do i:=i+1;

while A[j]>X do j:=j-1;

if i<=j then

begin

y:=A[i]; A[i]:=A[j]; A[j]:=y;

i:=i+1; j:=j-1;

end;

end;

if L<j then QSort(L,j);

if i<R then QSort(i,R);

end;

begin

write('массив элементтерінің саны');

read(N);

for i:=1 to n do read(A[i]);

QSort(1,n); {элементтерді біріншіден n-шіге дейін реттеу}

for i:=1 to n do write(A[i],' '); {реттелген массив}

end.

 

2.2.6 Индексті векторларды пайдалану арқылы сұрыптау

Алдында айтылған сұрыптау әдістерінен айырмашылығы, бұл өз бетінше жұмыс жасайтын алгоритм емес, ол кез келгеніне қолдануға болатын тәсіл көрсетеді. Ол тәсіл негізінен қосымша В массивін енгізу арқылы орындалады, оны индекстер векторы  деп атау қалыптасқан. Ондағы сандар А-ның элементтеріне қандай қатар бойынша қарау керктігіне байланысты, мысалы: Массив А: 4 7 3 5 Массив B : 3 1 4 2  {A[3] A[1] A[4] A[2] }

Программа басында индекстер векторы  В  1-ден N-ге дейінгі натурал сандар ретімен жазылады. Кез келген сұрыптау кезінде A[i] элементінің орнына A[B[i]] элементін шақырады. Бұл А массиві элементтерінің орнын ауыстыру үшін емес, олардың индекстерін, яғни В массиві элементтерін алмастыру үшін жасалған.

 

 

Зертханалық жұмыс

«Бір өлшемді және көп өлшемді массивтер»

     Жұмыстың мақсаты: Массивтерді есептер шығару барысында пайдалана білу, бір өлшемді және көп өлшемді массивтерді  типтер және айнымалылар бөлімінде сипаттай білу; массив элементтерін енгізу жолдарын білу, өлшемі айнымалы болып келген массивтерді сипаттай білу; массив элементтеріне әртүрлі операциялар:іздеу, сұрыптау, алмастыру операцияларын қолдана білу іскерлігі мен дағдысын  қалыптастыру.

Сабақтың  мазмұны

Паскаль тілінде  массив:

 атау : массив [индекстердің алғашқы .. соңғы  мәні] OF элемент типі – түрінде  жазылады.

Егер программада  массив пайдаланылатын болса, онда ол айнымалы (VAR) бөлігінде немесе тип (TYPE) бөлігінде бейнеленуі қажет.

Массив айнымалы бөлігінде былай бейнеленеді:

VAR       массив аты : ARRAY[t1]  OF  t2;

Мұндағы ARRAY (массив), OF (одан) - қызмет сөздері, t1-REAL, ІNTEGER базалық типінен өзге кез келген стандартты тип. Индекстің типі ретінде шектелген, саналатын, логикалық және литерлік типтер пайдаланылады. Мысалы,

Var   lіt=array[char] of real;

ogr=array[5..15] of char;

bol=array[boolean] of іnteger;

t2-құраушылар  типі,  Паскаль тілінде пайдалануға болатын массив элементтерінің типі. Мұны пайдалансақ, жоғарыдағы мысалдағы массивті айнымалы бөлігінде былай бейнелеуге болады:

Var  a : array[1..5] of real

Мұндағы А  – элементтері REAL типтегі массив аты, ал индекс 1-ден 5-ке дейін өзгереді.

Егер массив атауында бір ғана индекс болса, онда ол массивті бір өлшемді, ал екі индекс болса - екі өлшемді және т.с.с. n индекс болса, n өлшемді массив дейді. Бір  өлшемді массив вектор элементтері, ал екі өлшемді массив матрица  деп аталады.

«Тікелей таңдау» әдісімен сұрыптау алгоритмі төмендегідей.

 

 

Program suruptau2;

Uses crt;

var c:array[1..100] of word;

    і,j,n,r,k:іnteger;

Begіn

wrіte('n=');  {массивтің  өлшемін енгізу}

readln(n);    

{массивті толтыру}

Randomіze;

  for і:=1 to n do

      c[і]:=random(100);

  for і:=1 to n do    {алғашқы массивті шығару}

    wrіteln('c[',і,']=',c[і],' ');

    {массив  элементтерін сұрыптау}

    for і:=1 to n-1 do

                  begіn

                  k:=і;

                  r:=c[і];

                  {массив элементтерінің қалған  бөлігінен ең кіші элементін  іздеу}

    for j:=і+1 to n do

    іf c[j]<r then

            begіn

              k:=j;

              r:=c[j]; end;

              c[k]:=c[і];

              c[і]:=r;

           end;

           {сұрыпталған  массив элементтерін  шығару}

      wrіteln('suruptalgan massіv');

      for і:=1 to n do

    wrіteln('c[',і,']=',c[і]);

    repeat untіl keypressed;

  end.

 

2.3 Дербес орындайтын  жаттығулары

1. Бүтін сандардан құрылған А(n) массивіндегі берілген Х санына тең болатын элементтер санын табыңдар.
2. Бүтін сандардан құрылған элементтері әртүрлі А(n) және В(n) массивтері берілген. Осы массивтердің ортақ элементтерін экранға шығаратын программа құрыңдар.
3. Р және п натурал сандары мен а₁,…,а_n бүтін сандары берілген. а₁,…,а_n тізбегінің Р санына еселі болатын мүшелерінің көбейтіндісін табыңдар.
4. Р, q және а₁,…,а_n бүтін сандары берілген (P>q>=0). а₁,…,а_n тізбегіндегі модулі Р-ға бөлгенде q қалдық беретін мүшелерін нольмен алмастырыңдар.
5. а₁,…,а_n тізбегіндегі