Відокремлений структурний підрозділ Золочівський коледж Національного університету «Львівська політехніка» Циклова комісія природничо-математичних та комп’ютерних дисциплін Самостійна робота з дисципліни «Теорія алгоритмів» Студент[ім’я автора приховано] Напряму підготовки 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] Висновок: Вивчили методи впорядкування, та пошуку даних масивів, вдосконалили навички програмування. ДОДАТКИ Додаток 1 / Мал.1.1 Метод мінімального елементу Додаток 2 / Мал.1.2 Метод вставок Додаток 3 / Мал.1.3 Метод обміну Додаток 4 /Мал.1.4 Метод Шелла. Додаток 5 / Мал.1.5 Швидке сортування Оцінка_______________ Підпис викладача____________