Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ «КПІ»
ФАКУЛЬТЕТ ПРИКЛАДНОЇ МАТЕМАТИКИ
Кафедра спеціалізованих комп’ютерних систем
КУРСОВА РОБОТА
з дисципліни "Структури даних і алгоритми"
Виконав: Гудь Володимир
Група: КB-01
Номер залікової книжки: КВ-0104
Допущений до захисту
__________________
2 семестр 2010/2011
НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ
«КПІ»
ФАКУЛЬТЕТ ПРИКЛАДНОЇ МАТЕМАТИКИ
Узгоджено ЗАХИЩЕНА "__"_________2011р.
Керівник роботи з оцінкою_________________
_______/Марченко О.І./ ________ /Марченко О.І./
Дослідження ефективності методу сортування "вибір №4 – обмін" на багатовимірних масивах
Виконавець роботи:
Гудь Володимир Віталійович
______________2011р.
ТЕХНІЧНЕ ЗАВДАННЯ
на курсову роботу з дисципліни
“Структури даних і алгоритми”
I. Описати принцип та схему роботи кожного із досліджуваних методів сортування або пошуку для одновимірного масиву.
II. Скласти алгоритми сортування або пошуку в багатовимірному масиві заданими методами, згідно до варіанту, та написати відповідну програму на мові програмування.
Програма повинна задовольняти наступним вимогам:
III. Виконати налагодження та тестування коректності роботи написаної програми.
IV. Провести практичні дослідження швидкодії складених алгоритмів.
V. За результатами досліджень скласти порівняльні таблиці за різними ознаками.
VI. Виконати порівняльний аналіз поведінки заданих алгоритмів за отриманими результатами:
VII. Зробити висновки за виконаним порівняльним аналізом.
Варіант № 4
Задача
№2 Впорядкувати окремо кожен переріз тривимірного масиву А [p,m,n] наскрізно по стовпчиках за незменшенням.
Досліджувані методи та алгоритми
№21 Гібридний алгоритм "вибір №4 – обмін".
Способи обходу
№1. Переписати елементи заданого двовимірного масиву у додатковий одновимірний масив. Виконати сортування. Повернути результат у початковий масив.
№2. Не використовуючи додаткового масиву, виконати сортування перетворюючи один індекс елементів "уявного" вектора у відповідні індекси елементів заданого двовимірного масиву.
№3. Виконати сортування, здійснюючи обхід безпосередньо по елементах заданого двовимірного масиву, не використовуючи додаткових масивів і перетворень індексів.
Теоретичні положення
Гібридний алгоритм сортування "вибір №4 – обмін".
Принцип: в кожен момент часу масив вважається поділеним на 3 частини: відсортовану зліва, відсортовану справа та ще не відсортовану. Перед початком сортування не відсортована частина – весь масив, а відсортованої ще немає.
Алгоритм:
Схема:
|
6 |
9 |
7 |
4 |
4 |
3 |
7 |
|
7 |
9 |
|||||
|
6 |
7 |
7 |
4 |
4 |
3 |
9 |
|
4 |
6 |
|||||
|
4 |
7 |
7 |
6 |
4 |
3 |
9 |
|
3 |
4 |
|||||
|
3 |
7 |
7 |
6 |
4 |
4 |
9 |
|
|
4 |
|
7 |
|||
|
3 |
4 |
7 |
6 |
4 |
7 |
9 |
|
4 |
|
7 |
||||
|
3 |
4 |
7 |
6 |
4 |
7 |
9 |
(сірим позначені ліва та права відсортовані частини)
Оцінка швидкодії алгоритму: о( n∙ln(n) )
Реалізація алгоритму на мові Turbo Pascal:
program SelectExchange4;
uses Crt;
const n=10;
type
TVector=array[1..n] of integer;
var
A : TVector;
Min, Max : integer;
L, R, i : word;
Begin
ClrScr;
for i:=1 to n do read(A[i]);
readln;
L:=1; R:=n;
while L<R do
begin
for i:=L to R do
if A[i] < A[L] then
begin
Min:=A[i];
A[i]:=A[L];
A[L]:=Min;
end
else
if A[i] > A[R] then
begin
Max:=A[i];
A[i]:=A[R];
A[R]:=Max;
end;
L:=L+1; R:=R-1;
end;
for i:=1 to n do write(A[i]:8);
writeln;
End.
Структурна схема взаємозв’язків модулів та структурна схема взаємовикликів процедур та функцій.
1. Взаємозв’язки модулів
1. Взаємовиклики процедур та функцій
Опис призначення модулів, процедур і функцій.
1. Модуль “Globals”
Містить у собі константи розмірів масивів (P перерізів, M рядків, N стовпчиків); основні типи даних для 3-вимірного масиву (TArray3D) та вектору (TVector), опис типу для виміру часу (TTime); глобальну змінну для вектора (A), 3-вимірного масиву (B), часу початку роботи алгоритму (StartTime), часу закінчення роботи алгоритму (FinishTime).
2. Модуль “Tools”
Містить у собі процедури заповнення векторів усіх конфігурацій, виводу вектора та 3-вимірного масиву на екран, переписування вектора в 3-вимірний масив; функцію обрахунку часу роботи програми.
а. Функція “ResTime”- обчислення часу роботи алгоритму відніманням від часу кінця роботи алгоритму часу початку роботи. Результат в сотих долях секунди.
б. Процедура “GenerateRandomVector”- створення не відсортованого вектору.
в. Процедура “GenerateSortedVector”- створення відсортованого вектору.
г. Процедура “GenerateInvsortedVector”- створення обернено відсортованого вектору.
д. Процедура “Vector2Array3D”- переписування вектору в 3-вимірний масив по стовпчиках.
ж. Процедура “OutVector”- Виведення вектора на екран.
з. Процедура “OutArray3D”- Виведення 3-вимірного масиву на екран окремо по кожному перерізу.
3. Модуль “Sort”
Містить у собі процедуру cортування вектора та 3 процедури сортування 3-вимірного масиву з різними обходами.
а. Процедура “SortVector”- сортування одновимірного масиву (вектора) гібридним алгоритмом “вибір №4 – обмін”, з виміром часу.
б. Процедура “SortArray3D_1”- сортування 3-вимірного масиву гібридним алгоритмом “вибір №4 – обмін” (обхід з переписуванням перерізу у додатковий одновимірний масив), з виміром часу.
в. Процедура “SortArray3D_2”- сортування 3-вимірного масиву гібридним алгоритмом “вибір №4 – обмін” (обхід по уявному вектору з перетворенням індексів), з виміром часу.
г. Процедура “SortArray3D_3”- сортування 3-вимірного масиву гібридним алгоритмом “вибір №4 – обмін” (з безпосереднім обходом по елементах), з виміром часу.
4. Модуль “Menu”
Містить у собі процедури виведення меню на екран; процедури з викликами підготовки масивів, сортування, виведення на екран масивів та результатів; процедуру побудови таблиці результатів для 3-вимірних масивів.
а. Процедура “BuildMenu”- вивід на екран головного меню з варіантами дій.
б. Процедура “ChoiseVector”- підготовка, вивід, сортування векторів усіх конфігурацій.
г. Процедура “ChoiseArray3D_1”- підготовка, вивід, сортування (обхід 1) 3-вимірних масивів усіх конфігурацій, вивід результатів.
д. Процедура “ChoiseArray3D_2”- підготовка, вивід, сортування (обхід 2) 3-вимірних масивів усіх конфігурацій, вивід результатів.
ж. Процедура “ChoiseArray3D_3”- підготовка, вивід, сортування (обхід 3) 3-вимірних масивів усіх конфігурацій, вивід результатів.
з. Процедура “ChoiseArray3D_All”- підготовка, вивід, сортування усіма обходами 3-вимірних масивів усіх конфігурацій; побудова результуючої таблиці для всіх типів векторів та усіх обходів.
5. Програма “Main”
Містить у собі виклик процедури побудови головного меню (BuildMenu).
Текст програми з коментарями
1. main.pas
program main;
uses menu;
begin
{Алгоритм 21. Гібридний "Вибір №4 - Обмін". Обходи 1,2,3}
BuildMenu; {Викликаємо процедуру побудови меню}
end.
2. globals.pas
unit globals; {Модуль для глобальних змінних}
interface
const {Константи розмірів масиву}
p = 2; {p перерізів}
m = 4; {m рядків}
n = 5; {n стовпчиків}
type TVector = array [1..m*n*p] of integer; {Тип для вектора}
TArray3D = array [1..p,1..m,1..n] of integer; {Тип для 3-вимірного масиву}
TTime = record {Тип для зберігання часу}
Hours, {години}
Minutes, {хвилини}
Seconds, {секунди}
HSeconds: Word {соті долі секунди}
end;
var A : TVector; {Глобальна змінна для вектора}
B : TArray3D; {Глобальна змінна для 3-вимірного масиву}
StartTime,FinishTime : TTime; {Глобальні змінні для зберігання часу початку та закінчення роботи алгоритму}
implementation
begin
{...}
end.
3. tools.pas
unit tools; {Модуль з функцією обрахування часу роботи та процедурами роботи з масивами}
interface
uses globals;
function ResTime(const STime {час початку роботи}, FTime {час кінця роботи}: TTime):longint; {Обрахування часу роботи алгоритму}
procedure GenerateRandomVector(var A:TVector {вектор для заповнення}); {Заповнення вектора невпорядкованими числами}
procedure GenerateSortedVector(var A:TVector {вектор для заповнення}); {Заповнення вектора впорядкованими числами}
procedure GenerateInvsortedVector(var A:TVector {вектор для заповнення}); {Заповнення вектора обернено впорядкованими числами}
procedure Vector2Array3D(const A:TVector; {вектор з елементами} var B:TArray3D {масив для заповнення}); {Заповнення 3-вимірного масиву елементами з вектора}
procedure OutVector(const A:TVector {вектор для виводу}); {Вивід вектора на екран}
procedure OutArray3D(const A:TArray3D {масив для виводу}); {Вивід перерізів 3-вимірного масиву на екран}
implementation
uses crt;
function ResTime(const STime, FTime: TTime):longint;
begin
ResTime := {Визначаємо різницю між часом закінчення і часом старту алгоритму}
36000*(FTime.Hours - STime.Hours )+ {години}
6000*(FTime.Minutes - STime.Minutes)+ {хвилини}
100*(FTime.Seconds - STime.Seconds)+ {секунди}
(FTime.HSeconds - STime.HSeconds) {соті долі секунди}
end;
procedure GenerateRandomVector(var A:TVector);
var i : integer; {лічильник}
begin {присвоюємо кожному елементу вектора випадкове значення}
for i:=1 to m*n*p do A[i]:=random(999);
end;
procedure GenerateSortedVector(var A:TVector);
var u,d,i : integer; {верхня межа випадкового числа, нижня межа випадкового числа, лічильник}
begin
A[1]:=random(99); {присвоюємо першому елементу вектора значення}
for i:=2 to m*n*p do
begin
u:=A[i-1]+15; {збільшуємо верхню межу випадкового числа}
d:=A[i-1]+1; {збільшуємо нижню межу випадкового числа}
A[i]:=trunc((u-d)*random+d); {присвоюємо елементу випадкове значення в межах від "d" до "u"}
end;
end;
procedure GenerateInvsortedVector(var A:TVector);
var u,d,i : integer; {верхня межа випадкового числа, нижня межа випадкового числа, лічильник}
begin
A[m*n*p]:=random(100); {присвоюємо останньому елементу вектора значення}
for i:=m*n*p-1 downto 1 do
begin
u:=A[i+1]+15; {збільшуємо верхню межу випадкового числа}
d:=A[i+1]+1; {збільшуємо нижню межу випадкового числа}
A[i]:=trunc((u-d)*random+d); {присвоюємо елементу випадкове значення в межах від "d" до "u"}
end;
end;
procedure Vector2Array3D(const A:TVector; var B:TArray3D);
var i, j, k, t : integer; {лічильники для масиву і лічильник для вектора}
begin
t:=1; {задаємо початкове значення лічильника вектора}
{по стовпчиках переписуємо значення вектора в 3-вимірний масив}
for k:=1 to p do
for j:=1 to n do
for i:=1 to m do
begin
B[k,i,j]:=A[t]; {присвоюємо відповідному елементу масиву відповідне значення з вектора}
t:=t+1; {збільшуємо лічильник для вектора на 1}
end;
end;
procedure OutVector(const A:TVector);
var i : integer; {лічильник для вектора}
begin
for i:=1 to m*n*p do write(A[i],' '); {поелементний вивід вектора}
writeln;
writeln;
end;
procedure OutArray3D(const A:TArray3D);
var i, j, k : integer; {лічильники для масиву}
begin
for k:=1 to p do {окремо виводимо кожен переріз масиву}
begin
for i:=1 to m do
begin
for j:=1 to n do write(A[k,i,j]:3,' '); {поелементний вивід масиву}
writeln;
end;
writeln;
end;
end;
begin
randomize;
end.
4. sort.pas
unit sort; {Модуль з алгоритмами сортування}
interface
uses globals;
procedure SortVector(var A:TVector; {вектор} var WTime:longint {час роботи}); {Сортування вектора}
procedure SortArray3D_1(var A:TArray3D; {масив} var WTime:longint {час роботи}); {Сортування 3-вимірного масиву (Обхід 1)}
procedure SortArray3D_2(var A:TArray3D; {масив} var WTime:longint {час роботи}); {Сортування 3-вимірного масиву (Обхід 2)}
procedure SortArray3D_3(var A:TArray3D; {масив} var WTime:longint {час роботи}); {Сортування 3-вимірного масиву (Обхід 3)}
implementation
uses crt, dos, tools;
procedure SortVector(var A:TVector; var WTime:longint);
var Min, Max, {тимчасові змінні для перестановки місцями}
L, R, {межі сортування}
i {лічильник} : integer;
Begin
with StartTime do GetTime(Hours,Minutes,Seconds,HSeconds); {робимо замір часу початку роботи}
L:=1; R:=m*n*p; {Задаємо невідсортовану частину (початкові межі сортування)}
while L < R do {повторюємо доки крайні межі не перетнуться = доки невідсортована частина не буде порожньою}
begin
for i:=L to R do {перебираємо кожен з елементів невідсортованої частини}
if A[i] < A[L] then {порівнюємо вибраний елемент з лівою межею}
begin {якщо вибраний елемент менший за крайній лівий, то міняємо їх місцями}
Min:=A[i];
A[i]:=A[L];
A[L]:=Min;
end
else {якщо вибраний елемент не менший, то порівнюємо його з правою межею}
if A[i] > A[R] then
begin {якщо вибраний елемент більший за крайній правий, то міняємо їх місцями}
Max:=A[i];
A[i]:=A[R];
A[R]:=Max;
end;
L:=L+1; R:=R-1; {збільшуємо ліву межу на 1 елемент, а праву зменшуємо на 1}
end;
with FinishTime do GetTime(Hours,Minutes,Seconds,HSeconds); {робимо замір часу кінця роботи}
WTime := ResTime(StartTime, FinishTime); {функцією ResTime рахуємо час роботи}
End;
procedure SortArray3D_1(var A:TArray3D; var WTime:longint);
var Min, Max, {тимчасові змінні для перестановки місцями}
t, i, j, k, {лічильник для вектора та 3 лічильника для 3-вимірного масиву}
L, R {межі сортування} : integer;
B : array [1..m*n] of integer; {вектор для переписування перерізу}
Begin
with StartTime do GetTime(Hours,Minutes,Seconds,HSeconds); {робимо замір часу початку роботи}
for k:=1 to p do {повторюємо дії окремо для кожного перерізу}
begin
t:=1; {задаємо початкове значення лічильника вектора}
for j:=1 to n do
begin
for i:=1 to m do
begin
B[t]:=A[k,i,j]; {присвоюємо відповідному елементу вектора відповідне значення з масиву}
t:=t+1; {збільшуємо лічильник для вектора на 1}
end;
end;
L:=1; R:=m*n; {Задаємо невідсортовану частину (початкові межі сортування)}
while L < R do {повторюємо доки крайні межі не перетнуться = доки невідсортована частина не буде порожньою}
begin
for i:=L to R do {перебираємо кожен з елементів невідсортованої частини}
if B[i] < B[L] then {порівнюємо вибраний елемент з лівою межею}
begin {якщо вибраний елемент менший за крайній лівий, то міняємо їх місцями}
Min:=B[i];
B[i]:=B[L];
B[L]:=Min;
end
else {якщо вибраний елемент не менший, то порівнюємо його з правою межею}
if B[i] > B[R] then
begin {якщо вибраний елемент більший за крайній правий, то міняємо їх місцями}
Max:=B[i];
B[i]:=B[R];
B[R]:=Max;
end;
L:=L+1; R:=R-1; {збільшуємо ліву межу на 1 елемент, а праву зменшуємо на 1}
end;
t:=1; {задаємо початкове значення лічильника вектора}
for j:=1 to n do
begin
for i:=1 to m do
begin
A[k,i,j]:=B[t]; {присвоюємо відповідному елементу матриці відповідне значення з вектора}
t:=t+1; {збільшуємо лічильник для вектора на 1}
end;
end;
end;
with FinishTime do GetTime(Hours,Minutes,Seconds,HSeconds); {робимо замір часу кінця роботи}
WTime := ResTime(StartTime, FinishTime); {функцією ResTime рахуємо час роботи}
End;
procedure SortArray3D_2(var A:TArray3D; var WTime:longint);
var Min, Max, {тимчасові змінні для перестановки місцями}
i, {лічильник для уявного вектору}
k, {лічильник для перерізів}
L, R {межі сортування} : integer;
Begin
with StartTime do GetTime(Hours,Minutes,Seconds,HSeconds); {робимо замір часу початку роботи}
for k:=1 to p do {повторюємо дії окремо для кожного перерізу}
begin
L:=1; R:=m*n; {Задаємо невідсортовану частину (початкові межі сортування)}
while L < R do {повторюємо доки крайні межі не перетнуться = доки невідсортована частина не буде порожньою}
begin
for i:=L to R do {перебираємо кожен з елементів невідсортованої частини}
if A[k,(i-1) mod m + 1,(i-1) div m + 1] < A[k,(L-1) mod m + 1,(L-1) div m + 1] then {порівнюємо вибраний елемент з лівою межею}
begin {якщо вибраний елемент менший за крайній лівий, то міняємо їх місцями}
Min:=A[k,(i-1) mod m + 1,(i-1) div m + 1];
A[k,(i-1) mod m + 1,(i-1) div m + 1]:=A[k,(L-1) mod m + 1,(L-1) div m + 1];
A[k,(L-1) mod m + 1,(L-1) div m + 1]:=Min;
end
else {якщо вибраний елемент не менший, то порівнюємо його з правою межею}
if A[k,(i-1) mod m + 1,(i-1) div m + 1] > A[k,(R-1) mod m + 1,(R-1) div m + 1] then
begin {якщо вибраний елемент більший за крайній правий, то міняємо їх місцями}
Max:=A[k,(i-1) mod m + 1,(i-1) div m + 1];
A[k,(i-1) mod m + 1,(i-1) div m + 1]:=A[k,(R-1) mod m + 1,(R-1) div m + 1];
A[k,(R-1) mod m + 1,(R-1) div m + 1]:=Max;
end;
L:=L+1; R:=R-1; {збільшуємо ліву межу на 1 елемент, а праву зменшуємо на 1}
end;
end;
with FinishTime do GetTime(Hours,Minutes,Seconds,HSeconds); {робимо замір часу кінця роботи}
WTime := ResTime(StartTime, FinishTime); {функцією ResTime рахуємо час роботи}
End;
procedure SortArray3D_3(var A:TArray3D; var WTime:longint);
var Min, Max, {тимчасові змінні для перестановки місцями}
i, j, k, {лічильники для 3-вимірного масиву}
Li, Lj, {рядок та стовпчик лівої межі сортування}
Ri, Rj {рядок та стовпчик правої межі сортування}: integer;
Begin
with StartTime do GetTime(Hours,Minutes,Seconds,HSeconds);{робимо замір часу початку роботи}
for k:=1 to p do {повторюємо дії окремо для кожного перерізу}
begin
Li:=1; Lj:=1; {Задаємо початкові рядок та стовпчик лівої межі невідсортованої частини}
Ri:=m; Rj:=n; {Задаємо початкові рядок та стовпчик правої межі невідсортованої частини}
while (Lj<Rj) or ((Lj=Rj) and (Li<Ri)) do {повторюємо доки крайні межі сортування не перетнуться}
begin
i:=Li; j:=Lj; {задаємо перше значення лічильника}
while (j<Rj) or ((j=Rj) and (i<Ri)) do {перебираємо кожен з елементів невідсортованої частини}
begin
if A[k,i,j] < A[k,Li,Lj] then {порівнюємо вибраний елемент з лівою межею}
begin {якщо вибраний елемент менший за крайній лівий, то міняємо їх місцями}
Min:=A[k,i,j];
A[k,i,j]:=A[k,Li,Lj];
A[k,Li,Lj]:=Min;
end
else {якщо вибраний елемент не менший, то порівнюємо його з правою межею}
if A[k,i,j] > A[k,Ri,Rj] then
begin {якщо вибраний елемент більший за крайній правий, то міняємо їх місцями}
Max:=A[k,i,j];
A[k,i,j]:=A[k,Ri,Rj];
A[k,Ri,Rj]:=Max;
end;
{беремо наступний елемент}
if i<m then i:=i+1
else begin j:=j+1; i:=1; end;
end;
{збільшуємо ліву межу на 1 елемент, а праву зменшуємо на 1}
if Li<m then Li:=Li+1
else begin Lj:=Lj+1; Li:=1; end;
if Ri>1 then Ri:=Ri-1
else begin Rj:=Rj-1; Ri:=m; end;
end;
end;
with FinishTime do GetTime(Hours,Minutes,Seconds,HSeconds); {робимо замір часу кінця роботи}
WTime := ResTime(StartTime, FinishTime); {функцією ResTime рахуємо час роботи}
End;
BEGIN
{...}
END.
5. menu.pas
unit menu; {Модуль побудови меню}
interface
procedure BuildMenu; {процедура виводу на екран стартового меню}
implementation
uses crt, globals, tools, sort;
var butt : char; {Змінна для зчитування натиснутої клавіші}
procedure ChoiseVector; {процедура з сортуванням векторів}
var RandomTime, SortedTime, InvsortedTime : longint; {Час роботи алгоритму для різних конфігурацій векторів}
begin
repeat
begin
clrscr;
writeln('-> 1. Sort Vector A[M*N*P], where M*N*P = ',m*n*p,';');
write('Press Enter to Start');
readln;
{генеруємо невпорядкований вектор, виводимо його на екран, сортуємо його, виводимо відсортований вектор та час роботи}
GenerateRandomVector(A);
writeln(' -> Random');
OutVector(A);
SortVector(A,RandomTime);
OutVector(A);
writeln('Sort Time for Random Vector = ',RandomTime,' Hs');
writeln;
write('Press Enter to continue');
readln;
{генеруємо впорядкований вектор, виводимо його на екран, сортуємо його, виводимо відсортований вектор та час роботи}
GenerateSortedVector(A);
writeln(' -> Sorted');
OutVector(A);
SortVector(A,SortedTime);
OutVector(A);
writeln('Sort Time for Sorted Vector = ',SortedTime,' Hs');
writeln;
write('Press Enter to continue');
readln;
{генеруємо обернено впорядкований вектор, виводимо його на екран, сортуємо його, виводимо відсортований вектор та час роботи}
GenerateInvsortedVector(A);
writeln(' -> Inverse Sorted');
OutVector(A);
SortVector(A,InvsortedTime);
OutVector(A);
writeln('Sort Time for Inverse Sorted Vector = ',InvsortedTime,' Hs');
writeln;
write('Press "r" to restart, or any other key to back to menu');
butt:=readkey;
end;
until butt <> 'r';
clrscr;
BuildMenu;
end;
procedure ChoiseArray3D_1; {процедура з сортуванням масивів обходом 1}
var RandomTime, SortedTime, InvsortedTime : longint; {Час роботи алгоритму для різних конфігурацій масивів}
begin
repeat
begin
clrscr;
writeln('-> 2. 3D Array [',p,',',m,',',n,'] Sort ("Rewrite to Vector")');
write('Press Enter to Start');
readln;
{генеруємо невпорядкований вектор, записуємо його в масив, виводимо масив на екран, сортуємо масив (обхід 1), виводимо відсортований масив та час роботи}
GenerateRandomVector(A);
Vector2Array3D(A,B);
writeln(' -> Random');
OutArray3D(B);
SortArray3D_1(B,RandomTime);
OutArray3D(B);
writeln('"Rewrite to Vector" Sort Time for Random 3D Array = ',RandomTime,' Hs');
writeln;
write('Press Enter to continue');
readln;
{генеруємо впорядкований вектор, записуємо його в масив, виводимо масив на екран, сортуємо масив (обхід 1), виводимо відсортований масив та час роботи}
GenerateSortedVector(A);
Vector2Array3D(A,B);
writeln(' -> Sorted');
OutArray3D(B);
SortArray3D_1(B,SortedTime);
OutArray3D(B);
writeln('"Rewrite to Vector" Sort Time for Sorted 3D Array = ',SortedTime,' Hs');
writeln;
write('Press Enter to continue');
readln;
{генеруємо обернено впорядкований вектор, записуємо його в масив, виводимо масив на екран, сортуємо масив (обхід 1), виводимо відсортований масив та час роботи}
GenerateInvsortedVector(A);
Vector2Array3D(A,B);
writeln(' -> Inverse Sorted');
OutArray3D(B);
SortArray3D_1(B,InvsortedTime);
OutArray3D(B);
writeln('"Rewrite to Vector" Sort Time for Inverse Sorted 3D Array = ',InvsortedTime,' Hs');
writeln;
write('Press "r" to restart, or any other key to back to menu');
butt:=readkey;
end;
until butt <> 'r';
clrscr;
BuildMenu;
end;
procedure ChoiseArray3D_2; {процедура з сортуванням масивів обходом 2}
var RandomTime, SortedTime, InvsortedTime : longint; {Час роботи алгоритму для різних конфігурацій масивів}
begin
repeat
begin
clrscr;
writeln('-> 3. 3D Array [',p,',',m,',',n,'] Sort ("Imaginary Vector")');
write('Press Enter to Start');
readln;
{генеруємо невпорядкований вектор, записуємо його в масив, виводимо масив на екран, сортуємо масив (обхід 2), виводимо відсортований масив та час роботи}
GenerateRandomVector(A);
Vector2Array3D(A,B);
writeln(' -> Random');
OutArray3D(B);
SortArray3D_2(B,RandomTime);
OutArray3D(B);
writeln('"Imaginary Vector" Sort Time for Random 3D Array = ',RandomTime,' Hs');
writeln;
write('Press Enter to continue');
readln;
{генеруємо впорядкований вектор, записуємо його в масив, виводимо масив на екран, сортуємо масив (обхід 2), виводимо відсортований масив та час роботи}
GenerateSortedVector(A);
Vector2Array3D(A,B);
writeln(' -> Sorted');
OutArray3D(B);
SortArray3D_2(B,SortedTime);
OutArray3D(B);
writeln('"Imaginary Vector" Sort Time for Sorted 3D Array = ',SortedTime,' Hs');
writeln;
write('Press Enter to continue');
readln;
{генеруємо обернено впорядкований вектор, записуємо його в масив, виводимо масив на екран, сортуємо масив (обхід 2), виводимо відсортований масив та час роботи}
GenerateInvsortedVector(A);
Vector2Array3D(A,B);
writeln(' -> Inverse Sorted');
OutArray3D(B);
SortArray3D_2(B,InvsortedTime);
OutArray3D(B);
writeln('"Imaginary Vector" Sort Time for Inverse Sorted 3D Array = ',InvsortedTime,' Hs');
writeln;
write('Press "r" to restart, or any other key to back to menu');
butt:=readkey;
end;
until butt <> 'r';
clrscr;
BuildMenu;
end;
procedure ChoiseArray3D_3; {процедура з сортуванням масивів обходом 3}
var RandomTime, SortedTime, InvsortedTime : longint; {Час роботи алгоритму для різних конфігурацій масивів}
begin
repeat
begin
clrscr;
writeln('-> 4. 3D Array [',p,',',m,',',n,'] Sort ("Direct Acess")');
write('Press Enter to Start');
readln;
{генеруємо невпорядкований вектор, записуємо його в масив, виводимо масив на екран, сортуємо масив (обхід 3), виводимо відсортований масив та час роботи}
GenerateRandomVector(A);
Vector2Array3D(A,B);
writeln(' -> Random');
OutArray3D(B);
SortArray3D_3(B,RandomTime);
OutArray3D(B);
writeln('"Direct Acess" Sort Time for Random 3D Array = ',RandomTime,' Hs');
writeln;
write('Press Enter to continue');
readln;
{генеруємо впорядкований вектор, записуємо його в масив, виводимо масив на екран, сортуємо масив (обхід 3), виводимо відсортований масив та час роботи}
GenerateSortedVector(A);
Vector2Array3D(A,B);
writeln(' -> Sorted');
OutArray3D(B);
SortArray3D_3(B,SortedTime);
OutArray3D(B);
writeln('"Direct Acess" Sort Time for Sorted 3D Array = ',SortedTime,' Hs');
writeln;
write('Press Enter to continue');
readln;
{генеруємо обернено впорядкований вектор, записуємо його в масив, виводимо масив на екран, сортуємо масив (обхід 3), виводимо відсортований масив та час роботи}
GenerateInvsortedVector(A);
Vector2Array3D(A,B);
writeln(' -> Inverse Sorted');
OutArray3D(B);
SortArray3D_3(B,InvsortedTime);
OutArray3D(B);
writeln('"Direct Acess" Sort Time for Inverse Sorted 3D Array = ',InvsortedTime,' Hs');
writeln;
write('Press "r" to restart, or any other key to back to menu');
butt:=readkey;
end;
until butt <> 'r';
clrscr;
BuildMenu;
end;
procedure ChoiseArray3D_All; {процедура з пакетним сортуванням масивів}
var RandomTime1, SortedTime1, InvsortedTime1, {Час роботи алгоритму з обходом 1 для різних конфігурацій масивів}
RandomTime2, SortedTime2, InvsortedTime2, {Час роботи алгоритму з обходом 2 для різних конфігурацій масивів}
RandomTime3, SortedTime3, InvsortedTime3 : {Час роботи алгоритму з обходом 3 для різних конфігурацій масивів} longint;
i {лічильник для побудови таблиці} : word;
begin
repeat
begin
clrscr;
writeln('-> 5. Start All');
writeln;
{генеруємо впорядкований вектор}
GenerateSortedVector(A);
{записуємо згенрований вектор в масив, сортуємо масив (обхід 1), записуємо час роботи}
Vector2Array3D(A,B);
SortArray3D_1(B,SortedTime1);
{записуємо згенрований вектор в масив, сортуємо масив (обхід 2), записуємо час роботи}
Vector2Array3D(A,B);
SortArray3D_2(B,SortedTime2);
{записуємо згенрований вектор в масив, сортуємо масив (обхід 3), записуємо час роботи}
Vector2Array3D(A,B);
SortArray3D_3(B,SortedTime3);
{генеруємо невпорядкований вектор}
GenerateRandomVector(A);
{записуємо згенрований вектор в масив, сортуємо масив (обхід 1), записуємо час роботи}
Vector2Array3D(A,B);
SortArray3D_1(B,RandomTime1);
{записуємо згенрований вектор в масив, сортуємо масив (обхід 2), записуємо час роботи}
Vector2Array3D(A,B);
SortArray3D_2(B,RandomTime2);
{записуємо згенрований вектор в масив, сортуємо масив (обхід 3), записуємо час роботи}
Vector2Array3D(A,B);
SortArray3D_3(B,RandomTime3);
{генеруємо обернено впорядкований вектор}
GenerateInvsortedVector(A);
{записуємо згенрований вектор в масив, сортуємо масив (обхід 1), записуємо час роботи}
Vector2Array3D(A,B);
SortArray3D_1(B,InvsortedTime1);
{записуємо згенрований вектор в масив, сортуємо масив (обхід 2), записуємо час роботи}
Vector2Array3D(A,B);
SortArray3D_2(B,InvsortedTime2);
{записуємо згенрований вектор в масив, сортуємо масив (обхід 3), записуємо час роботи}
Vector2Array3D(A,B);
SortArray3D_3(B,InvsortedTime3);
{будуємо зведену таблицю результатів сортування масивів}
writeln(' Table for 3D Array A[P,M,N], where P = ',p,'; M = ',m,'; N = ',n,';');
write(' ',#201);
for i:=1 to 21 do write(#205);
write(#203);
for i:=1 to 10 do write(#205);
write(#203);
for i:=1 to 10 do write(#205);
write(#203);
for i:=1 to 16 do write(#205);
write(#187);
writeln;
write(' ',#186);
write(' ':21);
write(#186,' ');
write('Sorted');
write(' ',#186,' ');
write('Random');
write(' ',#186,' ');
write('Inverse Sorted');
write(' ',#186);
writeln;
write(' ',#204);
for i:=1 to 21 do write(#205);
write(#206);
for i:=1 to 10 do write(#205);
write(#206);
for i:=1 to 10 do write(#205);
write(#206);
for i:=1 to 16 do write(#205);
write(#185);
writeln;
write(' ',#186,' ');
write('Rewrite to Vector ');
write(' ',#186,' ');
write(SortedTime1:6);
write(' ',#186,' ');
write(RandomTime1:6);
write(' ',#186,' ');
write(InvsortedTime1:12);
write(' ',#186);
writeln;
write(' ',#204);
for i:=1 to 21 do write(#205);
write(#206);
for i:=1 to 10 do write(#205);
write(#206);
for i:=1 to 10 do write(#205);
write(#206);
for i:=1 to 16 do write(#205);
write(#185);
writeln;
write(' ',#186,' ');
write('Imaginary Vector ');
write(' ',#186,' ');
write(SortedTime2:6);
write(' ',#186,' ');
write(RandomTime2:6);
write(' ',#186,' ');
write(InvsortedTime2:12);
write(' ',#186);
writeln;
write(' ',#204);
for i:=1 to 21 do write(#205);
write(#206);
for i:=1 to 10 do write(#205);
write(#206);
for i:=1 to 10 do write(#205);
write(#206);
for i:=1 to 16 do write(#205);
write(#185);
writeln;
write(' ',#186,' ');
write('Direct Acess',' ':6);
write(' ',#186,' ');
write(SortedTime3:6);
write(' ',#186,' ');
write(RandomTime3:6);
write(' ',#186,' ');
write(InvsortedTime3:12);
write(' ',#186);
writeln;
write(' ',#200);
for i:=1 to 21 do write(#205);
write(#202);
for i:=1 to 10 do write(#205);
write(#202);
for i:=1 to 10 do write(#205);
write(#202);
for i:=1 to 16 do write(#205);
write(#188);
writeln;
writeln;
write('Press "r" to rebuild table, or any other key to back to menu');
butt:=readkey;
end;
until butt <> 'r';
clrscr;
BuildMenu;
end;
procedure BuildMenu; {процедура виводу на екран стартового меню}
begin
clrscr;
repeat
begin
{виводимо список можливих дій}
writeln(' Type number of task :');
writeln;
writeln(' 1. Vector Sort');
writeln(' 2. 3D Array Sort 1 ("Rewrite to Vector")');
writeln(' 3. 3D Array Sort 2 ("Imaginary Vector")');
writeln(' 4. 3D Array Sort 3 ("Direct Acess")');
writeln(' 5. Start All');
writeln;
write(' Press "q" to quit');
{в залежності від натиснутої клавіші запускаємо відповідну процедуру з сортуваннями або завершуємо роботу}
butt:=readkey;
case butt of
'1' : ChoiseVector;
'2' : ChoiseArray3D_1;
'3' : ChoiseArray3D_2;
'4' : ChoiseArray3D_3;
'5' : ChoiseArray3D_All;
end;
clrscr;
end;
until butt = 'q';
end;
begin
{ ... }
end.
Тести
1. Правильність роботи алгоритму для вектора
А. Створення невідсортованого вектору, сортування його гібридним алгоритмом вибір №4 – обмін, вимір часу сортування.
Б. Створення відсортованого вектору, сортування його гібридним алгоритмом вибір №4 – обмін, вимір часу сортування.
В. Створення обернено відсортованого вектору, сортування його гібридним алгоритмом вибір №4 – обмін, вимір часу сортування.
2. Правильність роботи алгоритму для 3-вимірного масиву
А. Створення невідсортованого 3-вимірного масиву, сортування його гібридним алгоритмом вибір №4 – обмін з обходом №1, вимір часу сортування.
Б. Створення відсортованого 3-вимірного масиву, сортування його гібридним алгоритмом вибір №4 – обмін з обходом №1, вимір часу сортування.
В. Створення обернено відсортованого 3-вимірного масиву, сортування його гібридним алгоритмом вибір №4 – обмін з обходом №1, вимір часу сортування.
Д. Створення невідсортованого 3-вимірного масиву, сортування його гібридним алгоритмом вибір №4 – обмін з обходом №2, вимір часу сортування.
Ж. Створення відсортованого 3-вимірного масиву, сортування його гібридним алгоритмом вибір №4 – обмін з обходом №2, вимір часу сортування.
З. Створення обернено відсортованого 3-вимірного масиву, сортування його гібридним алгоритмом вибір №4 – обмін з обходом №2, вимір часу сортування.
І. Створення невідсортованого 3-вимірного масиву, сортування його гібридним алгоритмом вибір №4 – обмін з обходом №3, вимір часу сортування.
Ї. Створення відсортованого 3-вимірного масиву, сортування його гібридним алгоритмом вибір №4 – обмін з обходом №3, вимір часу сортування.
Й. Створення обернено відсортованого 3-вимірного масиву, сортування його гібридним алгоритмом вибір №4 – обмін з обходом №3, вимір часу сортування.
К. Запуск усіх алгоритмів сортування в пакетному режимі.
Результати
Вимірювання проводилось в середовищі DOSBox 0.72
Одиниці вимірювання всіх результатів – соті долі секунди.
Виміри для порівняння сортування масиву та вектора та сортування векторів для різних типів векторів.
Частота 50.
Одновимірний масив.
Таблиця №1 для масиву A[n], де n=20;
|
Відсортований |
Не відсортований |
Обернений |
|
|
Вектор |
5 |
11 |
6 |
Таблиця №2 для масиву A[n], де n=35;
|
Відсортований |
Не відсортований |
Обернений |
|
|
Вектор |
21 |
28 |
22 |
Таблиця №3 для масиву A[n], де n=60;
|
Відсортований |
Не відсортований |
Обернений |
|
|
Вектор |
55 |
66 |
55 |
3-Вимірний масив.
1. Довгий (p*m*n=60)
Таблиця №4 для масиву A[p,m,n], де p=1; m=3; n=20;
|
Відсортований |
Не відсортований |
Обернений |
|
|
Перепис у вектор |
44 |
49 |
45 |
|
Уявний вектор |
214 |
258 |
220 |
|
Прямий доступ |
132 |
154 |
133 |
Довгий (p*m*n=60)
Таблиця №5 для масиву A[p,m,n], де p=2; m=2; n=15;
|
Відсортований |
Не відсортований |
Обернений |
|
|
Перепис у вектор |
22 |
33 |
28 |
|
Уявний вектор |
110 |
137 |
121 |
|
Прямий доступ |
66 |
82 |
66 |
2. Високий (p*m*n=60)
Таблиця №6 для масиву A[p,m,n], де p=1; m=20; n=3;
|
Відсортований |
Не відсортований |
Обернений |
|
|
Перепис у вектор |
44 |
49 |
44 |
|
Уявний вектор |
231 |
291 |
236 |
|
Прямий доступ |
154 |
193 |
160 |
Високий (p*m*n=60)
Таблиця №7 для масиву A[p,m,n], де p=2; m=15; n=2;
|
Відсортований |
Не відсортований |
Обернений |
|
|
Перепис у вектор |
22 |
28 |
22 |
|
Уявний вектор |
110 |
142 |
116 |
|
Прямий доступ |
71 |
94 |
77 |
3. Квадратний (p*m*n=56≈60)
Таблиця №8 для масиву A[p,m,n], де p=1; m=8; n=7;
|
Відсортований |
Не відсортований |
Обернений |
|
|
Перепис у вектор |
39 |
44 |
39 |
|
Уявний вектор |
187 |
220 |
192 |
|
Прямий доступ |
115 |
132 |
116 |
Квадратний (p*m*n=60)
Таблиця №9 для масиву A[p,m,n], де p=2; m=5; n=6;
|
Відсортований |
Не відсортований |
Обернений |
|
|
Перепис у вектор |
22 |
28 |
28 |
|
Уявний вектор |
109 |
143 |
121 |
|
Прямий доступ |
66 |
82 |
71 |
Виміри для порівняння між собою алгоритмів сортування тривимірних масивів.
1. Залежність від кількості перерізів. Частота 40000.
Таблиця №10 для масиву A[p,m,n], де p=1; m=40; n=40;
|
Відсортований |
Не відсортований |
Обернений |
|
|
Перепис у вектор |
32 |
33 |
33 |
|
Уявний вектор |
181 |
204 |
181 |
|
Прямий доступ |
115 |
126 |
116 |
Таблиця №11 для масиву A[p,m,n], де p=5; m=40; n=40;
|
Відсортований |
Не відсортований |
Обернений |
|
|
Перепис у вектор |
165 |
170 |
154 |
|
Уявний вектор |
1010 |
1033 |
917 |
|
Прямий доступ |
615 |
631 |
571 |
Таблиця №12 для масиву A[p,m,n], де p=10; m=40; n=40;
|
Відсортований |
Не відсортований |
Обернений |
|
|
Перепис у вектор |
330 |
346 |
307 |
|
Уявний вектор |
1988 |
2065 |
1823 |
|
Прямий доступ |
1219 |
1264 |
1132 |
2. Вплив геометричних форм. Частота 2000.
m*n=100 – const; p=15 – const;
1. Довгі перерізи
Таблиця №13 для масиву A[p,m,n], де p=15; m=2; n=50;
|
Відсортований |
Не відсортований |
Обернений |
|
|
Перепис у вектор |
39 |
49 |
44 |
|
Уявний вектор |
214 |
264 |
220 |
|
Прямий доступ |
132 |
159 |
138 |
2. Квадратні перерізи
Таблиця №14 для масиву A[p,m,n], де p=15; m=10; n=10;
|
Відсортований |
Не відсортований |
Обернений |
|
|
Перепис у вектор |
38 |
49 |
39 |
|
Уявний вектор |
214 |
270 |
220 |
|
Прямий доступ |
131 |
159 |
137 |
3. Високі перерізи
Таблиця №15 для масиву A[p,m,n], де p=15; m=50; n=2;
|
Відсортований |
Не відсортований |
Обернений |
|
|
Перепис у вектор |
43 |
50 |
44 |
|
Уявний вектор |
220 |
269 |
219 |
|
Прямий доступ |
143 |
176 |
148 |
Порівняльний аналіз алгоритмів
1. Для одновимірного масиву відносно загальновідомої теорії.
Для гібридного алгоритму вибір №4 – обмін найкращим виявився відсортований масив. Адже саме у такому випадку, на відміну від інших, ми робимо 0 перестановок, а також для кожного з елементів невідсортованої частини ми робимо по 2 перевірки (A[i] < A[L] та A[i] > A[R]) на кожному з рівнів відсортованості. Для обернено відсортованого випадку ситуація трохи гірша, кількість перевірок така ж сама (true повертатиме тільки друга умова A[i] > A[R] ), але кількість перестановок стає {n\2} (по одній на кожен рівень відсортованості). Хоча на практиці виявилось що різниця між відсортованим та обернено відсортованим майже відсутня для невеликих масивів. Очевидно, що для невідсортованого масиву алгоритм працює найдовше, так як в цьому випадку кількість перевірок скоріше за все незначно зменшиться, зате кількість перестановок збільшиться сильніше.
2. Для багатовимірних масивів відносно результатів для одномірного масиву.
Згідно теорії, для обходу 1, різниця між швидкістю сортування вектора розміром [m*n] та масиву [m,n] має бути не дуже великою, адже переписування елементів є досить швидкою операцією (проте це сповільнює алгоритм з лінійною залежністю від розмірів, тобто чим більшим буде масив тим більшою буде різниця відносно швидкості сортування вектора з такою ж кількістю елементів). Зате серйозним мінусом такого обходу є надмірне використання пам’яті (переписуючи переріз у вектор ми використовуємо її в 2 рази більше). Але на практиці виявилось трохи інакше. Це пов’язано з особливостями реалізації алгориму: для процедури сортування вектора використовується глобальна змінна, оголошена у модулі Globals, а в сортуванні масиву обходом №1 для переписування використовується вектор, оголошений в межах процедури сортування.
Обхід №2 використовує ту ж логіку сортування, що і обхід №1, але в ньому замість переписування перерізу вектора використовується такий ж вектор, але уявний. Він задається формулами (i-1) mod m + 1,(i-1) div m + 1. Але
він виявився набагато повільнішим за сортування вектора в середньому у 5 разів. Це пов’язано зі складністю операцій mod та div для обчислення на процесорі. Фактично під час кожного звертання до будь-якого елемента уявного вектора ми виконуємо 4 прості арифметичні операції (+,-) та 2 складні (mod, div), що надзвичайно сильно зменшує швидкодію алгоритму.
Обхід №3 як помітно з результатів затрачає набагато більше часу на індексацію (замість одного індексу ми використовуємо по два). Також сповільнює алгоритм і використання складніших операторів циклів (while замість for) а також складніших умов в циклах (замість (L<R) умова (Lj<Rj) or ((Lj=Rj) and (Li<Ri))). Тому даний обхід теж досить серйозно програє сортуванню вектора в звязку з витратами часу на індексацію а також на перевірки умов.
Також можна помітити що для всіх обходів, сортування однакової кількості елементів залежить від кількості перерізів: чим перерізів більше, тим швидше відбуватиметься сортування. Це очевидно, адже у алгоритму вибір №4 – обмін не лінійна залежність швидкодії від розмірів, і чим більший масив тим повільніше він сортується. Тому сортування масиву з 1 перерізом і 60 елементами, відбувається повільніше ніж такого ж масиву, але з 2-ма перерізами по 30 елементів.
3. Для заданих алгоритмів на багатовимірних масивах між собою.
Спираючись на таблиці 10-12 можна сказати, що обхід №1 є найшвидшим. Він є крайньою межею залежності швидкодія-пам'ять (максимальна швидкість - найбільше використання пам’яті). Обхід №2 набагато повільніший за алгоритм №1 через велику кількість складних для обчислення процесором операцій. Обхід №3 повільніший за обхід №1, але швидший за обхід №2. При чому зі збільшенням кількості перерізів час виконання нелінійно зростає (у обходу №1 через сам алгоритм, у №2 через нелінійне зростання кількості складних операцій ділення, а у №3 через нелінійне зростання кількості перевірок та індексування). Слід також зауважити що найстрімкіше зростання часу виконання у обходу №2 та наповільніше у №1.
4. Вплив різних геометричних розмірів багатовимірних масивів на поведінку алгоритмів та їх взаємовідношення між собою.
Обходи №1та №2 зводяться до роботи з вектором, тому геометрична форма впливу на них не несе. Обхід №3 також майже не чутливий до геометричних форм, невелике сповільнення для високих перерізів приносять умови 2 циклів while, адже у довгих перерізів набагато частіше виконується перша частина умови і другу перевіряти вже не треба. А відповідно у високих перерізів перша умова виконується набагато рідше і необхідно виконувати другу, подвійну.
Висновки
Отже вибір кращого з обходів алгоритму залежить від того що для нас важливіше: економне використання пам’яті чи швидкодія. У випадках коли пам’яттю можна знехтувати найкращим вибором є хоча і примітивний, але швидкий обхід №1.
Якщо ж кількість пам’яті у нас обмежена, то кращим вибором буде обхід №3, який хоча й не такий швидкий, але не використовує багато додаткової пам’яті.
Найближчим по швидкодії до сортування вектора є звісно ж обхід №1, адже він додатково витрачає тільки час на переписування одного перерізу масиву у вектор, який потім відправляється на сортування за тим же алгоритмом що і просто вектор.
В звязку з тим що всі 3 обходи так чи інакше зводяться до векторів, геометричні форми майже не несуть на них впливу. Впливає на них тільки кількість перерізів в матриці, що повязано з нелінійним сповільненням алгоритму зі збільшенням розмірів вектора сортування. Тому можна навіть досягти такої ситуації, що сортування матриці з великою кількістю перерізів відбуватиметься швидше ніж сортування вектора з тією ж кількістю елементів.
Список літератури
PAGE \* MERGEFORMAT 1
Main
Globals
ools
Sort
Menu
Main
BuildMenu
ChoiseArray3D_1
ChoiseVector
ChoiseArray3D_2
ChoiseArray3D_3
ChoiseArray3D_All
OutVector
GenerateRandomVector
GenerateSortedVector
GenerateInvsortedVector
SortVector
OutArray3D
Vector2Array3D
SortArray3D_1
SortArray3D_2
SortArray3D_3
ResTime