Қазақстан республикасының бiлiм және ғылым министрлiгi

1. 
   Массивтерді сұрыптайтын негізгі әдістер туралы айтып беріңіз?
   
2. 
   Массивті сұрыптау кезеңінде қалай бейнелеуге болады?
   
3. 
   Массивті сұрыптау үшін қандай қосымша процедуралар мен функцияларды дайындап қою керек?
   

№ 1 практикалық сабақты орындауға арналған методикалық нұсқаулар

Кесте 1.1. Көпіршік әдісіне мысалы

  Бағдарлама 1.1.

ПРОГРАММА 1.1. КӨПІРШІК ӘДІСІ.

 PROGRAM BS;

VAR I,J,X,N:INTEGER;

A:ARRAY[0..50] OF INTEGER;

BEGIN

WRITELN('массивтің ұзындығын беріңіз');

WRITELN('массив элементтерін беріңіз');

FOR I:=1 TO N DO READ(A[I]);

FOR I:=2 TO N DO FOR J:=N DOWNTO I DO IF A[J-1]>A[J] THEN BEGIN

X:=A[J-1];

A[J-1]:=A[J];

A[J]:=X

END;

FOR I:=1 TO N DO WRITE(A[I],' ')

END.

 Бұл әдістің жақсартылған нұсқасы Шейкерлік сұрыптау деп аталады

Көпіршік және шейкерлік алгоритмдерінің анализі.

Алмастырулар саны

C = (n² – n)/2,

Ал орын ауыстырулардың минималды, ортақ және максималды саны келесілерге сәйкес

M = 0, M_avg = 3*(n² – n)/2, M_max = 3*(n² – n)/4

 ПРОГРАММА 1.2. ШЕЙКЕР СҰРЫПТАУЫ.

 PROGRAM SS;

VAR

A:ARRAY[0..50] OF INTEGER;

BEGIN

WRITELN('массивтің ұзындығын еңгізіңіз’);

WRITELN('массивті еңгізіңіз');

FOR I:=1 TO N DO READ(A[I]);

L:=2;

K:=N;

FOR J:=R DOWNTO L DO IF A[J-1]>A[J] THEN BEGIN

X:=A[J-1];

A[J-1]:=A[J];

A[J]:=X;

K:=J

L:=K+1;

X:=A[J-1];

A[J-1]:=A[J];

A[J]:=X;

END;

UNTIL L>R;

WRITELN('нәтиже:');

FOR I:=1 TO N DO WRITE(A[I],' ')

END.

 №1 практикалық сабаққа тапсырма

1. 
   Жоғары көрсетілген деректерді сұрыптау әдістерін түсініп, өздерінің тапсырмаларында вариант бойынша орындаңдар.
   
2. 
   Бағдарламаның листингін басып шығару.
   
3. 
   Жұмысты ауызша қорғаңыз
   

№2 практикалық жұмыс. Тікелей таңдау әдісі.

№ 2 практикалық сабақты орындауға арналған методикалық нұсқаулар

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

Әдістің алгоритмі:

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

 БАҒДАРЛАМА 2.1. Тікелей таңдау бойынша сұрыптау.

PROGRAM SS;

VAR I,J,R,X,N:INTEGER;

A:ARRAY[0..50] OF INTEGER;

BEGIN

READ(N);

FOR I:=1 TO N DO READ(A[I]);

FOR I:=1 TO N-1 DO BEGIN

R:=I;

FOR J:=I+1 TO N DO IF A[J]

R:=J;

X:=A[R]

A[R]:=A[I];

A[I]:=X

END;

FOR I:=1 TO N DO WRITE(A[I],' ')

END.

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

1. 
   Жоғары көрсетілген деректерді сұрыптау әдістерін түсініп, өздерінің тапсырмаларында вариант бойынша орындаңдар.
   
2. 
   Бағдарламаның листингін басып шығару.
   
3. 
   Жұмысты ауызша қорғаңыз
   

№ 3 практикалық сабақты орындауға арналған методикалық нұсқаулар

Бұл әдіс 1959 жылы Donald Lewis Shell авторының атынан ұсынылды. Бұл алгоритмнің негізгі мәні мынада:

• 
  Массивтегі ретсіздіктен құтыламыз;
  
• 
  Бір-бірінен алшақ орналасқан элементтерді салыстырамыз;
  
• 
  Салыстырып отырған интервалдар бірте-бірте кемиді;
  
• 
  Соңғы қадамдарды элементтер жай ғана орые алмастырумен шектеледі.
  

Алгоритмнің өзі t = 4 үшін жазбасы 3.1. бағдарламасында берілген

 ПРОГРАММА 3.1. ШЕЛЛ СҰРЫПТАУЫ.

 PROGRAM SHELLS;

CONST T=4;

H: ARRAY[1..4] OF INTEGER = (15,7,3,1);

VAR

I,J,K,S,X,N,M:INTEGER;

BEGIN

READ(N);

FOR I:=1 TO N DO READ(A[I]);

FOR M:=1 TO T DO BEGIN

K:=H[M];

FOR I:=K+1 TO N DO BEGIN

X:=A[I];

J:=I-K;

INC(S);

WHILE X

A[J+K]:=A[J];

J:=J-K

A[J+K]:=X

END;

END;

FOR I:=1 TO N DO WRITE(A[I],' ')

END.

№3 практикалық сабаққа тапсырма

1. 
   Жоғары көрсетілген деректерді сұрыптау әдістерін түсініп, өздерінің тапсырмаларында вариант бойынша орындаңдар.
   
2. 
   Бағдарламаның листингін басып шығару.
   
3. 
   Жұмысты ауызша қорғаңыз
   

Бұл әдісті 1962 жылы Charles Antony Richard Hoare ұсынды. Оны басқаша жылдам сұрыптау деп те атайды. Бұл әдістің мәні мынада: тізбектің оны екі бөлікке бөлетіндей элементін табу; бөлгіштен кіші және бөлгіштен кіші емес элементтерге. Бұл әдісті көптеген жолдармен іске асыруға болады.

program Quitsort;
 uses
   crt;
 Const
  N=10;
 Type
  Mas=array[1..n] of integer;
var
  a: mas;
  k: integer;
function Part(l, r: integer):integer;
var
  v, i, j, b: integer;
begin
  V:=a[r];
  I:=l-1;
  j:=r;
  repeat
    repeat
      dec(j)
    until (a[j]<=v) or (j=i+1);
    repeat
      inc(i)
    until (a[i]>=v) or (i=j-1);
    b:=a[i];
    a[i]:=a[j];
    a[j]:=b;
  until i>=j;
  a[j]:=a[i];
  a[i]:= a[r];
  a[r]:=b;
  part:=i;
end;
procedure QuickSort(l, t: integer);
var i: integer;
begin
  if l    begin
      i:=part(l, t);
      QuickSort(l,i-1);
      QuickSort(i+1,t);
    end;
end;
begin
  clrscr;
  randomize;
  for k:=1 to 10 do
    begin
      a[k]:=random(100);
      write(a[k]:3);
    end;
  QuickSort(1,n);
  writeln;
  for k:=1 to n do
    write(a[k]:3);
  readln;
end.

Мысалы:
60,79, 82, 58, 39, 9, 54, 92, 44, 32

1. 
   Жоғары көрсетілген деректерді сұрыптау әдістерін түсініп, өздерінің тапсырмаларында вариант бойынша орындаңдар.
   
2. 
   Бағдарламаның листингін басып шығару.
   
3. 
   Жұмысты ауызша қорғаңыз
   

№ 5 практикалық сабақты орындауға арналған методикалық нұсқаулар

Сандық алгоритмдер сандармен математикалық есептеулер жүргізуге арналған, ал сандық емес алгоритмдер әртүрлі құрылымданған мәліметтермен жұмыс істейді. Ең маңызды есептеусіз алгоритмдердің бірі болып сұрыптау және іздеу табылады. Объектілердің берілген тізбегін қандай да бір анықталған ретпен қайта топтастыратын үрдісті сұрыптау деп атайды. Сұрыптаудың мақсаты – сұрыпталған тізбекте қажетті элементтерді іздестіруді жеңілдету. Сұрыптау алгоритмдері мәліметтер құрылымын таңдауға тәуелді, сондықтан сұрыптау әдістерін екі түрге бөледі: ішкі сұрыптау алгоритмдері(массивтерді сұрыптау) және сыртқы сұрыптау алгоритмдері(файлдарды сұрыптау). Сандық емес алгоритмдер үшін жазбалар массивтерін сұрыптау тән. Кілттік өріс – сызықтық тәртіптегі қатынаспен анықталатындай мәлімет типімен берілген өріс. Егер бірдей кілтті элементтердің салыстырмалы реті сұрыптауда өзгермесе, онда сұрыптау әдісі орнықты деп аталады. Ішкі сұрыптаулар алгоритмдері – бұл ішкі жадтағы мәліметтерді сұрыптау алгоритмдері, бұл жағдайда қолайлы құрылым – массив. Массивтерді сұрыптау алгоритмдеріне қойылатын басты талап – жадтың экономды пайдаланылуы. Элементтерді in situ (яғни элементтерді қайта топтастыруды жадтың сол жерінде жүргізеді) сұрыптайтын қарапайым сұрыптау алгоритмдері бар: кірулермен сұрыптау, таңдаумен сұрыптау, алмасумен сұрыптау («көбікше» әдісі). Сұрыптаудың жетілдірілген қарапайым әдістері: кемімелі өсімшелі кіру бойынша сұрыптау (Шелл сұрыптауы), ағаш көмегімен сұрыптау (пирамидалық сұрыптау), бөліктеу арқылы сұрыптау (жылдам сұрыптау). Кірулермен сұрыптау – элементтер шартты түрде дайын тізбекке a1,…, ai-1 және кіретін тізбекке ai,…, an бөлінеді, содан кейін әрбір қадамда, i=2 бастап және i-ді бірлікке арттыра отырып, кіретін тізбектің i-ші элементін алып дайын тізбектің тиісті орнына кіргізе береді. Таңдаумен сұрыптау – ең кіші кілтті элемент таңдалады, содан кейін ол бірінші a1 элементімен орын ауыстырылады. Алмасумен сұрыптау – барлық элементтер қажетінше сұрыпталғанша көрші элементтер өзара салыстырылып және орын ауыстырылады. Сурет.5. Массивті қарапайым сұрыптаудың модификацияланған әдісімен іріктеудің жалрыланған алгоритмі Кесте 5.1. Сұрыптау мысалысы Массивті қарастыру номері i Бастапқы массив Минималды элемент Орны ауыстырылатын элемент Орын ауыстырғаннан кейінгі массив Номер Мәні Номер Мәні  1  (2,8,1,3,7)  3  1  1  2  (1,8,2,3,7)  2  1,(8,2,3,7)  3  2  2  8  1,(2,8,3,7)  3  1,2,(8,3,7)  4  3  3  8  1,2,(3,8,7)  4  1,2,3,(8,7)  5  7  4  8  1,2,3,7,8 Келесі бейнеленулерді еңгізейік  :       К- минималды элементтің номері,       J – массив элементінің номері,       М және А(К)- массивтің минималды элементінің бір мәні,       i – орны ауыстырылатын элементтің номері,       А(i)- орны ауыстырылатын элементтің мәні. Онда қарапайым сұрыптаудың модификацияланған әдістің циклдік алгоритмі келесі түрге ие болады. Сурет.6. қарапайым сұрыптаудың модификацияланған әдістің циклдік алгоритмі

1. 
   Жоғары көрсетілген деректерді сұрыптау әдістерін түсініп, өздерінің тапсырмаларында вариант бойынша орындаңдар.
   
2. 
   Бағдарламаның листингін басып шығару.
   
3. 
   Жұмысты ауызша қорғаңыз