Відокремлений структурний підрозділ Золочівський коледж
Національного університету «Львівська політехніка»
Циклова комісія природничо-математичних та комп’ютерних дисциплін
Самостійна робота
з дисципліни
«Теорія алгоритмів»
Студента 2 курсу ОПС-2 групи
Напряму підготовки
6.050101 Комп’ютерні науки
Спеціальності
5.05010101 Обслуговування програмних систем та комплексів
Бомк Б.В.
Викладач Чіпак І.П.
м. Золочів – 2015 рік
Самостійна робота №1
Тема: Методи сортування.
Мета: Вивчення методів впорядкування та пошуку даних масивів, вдосконалення навичок програмування.
Короткі теоретичні відомості
Сортування вибором — простий алгоритм сортування лінійного масиву, на основі вставок.
Сортування включенням — простий алгоритм сортування на основі порівнянь.
Сортування обміном - алгоритм працює таким чином — у поданому наборі даних порівнюються два сусідні елементи.
Сортування Шелла — це алгоритм сортування, що є узагальненням сортування включенням.
Швидке сортування - полягає в переставлянні елементів масиву таким чином, щоб його можна було розділити на дві частини і кожний елемент з першої частини був не більший за будь-який елемент з другої.
Хід роботи
Завдання 1
Впорядкувати масив: 7,5,6,4,2,3.Методом мінімальних елементів.
program Minelement;
uses CRT;
var a:array[1..6] of integer;
i,j,min,k:integer;
begin
writeln('Введіть елементи масиву:');
for i:=1 to 6 do
begin
write(i,'.Елемент: ');
readln(a[i]);
end;
for i:=1 to 6 do
begin
min:=a[i];
k:=i;
j:=i+1;
while j<=6 do
begin
if min>a[j] then
begin
min:=a[j];
k:=j;
end;
j:=j+1;
end;
a[k]:=a[i];
a[i]:=min;
end;
Writeln('Масив після сортування');
for i:=1 to 6 do
write(a[i]:4);
end.
[Додаток 1]
Завдання 2
Впорядкувати масив: 7,5,6,4,2,3.Методом вставок.
program Vstavka;
uses crt;
type a=array[1..1000] of integer;
var m: a;
i, j, t, no, n: integer;
procedure InsertSort(q: a; n: integer);
begin
for i:=1 to n-1 do
begin
no:=i+1;
t:=q[no];
for j:=i+1 downto 2 do
begin
if (t<q[j-1]) then
begin
q[j]:=q[j-1];
no:=j-1;
end;
end;
q[no]:=t;
end;
write('Результат масиву: ');
for i:=1 to n do
write(q[i], ' ');
end;
begin
write(Введіть скільки елементів: ');
read(n);
for i:=1 to n do
begin
write(i,'.Елемент: ');
read(m[i]);
end;
InsertSort(m, n);
end.
[Додаток 2]
Завдання 3
Впорядкувати масив: 7,5,6,4,2,3.Методом обміну(бульбашки).
program Bulbahki;
uses CRT;
const n=6;
var z:array[1..n] of integer;
a,b,min,q:integer;
begin
writeln('Введіть елементи масиву: ');
for a:=1 to n do
begin
readln(z[a]);
end;
for a:=1 to n do
begin
min:=z[a];
q:=a;
b:=a+1;
while b<=6 do
begin
if min > z[b] then
begin
min:=z[b];
q:=b;
end;
b:=b+1;
end;
z[q]:=z[a];
z[a]:=min;
end;
writeln('Масив після сортування: ');
for a:=1 to n do
write(z[a]:4);
end.
[Додаток 3]
Завдання 4
Впорядкувати масив: 7,5,6,4,2,3.Методом Шелла.
program Shella;
uses crt;
type massiv=array[1..100] of integer;
var
i,j,n,d,c: integer;
A: massiv;
procedure Shell(A: massiv; n: integer);
begin
d:=n;
d:=d div 2;
while (d>0) do
begin
for i:=1 to n-d do
begin
j:=i;
while ((j>0) and (A[j]>A[j+d])) do
begin
c:=A[j];
A[j]:=A[j+d];
A[j+d]:=c;
j:=j-1;
end;
end;
d:=d div 2;
end;
writeln;
for i:=1 to n do write(' ', A[i]);
end;
begin
write('Розмір масиву: ');
read(n);
for i:=1 to n do
begin
write(i, ' елемент: ');
readln(A[i]);
end;
write('Результат: ');
Shell(A, n);
end.
[Додаток 4]
Завдання 5
Впорядкувати масив: 7,5,6,4,2,3.Методом швидкого сортування.
program MetodHoarra;
uses CRT;
const n=6;
var
i:integer;
a:array[1..n] of integer;
procedure qsort (l,r:integer);
var
i,j,b,k,m,c:integer;
begin
i:=b;
j:=r;
m:=a[(l+r) div 2];
while a[i]<m do i:=i+r;
while a[j] >m do j:=J-1;
if i<j then
begin
c:=a[i];
a[i]:=a[j];
a[j]:=c;
i:=i+l;
j:=j-l;
end;
until i>j;
if l<j then qsort(l,j);
if i<j then qsort(i,j);
end;
begin
for i:1 to n do
begin
writeln('Введіть елементи масиву: ');
read (a[i]);
end;
readln;
qsort(l,n);
writeln('Впорядкований масив: ');
for i:=1 to n do
writeln(a[i]);
end. [Додаток 5]
Висновок: Вивчили методи впорядкування, та пошуку дани...
