Практикалық сабақ №3. Шелл әдісі.

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

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

· Массивтегі ретсіздіктен қ ұ тыламыз;

· Бір-бірінен алшақ орналасқ ан элементтерді салыстырамыз;

· Салыстырып отырғ ан интервалдар бірте-бірте кемиді;

· Соң ғ ы қ адамдарды элементтер жай ғ ана орые алмастырумен шектеледі.

Кесте 3.1. Шелл ә дісімен сұ рыптау алгоритмі.

Массивтің жазбалануы келесідей болады

A: ARRAY [-h₁..n] OF INTEGER

Алгоритмнің ө зі 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;

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

BEGIN

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

READ(N);

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

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

FOR M: =1 TO T DO BEGIN

K: =H[M];

S: =-K;

FOR I: =K+1 TO N DO BEGIN

X: =A[I];

J: =I-K;

IF S=0 THEN S: =-K;

INC(S);

A[S]: =X;

WHILE X< A[J] DO BEGIN

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

J: =J-K

END;

A[J+K]: =X

END;

END;

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

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

END.

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

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

2. Бағ дарламаның листингін басып шығ ару.

3. Жұ мысты ауызша қ орғ аң ыз

Практикалық сабақ №4. Жылдам сұ рыптау.

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

Бұ л ә дісті 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< t then
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
60, 79, 82, 58, 39, 9, 54, 92, 44, 32
9, 79, 82, 58, 39, 60, 54, 92, 44, 32
9, 79, 82, 58, 39, 60, 54, 92, 44, 32
9, 32, 82, 58, 39, 60, 54, 92, 44, 79
9, 32, 44, 58, 39, 60, 54, 92, 82, 79
9, 32, 44, 58, 39, 54, 60, 92, 82, 79
9, 32, 44, 58, 39, 92, 60, 54, 82, 79
9, 32, 44, 58, 39, 54, 60, 79, 82, 92
9, 32, 44, 58, 54, 39, 60, 79, 82, 92
9, 32, 44, 58, 60, 39, 54, 79, 82, 92
9, 32, 44, 58, 54, 39, 60, 79, 82, 92
9, 32, 44, 58, 54, 39, 60, 79, 82, 92
9, 32, 44, 58, 54, 39, 60, 79, 82, 92
9, 32, 39, 58, 54, 44, 60, 79, 82, 92
9, 32, 39, 58, 54, 44, 60, 79, 82, 92
9, 32, 39, 44, 54, 58, 60, 79, 82, 92
9, 32, 39, 44, 58, 54, 60, 79, 82, 92
9, 32, 39, 44, 54, 58, 60, 79, 82, 92
9, 32, 39, 44, 54, 58, 60, 79, 92, 82
9, 32, 39, 44, 54, 58, 60, 79, 82, 92

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

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

2. Бағ дарламаның листингін басып шығ ару.

3. Жұ мысты ауызша қ орғ аң ыз