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

Нәтижесінде , алты элемент үшін 5+4+3+2+1 = 15 салыстыру және 8 орын ауыстырулар өткізілді.

Жалпы жағдайда, әр n-1 қадамда орташа n/2 салыстырулар өткізіледі, сондықтан салыстырулар саны үшін бағалау n(n-1)/2 жазбасымен бейнеленеді, яғни берілген әдіс O(n²) классына байланысты. Аналогті түрде, орын ауыстырулар саны да n² мәніне пропорционалды. Бұл әдіс ең тиімді емес сұрыптау әдісі болып табылады. Мысалы, 1000 элементтер үшін салыстырулар саны 500 мыңға жұық болады.

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

Көбікше әдістің бағдарламасының негізгі фрагменті:

for i := 2 to n do

begin

for j := n downto i do

if a[j-1] > a[j] then

begin temp := a[j-1]; a[j-1] := a[j]; a[j] := temp; end;

end;

Бағдарлама 1. Көбікше әдіс А

program puz_sort;

(*көбікше сұрыптау әдісі*)

const N=5;

type item: integer;

var a: array [1..n] of item; i, j: integer; x: item;

begin (*бастапқы массивті беру*)

for i:=1 to N do begin write ('элемент еңгізу a [', i, ']= ');

readln (a[i]);

end;

for i:=1 to N do begin write (a[i], ' ');

writeln;

(*көбікше сұрыптаудың алгоритмі*)

for i:=2 to n do for j:=n downto i do begin

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 begin write (a[i], ' ');

end;

end.

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

Бағдарлама 2. Көбікше әдіс В

 PROGRAM BS;

VAR I,J,X,N:INTEGER;

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

BEGIN

READ(N);

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

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

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

END.

Бағдарлама 3. Ауыстыруларды тексеру арқылы айырбастау бойынша сұрыптау.

program Sort_Obmen1;

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

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

begin

read(N);

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

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

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

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

while p do

begin

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

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;

end.

Бағдарлама 4. Соңғы алмастыру орнын есте сақтау арқылы айырбастау бойынша сұрыптау.

program Sort_Obmen2;

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

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

begin

read(N);

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

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

while k>0 do

begin

{бұл сүзгі кезінде ауыстырулар болған жоқ, орын 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;

end;

end.

1. 
   «Көпіршік» әдісінің ерекшелігі неде?
   
2. 
   Бұл сұрыптау әдісі қандай классқа жатады?
   
3. 
   Бұл әдіс тағы қалай аталады?
   
4. 
   Берілген сұрыптау әдісінің ішіне қандай цикл жатады?
   
5. 
   Берілген әдіс тиімді болып табылама?
   

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

Біріншіден, егер массив бөлігінде қозғалыстарда орын ауыстырулар болмаса онда массивтің бұл бөлігі сұрыпталған болып есептеледі, сондықтан, оны қарастырудан алып тастауға болады.

Екіншіден, массивтің соңынан басына дейін өткенде минималды элемент бірінші позицияға тұрады, ал максималды элемент тек бір позицияға оң жаққа қарай қозғалады.

Массивтің жұмыс бөлігінің шектері әр итерацияның орын ауыстыруында орнықтырылады. Массив рет бойынша оң жақтан сол жаққа және сол жақтан оң жаққа кезек кезек қарастырылады.

Бұл сұрыптаудың үздік жағдайы — сұрыпталған массив (О(n)), ең жаманы — кері бағытта сұрыпталған массив (O(n²)).

Салыстырулар санының ең кіші мәні Шейкер-сұрыптауында C=N-1. Бұл сұрыпталған массивте тек бір өтуге сәйкес (үздік жағдай)

Шейкер әдісінің бағдарламалық реализациясы:

Бағдарлама 5. Шейкер әдісі А

program sheiker_sort;

(*шейкерлік сұрыптау*)

const N=5;

type item= integer;

var a: array [1 n] of item; i, j, k, L, R: integer; x: item;

begin (*бастапқы массивті беру*)

for i: =1 to N do begin write ('элементтерді еңгізу а [', i, '] = ');

readln (a[i]);

end;

for i:=1 to N do begin write (a[i], ' ');

writeln;

(*шейкерлік сұрыптаудың алгоритмі*)

L: =2; R:=n; k:=n;

repeat

for j:=R downto L do begin

if a [j-l]>a[j] then begin x:=a [j‑1]; a [j‑1]:=a[j];

a[j]:=x; k:=-j

end;

end;

for j:=L to R do begin

if a [j-l]>a[j] then begin x:=a [j-l]

a [j-l]:=a[j]; a[j]:=x; k:=j

end;

end;

(*сұрыпталған массивті шығару*)

for i:=l to N do

begin write (a[i], ' ');

end;

readln;

Екінші дәрісте берілген тізбекті Шейкер әдісімен сұрыптап көрейік

Кесте 3. Шейкерлік сұрыптауға мысалы.

L = 2	3	3	4	4
R = 8	8	7	7	4
Dir =
44	06	06	06	06
55	44	44	12	12
12	55	12	44	18
42	12	42	18	42
94	42	55	42	44
18	94	18	55	55
06	18	67	67	67
67	67	94	94	94

Шейкер сұрыптау бағдарламасының басқа түрі

Бағдарлама 6. Шейкер әдісі В

 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. 
   Шейкерлік сұрыптау қай әдістің жақсартылған версиясы болып табылады?
   
2. 
   Бұл әдістің ең үздік жағдайы болып не табылады?
   
3. 
   Неге бұл әдісті шейкерлік деп атаған?
   
4. 
   Шейкерлік әдісте сұрыптау неше бағыт бойынша өткізіледі?
   

1. 
   Тікелей қосу сұрыптауы деген не?
   
2. 
   Екілік қосу сұрыптауы деген не?
   
3. 
   Берілген әдіс «көпіршік » және таңдау әдісінен немен ерекшелінеді?
   
4. 
   Кезекті элементті дұрыс орны қай жолмен табылады?
   
5. 
   Сұрыптаудың ортақ және ең жаман жағдай қалай бағаланады?
   
6. 
   Сұрыптаудағы «Күзетші элемент» деген не?
   

5. 
   Шелл сұрыптау әдісі. ( 1 сағат)
   

Бұл әдіс Дональд Л. Шеллмен ұсынылған, орналасқан жері бойынша тұрақсыз сұрыптау болып табылады. Шелл әдісі қосулар әдісінің жақсартылған нұсқасы.

Шелл әдісінің алгоритмі екі негізгі амалдың көп рет қайталанудан тұрады:

бір ереже бойынша массивтің кейбір элементтерін біріктіру

 біріктірілген элементтер арасында әдеттегідей қосу әдісімен сұрыптау

Бірінші кезеңде жеткілікті улкен қадамды кіріс жиынның элементтері топталады. Мысалы, барлық 1000-ші элементтер, яғни топтар құрастырылады:

Топ 1: 1, 1001, 2001, 3001 және т.б.

Топ 2: 2, 1002, 2002, 3002 және т.б.

Топ 3: 3, 1003, 2003, 3003 және т.б.

. . . . . . . . . . . . . . . . . . . . .

Топ 1000: 1000, 2000, 3000 және т.б.

Әр топтың ішінде әдеттегідей қосу сұрыптауы орындалады, бұл топтағы элементтер саны аз болған жағдайда тиімді болады.

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

Соңғы кезеңде басында топтасы 1 қадаммен орындалады, бұл n өлшемді тек бір жиынды құрастырады, содан кейін – практикалық түрде сұрыпталған жиын іріктіріледі.

3 санына тең қадаммен бөлеміз, бізде 2 элементтен тұратын і топ бар, әрқайссысын жеке жеке сұрыптаймыз:

топ 1: 15 – 07 => 07 – 15 (1 салыстыру, 1 ауыстыру)

топ 2: 33 – 12 => 12 – 33 (1 салыстыру, 1 ауыстыру)

топ 3: 42 – 19 => 19 – 42 (1 салыстыру, 1 ауыстыру)

сандардың жаңа жиыны: 07 15 12 33 19 42

2 санға тең 3 элементтен бөлеміз, олар жеке сұрыпталады:

топ 1: 07 – 12 – 19 => реттелген (2 салыстыру, 0 ауыстыру)

топ 2: 15 – 33 – 42 => реттелген (2 салыстыру, 0 ауыстыру)

сандардың жаңа жиыны: 07 12 19 15 33 42

Соңғы қадамы 1 тең бөлу сандардың керекті жиынын береді; оған 5 салыстырулары бар қосу іріктеуі қолданылады және тек бір орын ауыстыру орындалады, сонымен біз нәтижеге ие боламыз.

Сонымен – 12 салыстыру және 4 ауыстыру, алдында қарастырылған әдістерден жақсырақ емес. Бірақ мұнда екі факторды ескеру керек.

1, 3, 5, 9, 17, 33, . . . (жалпы формула: t_k = (2* t_k-1) –1 )

1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767 . . . (жалпы формула: t_k = (2* t_k-1) +1, ал қарапайымы – (2^k – 1)).

Бағдарламалық түрде іске асыру (Шелл әдісі бағдарламасының негізгі бөлігі)

for m := 1 to t do {t – топтасудың қадамдарының саны, m – қадамның номірі}

begin

k := h [m]; {берілген массивте қадамның өлшемін таңдау }

temp := a [i]; j := i – k;

a [j + k] := a [j]; j := j – k;

a [j + k] := temp;

Бағдарлама 9. Шелл әдісі

 PROGRAM SHELLS;

CONST T=4;

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

VAR

A:ARRAY[-16..50] OF INTEGER;

BEGIN

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

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

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

FOR M:=1 TO T DO BEGIN

K:=H[M];

S:=-K;

X:=A[I];

IF S=0 THEN S:=-K;

INC(S);

A[S]:=X;