Дослідження ефективності методів сортування на багатовимірних масивах

Національний технічний університет України

«Київський політехнічний інститут»

Факультет прикладної математики Кафедра специалізованих компьютерних систем

Курсова робота

з дисципліни «Структури даних та алгоритми «

тема «Дослідження ефективності методів сортування на багатовимірних масивах«

Варіант № 3

1. Технічне завдання

1. Описати принцип роботи кожного з методів, що досліджуються, для одновимірного випадку.

2. Скласти алгоритми сортування в багатовимірному масиві методами, що задані за варіантом.

3. Провести практичні дослідження швидкодії складених алгоритмів.

4. За результатами досліджень скласти порівняльні таблиці за різноманітними ознаками.

5. Зробити висновки про порівняння отриманих результатів.

P. S. При бажанні, можна дослідити вплив геометричних розмірів масиву на швидкість сортування, тобто не змінюючи загальної кількості елементів змінювати геометричні розміри масиву. Для випадку перестановки перерізів, не повинна змінюватись загальна кількість перерізів та загальна кількість елементів масиву, а іншими параметрами розмірності можна варіювати. Для випадку перестановки рядків/стовпців у кожному перерізі - не повинна змінюватись кількість рядків/стовпців у кожному перерізі та загальна кількість елементів масиву.

Задача

Впорядкувати тривимірний масив A[m, n, p] наступним чином: переставити перерізи масиву (зміна другого індексу змінює номер перерізу) за не спаданням сум елементів перших рядків кожного перерізу.

Методи

1. Вибір.

2. Вставка з лінійним пошуком місця вставки від взятого елемента («справа») без бар'єру.

3. Шейкерне сортування.

1.4. Стан масиву

Вихідний масив впорядкований, як задано за варіантом.

Елементи вихідного масиву невпорядковані.

Вихідний масив впорядкований протилежно, ніж задано за варіантом

2. Опис теоретичних положень

2.1 Сортування вибором

Опис алгоритму: алгоритм сортування масиву за не спаданням методом вибору можна описати так:

1. Серед всіх елементів масиву, починаючи з першого, будь яким способом відшукується мінімальний елемент.

2. Знайдений мінімальний елемент поміщається на місце першого елементу.

3. Перевіряється масив від другого елементу, знаходиться мінімальний серед тих, що залишилися і поміщається на місце другого елементу.

4. І так далі до останнього елементу.

Малюнок 2.1 — Алгоритм сортування по не спаданню методом вибору.

Аналіз описаних вище дій при сортуванні вибором показує, що для програмної реалізації цього методу сортування буде потрібно два цикли for.

У зовнішньому циклі повинен змінюватися номер змінного елементу від першого до передостаннього. Цей цикл визначатиме кількість проходів по масиву. Внутрішній цикл повинен забезпечити послідовне порівняння змінного елементу зі всіма елементами, які слідують в масиві за ним. У тілі внутрішнього циклу виробляється порівняння елементів.

У тілі внутрішнього циклу виробляється порівняння елементів, індекси яких задаються параметрами зовнішнього і внутрішнього циклу. Якщо при порівнянні виявляється, що порядок дотримання елементів порушений, то порівнювані елементи міняються місцями. Схема алгоритму сортування масиву методом вибору показана на малюнку 2.1. Вихідними даними для алгоритму є: сортований масив mas і кількість елементів в цьому масиві count

Процедура сортування масиву методом вибору

procedure SortChoise (var a: TArray100; count: integer);

var i, j, x: integer;

begin

for i := 1 to count — 1 do

begin

for j := i + 1 to count do

if a[j] > a[i] then

begin

x := a[i];

a[i] := a[j];

a[j] := x;

end;

end;

end;

2.2 Вставка з лінійним пошуком місця вставки від взятого елемента («справа») без бар'єру

Сортування вставкою або включенням. Суть алгоритму в наступному — елементи масиву розділяють на впорядковану частину А[1], А[2], ., А[i-1], яка розташовується на початку масиву, і останню, невпорядковану частину А[i], …, А[N], а потім, поодинці, елементи з невпорядкованої частини переносяться у впорядковану. Перед початком сортування впорядкована частина складається всього з одного, першого елементу, а всі останні елементи розташовуються в другій частині масиву.

Послідовні кроки алгоритму сортування полягають в тому, що перший елемент з неврегульованої частини порівнюється з останнім елементом впорядкованої послідовності. Якщо виявляється, що порядок розташування порівнюваних елементів не відповідає вимогам сортування, то елемент з неврегульованої частини витягується і переноситься у впорядковану частину. Місце для цього елементу звільняється шляхом зрушення впорядкованих елементів управо на місце елементу, що вилучається. Зрушення впорядкованих елементів на одну позицію управо продовжуються до тих пір, поки не буде знайдено місце для елементу, що вилучається з неврегульованої послідовності.

Як видно з малюнка 2.2, в алгоритмі є два цикли. У зовнішньому циклі послідовно змінюється номер лівого кордону неврегульованої області від значення i = 2 до i = count. У телі цього циклу виробляється порівняння елементів, що знаходяться по обидві сторони від кордону, що розділяє впорядковану і невпорядковану частини. Якщо порядок порушений, то перший елемент неврегульованої послідовності запам’ятовується в змінній tmp і, тим самим, звільняється місце для зрушень впорядкованих елементів вправо.

Внутрішній цикл забезпечує послідовні зрушення впорядкованих елементів управо, починаючи з останнього, до тих пір, поки не буде знайдено місце для першого елементу з неврегульованої області.

Можливість вставки елементу визначається одним з двох умов.

— mas[j-1] <= buf < mas[j] і 1 < j < i, тобто знайдено місце усередині впорядкованої послідовності.

— j=1, тобто tmp є найменшим елементом і вставляється на перше місце у впорядкованій частині масиву.

Після завершення циклу зрушень елемент масиву із змінної tmp переноситься на знайдене місце у впорядкованій послідовності.

Малюнок 2.2 — Алгоритм сортування по неспаданню методом вставки Процедура сортування методом вставки

procedure SortInsert (var a: TArray100; count: integer);

var i, j, x: integer;

begin

for i := 2 to count do

begin

// Порівнюємо елементи на границі між

// впорядкованими та невпорядкованими частинами масиву

if a[i] < a[i-1] then

begin

// Порядок порушений, запамятовуємо i-й елемент

x := a[i];

// Починаємо цикл зрушень вправо на місце i-го елементу

j := i;// j — індекс вакантного місця

repeat

// зрушуємо вправо

a[j]: =a[j-1];

j:=j-1;

// поки зліва не зявилось меньше число,

// або дішли до початку масиву

until (j = 1) or (a[j-1] <= x);

//'Тепер вставим колишній i-й елемент на нове місцез індексом j

a[j] := x;

end;

end;

end;

2.3 Метод шейкерного сортування

Метод шейкерного сортування є удосконаленим методом сортування обміном із запам’ятовуванням місця останньої перестановки. Основна ідея методу полягає в тому, що послідовні проходи по масиву здійснюються з двох боків, і відсортованих частин у масиві є дві, причому вони з двох сторін «насуваються» на невпорядковану частину. Пари елементів послідовно порівнюються, та, якщо їх порядок розташування не відповідає певному критерію, елементи міняються місцями. Таким чином, найбільший елемент «спливає» у кінець масиву, а найменший — «тоне» у початок.

Метод шейкерного сортування за визначенням не зменшує кількість обмінів, але кількість порівнянь у нього є зазвичай меншою, аніж у методу обміну. Гарним прикладом переваги шейкерного методу над методом обміну може бути послідовність 2, 3, 4, 5, 1, яку необхідно впорядкувати за неспаданням. Методом шейкерного сортування достатньо 1−2 проходи (залежно від того, з якого боку починати), а методом обміну знадобилося б чотири проходи, якщо кожен раз починати прохід з початку масиву.

Складність алгоритму O (nІ), для найгіршого та середнього способу розташування, якщо масив майже відсортовано — прямує до O (n).

Для сортування тривимірного масиву згідно із варіантом завдання алгоритм ускладнюється так само як і для методу обміну.

Схематично (у вигляді блок-схеми) алгоритм шейкерного сортування зображено на Рис 2.3.

Малюнок 2.3. Алгоритм шейкерного сортування (блок-схема)

3. Лістинг програми з коментарями

unit unitSort3D;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, UnitDop, sort3DArrayDop;

type

TfrmSort3D = class (TForm)

Label5: TLabel;

Label6: TLabel;

memSortResults: TMemo;

edtSizeM: TEdit;

btnCreateTestArrays: TButton;

memSortDetails: TMemo;

edtSizeP: TEdit;

edtSizeN: TEdit;

btnLaunchSort: TButton;

btnCompareSortingbyOperations: TButton;

btnCalculateForAlternateSize: TButton;

GroupBox1: TGroupBox;

Label2: TLabel;

Label3: TLabel;

Label4: TLabel;

GroupBox2: TGroupBox;

Label1: TLabel;

Label7: TLabel;

Label8: TLabel;

procedure FormCreate (Sender: TObject);

procedure btnCreateTestArraysClick (Sender: TObject);

procedure btnLaunchSortClick (Sender: TObject);

procedure btnCompareSortingbyOperationsClick (Sender: TObject);

procedure btnCalculateForAlternateSizeClick (Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

frmSort3D: TfrmSort3D;

ad, ad1, ad2,ad3:TArrayDyn;

implementation

{$R *.dfm}

procedure TfrmSort3D. FormCreate (Sender: TObject);

begin

edtSizeM.Text:='100';

edtSizeP.Text:='100';

edtSizeN.Text:='100';

end;

procedure TfrmSort3D. btnCreateTestArraysClick (Sender: TObject);

var

i, j, k, sizeN, sizeM, sizeP: integer;

begin

//Очистити поле результатів

memSortResults.clear;

memSortDetails.clear;

sizeN:=StrToInt (edtSizeN.Text);

sizeM:=StrToInt (edtSizeM.Text);

sizeP:=StrToInt (edtSizeP.Text);

SetLength (ad, sizeN, sizeM, sizeP);

SetLength (ad1,sizeN, sizeM, sizeP);

Randomize;

for i :=0 to sizeN-1 do

for j :=0 to sizeM-1 do

for k:=0 to sizeP-1 do

begin

ad[i, j, k]: =Random (100);

ad1[i, j, k]:= ad[i, j, k];

end;

memSortDetails.Lines.Append ('Масив ' +InttoStr (SizeN)+'x' +InttoStr (SizeM)+'x' +InttoStr (SizeP)+ ' створено');

if (sizeN<5) and (sizeM<5) and (sizeP<5) then

begin

showArrayDyninMemo (ad, sizeN, sizeM, sizeP, memSortDetails);

showArrayDyninMemo (ad1,sizeN, sizeM, sizeP, memSortDetails);

end;

end;

procedure TfrmSort3D. btnLaunchSortClick (Sender: TObject);

var sizeN, sizeM, sizeP: integer;

begin

//Зчитати розмір масиву

sizeN:=StrToInt (edtSizeN.Text);

sizeM:=StrToInt (edtSizeM.Text);

sizeP:=StrToInt (edtSizeP.Text);

//запускаємо процедуру сортування та виведення масиву

sortArrayAndShowResultsInMemo (ad, ad1, sizeN, sizeM, sizeP, memSortResults, memSortDetails)

end;

procedure TfrmSort3D. btnCompareSortingbyOperationsClick (Sender: TObject);

var i, j, k, sizeN, sizeM, sizeP: integer;

pCountByInsertion, pCountSelection, pCountShaker: int64;

begin

//Зчитати розмір масиву

sizeN:=StrToInt (edtSizeN.Text);

sizeM:=StrToInt (edtSizeM.Text);

sizeP:=StrToInt (edtSizeP.Text);

//вивести заголовок результатів

memSortResults.Lines.Append (

Порівняння методів сортувань за кількістю переміщень'

+InttoStr (sizeN) + 'x'+InttoStr (sizeM)+'x'+InttoStr (sizeP));

memSortResults.Lines.Append ('Вставка |Обмін| Шейкер');

pCountByInsertion:=0;

pCountSelection:=0;

pCountShaker:=0;

//зчитати масив ad1 з ad

for i:=0 to sizeN-1 do

for j:=0 to sizeM-1 do

for k:=0 to sizeP-1 do

begin

ad1[i, j, k]: =ad[i, j, k]

end;

{==============

Процеси сортування}

//Сортувати невпорядкований масив вставкою із підрахунком кількості переміщень

sortDynByInsertionCount (ad1,pCountByInsertion, sizeN, sizeM, sizeP);

//зчитати масив ad1 з ad

for i:=0 to sizeN-1 do

for j:=0 to sizeM-1 do

for k:=0 to sizeP-1 do

begin

ad1[i, j, k]: =ad[i, j, k]

end;

//Сортувати невпорядкований масив вибором із підрахунком кількості переміщень

sortDynSelectionCount (ad1,pCountSelection, sizeN, sizeM, sizeP);

//зчитати масив ad1 з ad

for i:=0 to sizeN-1 do

for j:=0 to sizeM-1 do

for k:=0 to sizeP-1 do

begin

ad1[i, j, k]: =ad[i, j, k]

end;

//Сортувати невпорядкований масив шейкером із підрахунком кількості переміщень

sortDynShakerCount (ad1,pCountShaker, sizeN, sizeM, sizeP);

memSortResults.Lines.Append ('——Переміщень для випадкового масиву———-');

memSortResults.Lines.Append (format (' %1.4d %1.4d %1.4d ',

[pCountByInsertion, pCountSelection, pCountShaker]));

pCountByInsertion:=0;

pCountSelection:=0;

pCountShaker:=0;

//Сортувати впорядкований масив вставкою із підрахунком кількості переміщень

sortDynByInsertionCount (ad1,pCountByInsertion, sizeN, sizeM, sizeP);

//Сортувати впорядкований масив вибором із підрахунком кількості переміщень

sortDynSelectionCount (ad1,pCountSelection, sizeN, sizeM, sizeP);

//Сортувати впорядкований масив шейкером із підрахунком кількості переміщень

sortDynShakerCount (ad1,pCountShaker, sizeN, sizeM, sizeP);

memSortResults.Lines.Append ('——Переміщень для відсортованого масиву———-');

memSortResults.Lines.Append (format (' %1.4d %1.4d %1.4d ',

[pCountByInsertion, pCountSelection, pCountShaker]));

pCountByInsertion:=0;

pCountSelection:=0;

pCountShaker:=0;

//Сортувати зворотно впорядкований масив вставкою із підрахунком кількості переміщень

sortDynByInsertionReverse (ad1,sizeN, sizeM, sizeP);

sortDynByInsertionCount (ad1,pCountByInsertion, sizeN, sizeM, sizeP);

//Сортувати зворотно впорядкований масив вибором із підрахунком кількості переміщень

sortDynByInsertionReverse (ad1,sizeN, sizeM, sizeP);

sortDynSelectionCount (ad1,pCountSelection, sizeN, sizeM, sizeP);

//Сортувати зворотно впорядкований масив шейкером із підрахунком кількості переміщень

sortDynByInsertionReverse (ad1,sizeN, sizeM, sizeP);

sortDynShakerCount (ad1,pCountShaker, sizeN, sizeM, sizeP);

memSortResults.Lines.Append ('—Переміщень для зворотно відсортованого масиву——');

memSortResults.Lines.Append (format (' %1.4d %1.4d %1.4d ',

[pCountByInsertion, pCountSelection, pCountShaker]));

end;

procedure TfrmSort3D. btnCalculateForAlternateSizeClick (Sender: TObject);

var sizeN, sizeM, sizeP,

sizeNad2,sizeMad2,sizePad2,

i, j, k, j_ad2,k_ad2:integer;

begin

//зчитати розмір масиву

sizeN:=StrToInt (edtSizeN.Text);

sizeM:=StrToInt (edtSizeM.Text);

sizeP:=StrToInt (edtSizeP.Text);

//задати довжину для масивів

sizeNad2:=sizeN;

sizeMad2:=sizeM div 2;

sizePad2:=sizeP*2;

SetLength (ad2,sizeNad2,sizeMad2,sizePad2);

SetLength (ad3,sizeNad2,sizeMad2,sizePad2);

//зчитати массив з ad в ad2 и ad3 з урахуванням зміни геометричних розмірів перерізу

for i:=0 to sizeN-1 do

begin

j_ad2:=0;

for j:=0 to sizeM-1 do

begin

if j mod 2 = 0

then k_ad2:=0

else k_ad2:=sizeP;

for k:=0 to sizeP-1 do

begin

ad2[i, j_ad2,k_ad2]: =ad[i, j, k];

ad3[i, j_ad2,k_ad2]:=ad[i, j, k];

k_ad2:=k_ad2+1;

end;

if j mod 2 = 1

then j_ad2:=j_ad2+1;

end;

end;

memSortDetails.Lines.Append ('Масив набув нових геометричних розмірів:'+

IntToStr (sizeNad2)+ 'x'+ IntToStr (sizeMad2)+'x' +IntToStr (sizePad2));

//Якщо масив невеликий, відображаємо його

if (sizeNad2<11) and (sizeMad2 <11) and (sizePad2<11) then

begin

memSortDetails.Lines.Append ('Новий масив:'+ IntToStr (sizeNad2)+ 'x'+

IntToStr (sizeMad2)+'x' +IntToStr (sizePad2));

showArrayDyninMemo (ad2,sizeNad2,sizeMad2,sizePad2,memSortDetails);

end;

//запускаємо процедуру сортування та виведення масиву

sortArrayAndShowResultsInMemo (ad2,ad3,sizeNad2,sizeMad2,sizePad2,memSortResults, memSortDetails);

//задать длину для массивов

sizeNad2:=sizeN;

sizeMad2:=sizeM*2;

sizePad2:=sizeP div 2;

SetLength (ad2,sizeNad2,sizeMad2,sizePad2);

SetLength (ad3,sizeNad2,sizeMad2,sizePad2);

//зчитати массив з ad в ad2 и ad3 з урахуванням зміни геометричних розмірів перерізу

for i:=0 to sizeN-1 do

begin

j_ad2:=0;

for j:=0 to sizeM-1 do

begin

k_ad2:=0;

for k:=0 to sizeP-1 do

begin

ad2[i, j_ad2,k_ad2]: =ad[i, j, k];

ad3[i, j_ad2,k_ad2]:=ad[i, j, k];

//if row ended atart from next row

if k=sizePad2−1

then

begin j_ad2:=j_ad2+1;

k_ad2:=0;

end

else

k_ad2:=k_ad2+1;

end;

j_ad2:=j_ad2+1

end;

end;

memSortDetails.Lines.Append ('Масив набув нових геометричних розмірів:'+

IntToStr (sizeNad2)+ 'x'+ IntToStr (sizeMad2)+'x' +IntToStr (sizePad2));

//Якщо масив невеликий, відображаємо його

if (sizeNad2<50) and (sizeMad2 <50) and (sizePad2<50) then

begin

memSortDetails.Lines.Append ('Новый массив:'+ IntToStr (sizeNad2)+ 'x'+

IntToStr (sizeMad2)+'x' +IntToStr (sizePad2));

showArrayDyninMemo (ad2,sizeNad2,sizeMad2,sizePad2,memSortDetails);

end;

//запускаємо процедуру сортування та виведення масиву

sortArrayAndShowResultsInMemo (ad2,ad3,sizeNad2,sizeMad2,sizePad2,memSortResults, memSortDetails)

end;

end.

Допоміжний модуль:

unit sort3DArrayDop;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls;

type

TArray1D = Array[0.1 000 000] of integer;

TArrayDyn = Array of Array of Array of integer;

procedure showArrayDyninMemo (a: TArrayDyn;sizeN, sizeM, sizeP: integer;m: Tmemo);

procedure sortArrayAndShowResultsInMemo (a, a1: TArrayDyn;sizeN, sizeM, sizeP: integer;memSortResults, memSortDetails: Tmemo);

procedure sortDynByInsertion (var ad: TArrayDyn; sizeN, sizeM, sizeP: integer);

procedure sortDynByInsertionReverse (var ad: TArrayDyn; sizeN, sizeM, sizeP: integer);

procedure sortDynSelection (var ad: TArrayDyn; sizeN, sizeM, sizeP: integer);

procedure sortDynSelectionReverse (var ad: TArrayDyn; sizeN, sizeM, sizeP: integer);

procedure sortDynShaker (var ad: TArrayDyn; sizeN, sizeM, sizeP: integer);

procedure sortDynShakerReverse (var ad: TArrayDyn; sizeN, sizeM, sizeP: integer);

procedure sortDynByInsertionCount (var ad: TArrayDyn; var pCount: int64; sizeN, sizeM, sizeP: integer);

procedure sortDynSelectionCount (var ad: TArrayDyn; var pCount: int64; sizeN, sizeM, sizeP: integer);

procedure sortDynShakerCount (var ad: TArrayDyn; var pCount: int64; sizeN, sizeM, sizeP: integer);

implementation

procedure showArrayDyninMemo (a: TArrayDyn;sizeN, sizeM, sizeP: integer;m: Tmemo);

var i, j, k: integer;

str: string;

begin

for i:=0 to sizeN-1 do

begin

m.lines.append (IntToStr (i));

for j:=0 to sizeM-1 do

begin

str:=inttostr (a[i, j,0]);

for k:=1 to sizeP-1 do

begin

str:=str+' ' + IntToStr (a[i, j, k])

end;

m.lines.append (str);

end;

end;

end;

procedure sortArrayAndShowResultsInMemo (a, a1: TArrayDyn;sizeN, sizeM, sizeP: integer;memSortResults, memSortDetails: Tmemo);

var i, j, k, t1, t2,t, tSumInsertRandom, tSumInsertSorted, tSumInsertSortedReverse,

tSumSelectionRandom, tSumSelectionSorted, tSumSelectionSortedReverse,

tSumShakerRandom, tSumShakerSorted, tSumShakerSortedReverse: integer;

begin

{===============================================

Заголовок результатів}

memSortResults.Lines.Append ('Результати сортування массиву' +InttoStr (sizeN) + 'x'+InttoStr (sizeM)+'x'+InttoStr (sizeP));

memSortResults.Lines.Append ('Невпорядкований|Впорядкований|Зворотно впорядкований');

tSumInsertRandom:=0;

tSumInsertSorted:=0;

tSumInsertSortedReverse:=0;

tSumSelectionRandom:=0;

tSumSelectionSorted:=0;

tSumSelectionSortedReverse:=0;

tSumShakerRandom:=0;

tSumShakerSorted:=0;

tSumShakerSortedReverse:=0;

//зчитати масив a1 з a

for i:=0 to sizeN-1 do

for j:=0 to sizeM-1 do

for k:=0 to sizeP-1 do

begin

a1[i, j, k]: =a[i, j, k]

end;

if (sizeN<=10) and (sizeM<=10) and (sizeP<=10)

then begin

memSortDetails.Lines.append ('Вихідний невпорядкований масив для сортування вибором');

showArrayDyninMemo (a1,sizeN, sizeM, sizeP, memSortDetails);

memSortDetails.Lines.append ('');

end;

{===========================

Сортувати випадковий масив вибором}

t1:=GetTickCount;

sortDynSelection (a1,sizeN, sizeM, sizeP);

t2:=GetTickCount;

t:=t2-t1;

tSumSelectionRandom:=tSumSelectionRandom+t;

if (sizeN<=10) and (sizeM<=10) and (sizeP<=10)

then begin

memSortDetails.Lines.append ('Відсортований неупорядкований масив для сортування вибором');

showArrayDyninMemo (a1,sizeN, sizeM, sizeP, memSortDetails);

memSortDetails.Lines.append ('');

end;

{====================

сортувати впорядкований масив вибором}

t1:=GetTickCount;

sortDynSelection (a1,sizeN, sizeM, sizeP);

t2:=GetTickCount;

t:=t2-t1;

tSumSelectionSorted:=tSumSelectionSorted+t;

if (sizeN<=10) and (sizeM<=10) and (sizeP<=10)

then begin

memSortDetails.Lines.append ('Впорядкований впорядкований масив для сортування вибором');

showArrayDyninMemo (a1,sizeN, sizeM, sizeP, memSortDetails);

memSortDetails.Lines.append ('');

end;

{=================

Сортувати зворотно впрорядкований масив вибором}

sortDynSelectionReverse (a1,sizeN, sizeM, sizeP);

if (sizeN<=10) and (sizeM<=10) and (sizeP<=10)

then begin

memSortDetails.Lines.append ('Вихідний зворотно впорядкований масив для сортування вибором');

showArrayDyninMemo (a1,sizeN, sizeM, sizeP, memSortDetails);

memSortDetails.Lines.append ('');

end;

t1:=GetTickCount;

sortDynSelection (a1,sizeN, sizeM, sizeP);

t2:=GetTickCount;

t:=t2-t1;

tSumSelectionSortedReverse:=tSumSelectionSortedReverse+t;

if (sizeN<=10) and (sizeM<=10) and (sizeP<=10)

then begin

memSortDetails.Lines.append ('Впорядкований зворотно впорядкований масив для сортування вибором');

showArrayDyninMemo (a1,sizeN, sizeM, sizeP, memSortDetails);

memSortDetails.Lines.append ('');

end;

//зчитуємо масив ad1 з ad

for i:=0 to sizeN-1 do

for j:=0 to sizeM-1 do

for k:=0 to sizeP-1 do

begin

a1[i, j, k]: =a[i, j, k]

end;

if (sizeN<=10) and (sizeM<=10) and (sizeP<=10)

then begin

memSortDetails.Lines.append ('Вихідний невпорядкований масив для сортування шейкером');

showArrayDyninMemo (a1,sizeN, sizeM, sizeP, memSortDetails);

memSortDetails.Lines.append ('');

end;

{================

сортувати невпорядкований масив шейкером}

t1:=GetTickCount;

sortDynShaker (a1,sizeN, sizeM, sizeP);

t2:=GetTickCount;

t:=t2-t1;

tSumShakerRandom:=tSumShakerRandom+t;

if (sizeN<=10) and (sizeM<=10) and (sizeP<=10)

then begin

memSortDetails.Lines.append ('Впорядкований неупорядовкований масив для сортування шейкером');

showArrayDyninMemo (a1,sizeN, sizeM, sizeP, memSortDetails);

memSortDetails.Lines.append ('');

end;

{===============

сортувати впорядкований масив шейкером}

t1:=GetTickCount;

sortDynShaker (a1,sizeN, sizeM, sizeP);

t2:=GetTickCount;

t:=t2-t1;

tSumShakerSorted:=tSumShakerSorted+t;

if (sizeN<=10) and (sizeM<=10) and (sizeP<=10)

then begin

memSortDetails.Lines.append ('Впорядкований впорядкований масив для сортування шейкером');

showArrayDyninMemo (a1,sizeN, sizeM, sizeP, memSortDetails);

memSortDetails.Lines.append ('');

end;

{==============

сортувати зворотно впорядкований масив шейкером}

sortDynShakerReverse (a1,sizeN, sizeM, sizeP);

if (sizeN<=10) and (sizeM<=10) and (sizeP<=10)

then begin

memSortDetails.Lines.append ('Вихідний зворотно впорядкований масив для сортування шейкером');

showArrayDyninMemo (a1,sizeN, sizeM, sizeP, memSortDetails);

memSortDetails.Lines.append ('');

end;

t1:=GetTickCount;

sortDynShaker (a1,sizeN, sizeM, sizeP);

t2:=GetTickCount;

t:=t2-t1;

tSumShakerSortedReverse:=tSumShakerSortedReverse+t;

if (sizeN<=10) and (sizeM<=10) and (sizeP<=10)

then begin

memSortDetails.Lines.append ('Впорядкований зворотно впорядкований масив для сортування вибором');

showArrayDyninMemo (a1,sizeN, sizeM, sizeP, memSortDetails);

memSortDetails.Lines.append ('');

end;

//зчитати масив ad1 з ad

for i:=0 to sizeN-1 do

for j:=0 to sizeM-1 do

for k:=0 to sizeP-1 do

begin

a1[i, j, k]: =a[i, j, k]

end;

if (sizeN<=10) and (sizeM<=10) and (sizeP<=10)

then begin

memSortDetails.Lines.append ('Вихідний невпорядкований масив для сортування вставкою');

showArrayDyninMemo (a1,sizeN, sizeM, sizeP, memSortDetails);

memSortDetails.Lines.append ('');

end;

{=============

сортувати невпорядкований масив вставкою}

t1:=GetTickCount;

sortDynByInsertion (a1,sizeN, sizeM, sizeP);

t2:=GetTickCount;

t:=t2-t1;

tSumInsertRandom:=tSumInsertRandom+t;

if (sizeN<=10) and (sizeM<=10) and (sizeP<=10)

then begin

memSortDetails.Lines.append ('Відсортований невпорядкований масив для сортування вставкою');

showArrayDyninMemo (a1,sizeN, sizeM, sizeP, memSortDetails);

memSortDetails.Lines.append ('');

end;

{===========

сортувати впорядкований масив вставкою}

t1:=GetTickCount;

sortDynByInsertion (a1,sizeN, sizeM, sizeP);

t2:=GetTickCount;

t:=t2-t1;

tSumInsertSorted:=tSumInsertSorted+t;

if (sizeN<=10) and (sizeM<=10) and (sizeP<=10)

then begin

memSortDetails.Lines.append ('Відсортований упорядкований масив для сортування вставкою');

showArrayDyninMemo (a1,sizeN, sizeM, sizeP, memSortDetails);

memSortDetails.Lines.append ('');

end;

{=============

сортувати зворотно впорядкований масив вставкою}

sortDynByInsertionReverse (a1,sizeN, sizeM, sizeP);

if (sizeN<=10) and (sizeM<=10) and (sizeP<=10)

then begin

memSortDetails.Lines.append ('Вихідний зворотно впорядкований масив для сортування вставкою');

showArrayDyninMemo (a1,sizeN, sizeM, sizeP, memSortDetails);

memSortDetails.Lines.append ('');

end;

t1:=GetTickCount;

sortDynByInsertion (a1,sizeN, sizeM, sizeP);

t2:=GetTickCount;

t:=t2-t1;

tSumInsertSortedReverse:=tSumInsertSortedReverse+t;

if (sizeN<=10) and (sizeM<=10) and (sizeP<=10)

then begin

memSortDetails.Lines.append ('Впорядкований зворотно впорядкований масив для сортування вставкою');

showArrayDyninMemo (a1,sizeN, sizeM, sizeP, memSortDetails);

memSortDetails.Lines.append ('');

end;

memSortResults.Lines.Append ('——дані по сортуванню вставкою———-');

memSortResults.Lines.Append (format (' %1.4d %1.4d %1.4d ',

[tSumInsertRandom, tSumInsertSorted, tSumInsertSortedReverse]));

memSortResults.Lines.Append ('——дані по сортуванню вибором———-');

memSortResults.Lines.Append (format (' %1.4d %1.4d %1.4d ',

[tSumSelectionRandom, tSumSelectionSorted, tSumSelection Sorted Reverse]));

memSortResults.Lines.Append ('——дані по сортуванню шейкром———-');

memSortResults.Lines.Append (format (' %1.4d %1.4d %1.4d ',

[tSumShakerRandom, tSumShakerSorted, tSumShakerSortedReverse]));

end;

{=====

сортування вставкою перерезів за НЕспаданням сум їх елементів}

procedure sortDynByInsertion (var ad: TArrayDyn; sizeN, sizeM, sizeP: integer);

var a1: TArray1D;

i, j, k, sum, b, c, l: integer;

//створення одновимірного масиву із сум елементів кожного перерізу

begin

for i:=0 to sizeN-1 do

begin

sum:=0;

for j:=0 to sizeM-1 do

begin

for k:=0 to sizeP-1 do

begin

sum:=sum+ad[i, j, k];

end;

end;

a1[i]:=sum;

end;

//пошук місця вставки

for i:=1 to sizeN-1 do

begin

c:=0;

b:=a1[i];

while a1[c]

begin

c:=c+1;

end;

if a1[c]=a1[i] then continue

else begin

//зсув елементів одновимірного масиву

for l:=i downto c+1 do

begin

a1[l]: =a1[l-1];

end;

//вставка на місце, що звільнилося

a1[c]: =b;

//зсув елементів тривімирного масиву і вставка на місце, що звільнилося

for j:=0 to sizeM-1 do

begin

for k:=0 to sizeP-1 do

begin

b:=ad[i, j, k];

for l:=i downto c+1 do

begin

ad[l, j, k]: =ad[l-1,j, k];

end;

ad[c, j, k]:=b;

end;

end;

end;

end;

{============

сортування вставкою перерізів за НЕзростанням суми їх елементів}

procedure sortDynByInsertionReverse (var ad: TArrayDyn; sizeN, sizeM, sizeP: integer);

var a1: TArray1D;

i, j, k, sum, b, c, l: integer;

//створення одновимірного масиву із сум елементів кожного перерізу

begin

for i:=0 to sizeN-1 do

begin

sum:=0;

for j:=0 to sizeM-1 do

begin

for k:=0 to sizeP-1 do

begin

sum:=sum+ad[i, j, k];

end;

end;

a1[i]:=sum;

end;

//пошук місця вставки

for i:=1 to sizeN-1 do

begin

c:=0;

b:=a1[i];

while a1[c]>b do

begin

c:=c+1;

end;

if a1[c]=a1[i] then continue

else begin

//зсув елементів одновимірного масиву

for l:=i downto c+1 do

begin

a1[l]: =a1[l-1];

end;

//вставка на місце, що звільнилося

a1[c]: =b;

//зсув елементів тривімирного масиву і вставка на місце, що звільнилося

for j:=0 to sizeM-1 do

begin

for k:=0 to sizeP-1 do

begin

b:=ad[i, j, k];

for l:=i downto c+1 do

begin

ad[l, j, k]: =ad[l-1,j, k];

end;

ad[c, j, k]:=b;

end;

end;

end;

end;

end;

{=================

Сортування вибором із запам’ятовуванням місця останньої перестановки перерізів за НЕспаданням суми їх елементів}

procedure sortDynSelection (var ad: TArrayDyn; sizeN, sizeM, sizeP: integer);

var a1: TArray1D;

i, j, k, sum, x, y, l: integer;

//створення одновимірного масиву із сум елементів кожного перерізу

begin

for i:=0 to sizeN-1 do

begin

sum:=0;

for j:=0 to sizeM-1 do

begin

for k:=0 to sizeP-1 do

begin

sum:=sum+ad[i, j, k];

end;

end;

a1[i]:=sum;

end;

// процедура сортування методом вибору

begin

for l:=i+1 to sizeN do

if a1[l]>a1[i] then

begin

//міняємо місцями елементи одновимірного масиву

x:=a1[i];

a1[i]:=a1[l];

a1[l]:=x;

begin

//міняємо місцями перерізи тривимірного масиву

for j:=0 to sizeM-1 do

begin

for k:=0 to sizeP-1 do

begin

y:=ad[i, j, k];

ad[i, j, k]:=ad[i+1,j, k];

ad[i+1,j, k]:=y;

end

{==============

Сортування вибором із запам’ятовуванням місця останньої перестановки перерізів за НЕзростанням суми їх елементів}

procedure sortDynSelectionReverse (var ad: TArrayDyn; sizeN, sizeM, sizeP: integer);

var a1: TArray1D;

i, j, k, sum, x, y, l, R:integer;

//створення одновимірного масиву із сум елементів кожного перерізу

begin

for i:=0 to sizeN-1 do

begin

sum:=0;

for j:=0 to sizeM-1 do

begin

for k:=0 to sizeP-1 do

begin

sum:=sum+ad[i, j, k];

end;

end;

a1[i]:=sum;

end;

// процедура сортування методом вибору

begin

for l:=i+1 to sizeN do

if a1[l]

begin

//міняємо місцями елементи одновимірного масиву

x:=a1[i];

a1[i]:=a1[l];

a1[l]:=x;

begin

//міняємо місцями перерізи тривимірного масиву

for j:=0 to sizeM-1 do

begin

for k:=0 to sizeP-1 do

begin

y:=ad[i, j, k];

ad[i, j, k]:=ad[i+1,j, k];

ad[i+1,j, k]:=y;

end

end;

{=======

Сортування шейкером перерізів за НЕзростанням суми їх елементів}

procedure sortDynShaker (var ad: TArrayDyn; sizeN, sizeM, sizeP: integer);

var a1: TArray1D;

i, j, k, sum, x, y, L, R, b: integer;

//створення одновимірного масиву із сум елементів кожного перерізу

begin

for i:=0 to sizeN-1 do

begin

sum:=0;

for j:=0 to sizeM-1 do

begin

for k:=0 to sizeP-1 do

begin

sum:=sum+ad[i, j, k];

end;

end;

a1[i]:=sum;

end;

//зовнішній цикл — поки границі відсортований частин не зійдуться

//L — ліва границя невідсортованої частини

//R — права границя невідсортованої частини

b:=0; L:=0;R:=sizeN-1;

while L

for i:=L to R-1 do

begin

if a1[i]>a1[i+1] then //якщо порядок розташування сусідніх елементів порушено

begin

//міняємо місцями елементи одновимірного масиву

x:=a1[i];

a1[i]:=a1[i+1];

a1[i+1]:=x;

//міняємо місцями перерізи тривимірного масиву

for j:=0 to sizeM-1 do

begin

for k:=0 to sizeP-1 do

begin

y:=ad[i, j, k];

ad[i, j, k]:=ad[i+1,j, k];

ad[i+1,j, k]:=y;

end

end;

b:=i;

end;

R:=b;

end;

//Зворотний прохід

for i:=R-1 downto L do

begin

if a1[i]>a1[i+1] then //якщо порядок розташування сусідніх елементів порушено

begin

//міняємо місцями елементи одновимірного масиву

x:=a1[i];

a1[i]:=a1[i+1];

a1[i+1]:=x;

//міняємо місцями перерізи тривимірного масиву

for j:=0 to sizeM-1 do

begin

for k:=0 to sizeP-1 do

begin

y:=ad[i, j, k];

ad[i, j, k]:=ad[i+1,j, k];

ad[i+1,j, k]:=y;

end

end;

b:=i;

end;

L:=b+1;

end;

end;

end;

{========

Сортування шейкером перерізів за НЕспаданням суми їх елементів}

procedure sortDynShakerReverse (var ad: TArrayDyn; sizeN, sizeM, sizeP: integer);

var a1: TArray1D;

i, j, k, sum, x, y, L, R, b: integer;

//створення одновимірного масиву із сум елементів кожного перерізу

begin

for i:=0 to sizeN-1 do

begin

sum:=0;

for j:=0 to sizeM-1 do

begin

for k:=0 to sizeP-1 do

begin

sum:=sum+ad[i, j, k];

end;

end;

a1[i]:=sum;

end;

//зовнішній цикл — поки границі відсортований частин не зійдуться

//L — ліва границя невідсортованої частини

//R — права границя невідсортованої частини

b:=0; L:=0;R:=sizeN-1;

while L

for i:=L to R-1 do

begin

if a1[i]

begin

//міняємо місцями елементи одновимірного масиву

x:=a1[i];

a1[i]:=a1[i+1];

a1[i+1]:=x;

//міняємо місцями перерізи тривимірного масиву

for j:=0 to sizeM-1 do

begin

for k:=0 to sizeP-1 do

begin

y:=ad[i, j, k];

ad[i, j, k]:=ad[i+1,j, k];

ad[i+1,j, k]:=y;

end

end;

b:=i;

end;

R:=b;

end;

//Зворотний прохід

for i:=R-1 downto L do

begin

if a1[i]

begin

//міняємо місцями елементи одновимірного масиву

x:=a1[i];

a1[i]:=a1[i+1];

a1[i+1]:=x;

//міняємо місцями перерізи тривимірного масиву

for j:=0 to sizeM-1 do

begin

for k:=0 to sizeP-1 do

begin

y:=ad[i, j, k];

ad[i, j, k]:=ad[i+1,j, k];

ad[i+1,j, k]:=y;

end

end;

b:=i;

end;

L:=b+1;

end;

end;

{==========

сортування для глобального масиву із підрахунком кількості операцій Сортує масив методом вибору так, як задано за варіантом із підрахунком кількості переміщень елементів}

procedure sortDynByInsertionCount (var ad: TArrayDyn; var pCount: int64; sizeN, sizeM, sizeP: integer);

var a1: TArray1D;

i, j, k, sum, b, c, l: integer;

begin

pCount:=0;

//створення одновимірного масиву із сум елементів кожного перерізу

for i:=0 to sizeN-1 do

begin

sum:=0;

for j:=0 to sizeM-1 do

begin

for k:=0 to sizeP-1 do

begin

sum:=sum+ad[i, j, k];

end;

end;

a1[i]:=sum;

end;

for i:=1 to sizeN-1 do

begin

c:=0;

b:=a1[i];

while a1[c]

begin

c:=c+1;

end;

if a1[c]=a1[i] then continue

else begin

for l:=i downto c+1 do

begin

a1[l]: =a1[l-1];

end;

a1[c]:=b;

for j:=0 to sizeM-1 do

begin

for k:=0 to sizeP-1 do

begin

b:=ad[i, j, k];

pCount:=pCount+1; //прирощуємо кількість переміщень

for l:=i downto c+1 do

begin

ad[l, j, k]: =ad[l-1,j, k];

pCount:=pCount+1; //прирощуємо кількість переміщень

end;

ad[c, j, k]: =b;

pCount:=pCount+1; //прирощуємо кількість переміщень

end;

end;

{=======

Сортує масив методом вибору так, як задано за варіантом із підрахунком кількості переміщень елементів}

procedure sortDynSelectionCount (var ad: TArrayDyn; var pCount: int64; sizeN, sizeM, sizeP: integer);

var a1: TArray1D;

i, j, k, sum, x, y, l, R:integer;

begin

pCount:=0;

//створення одновимірного масиву із сум елементів кожного перерізу

for i:=0 to sizeN-1 do

begin

sum:=0;

for j:=0 to sizeM-1 do

begin

for k:=0 to sizeP-1 do

begin

sum:=sum+ad[i, j, k];

end;

end;

a1[i]:=sum;

end;

R:=sizeN-1;

while R>0 do begin

l:=0;

begin

for i:=0 to R-1 do

begin

if a1[i]>a1[i+1] then

begin

x:=a1[i];

a1[i]:=a1[i+1];

a1[i+1]:=x;

for j:=0 to sizeM-1 do

begin

for k:=0 to sizeP-1 do

begin

y:=ad[i, j, k];

ad[i, j, k]:=ad[i+1,j, k];

ad[i+1,j, k]:=y;

pCount:=pCount+3 //прирощуємо кількість переміщень

end

end;

l:=i+1;

end;

end;

R:=l ;

end;

end;

end;

{=====

Сортує масив шейкерним методом так, як задано за варіантом із підрахунком кількості переміщень елементів}

procedure sortDynShakerCount (var ad: TArrayDyn; var pCount: int64; sizeN, sizeM, sizeP: integer);

var a1: TArray1D;

i, j, k, sum, x, y, L, R, b: integer;

begin

pCount:=0;

//створення одновимірного масиву із сум елементів кожного перерізу

for i:=0 to sizeN-1 do

begin

sum:=0;

for j:=0 to sizeM-1 do

begin

for k:=0 to sizeP-1 do

begin

sum:=sum+ad[i, j, k];

end;

end;

a1[i]:=sum;

end;

b:=0; L:=0;R:=sizeN-1;

while L

for i:=L to R-1 do

begin

if a1[i]>a1[i+1] then

begin

x:=a1[i];

a1[i]:=a1[i+1];

a1[i+1]:=x;

for j:=0 to sizeM-1 do

begin

for k:=0 to sizeP-1 do

begin

y:=ad[i, j, k];

ad[i, j, k]:=ad[i+1,j, k];

ad[i+1,j, k]:=y;

pCount:=pCount+3; //прирощуємо кількість переміщень

end

end;

b:=i;

end;

R:=b;

end;

for i:=R-1 downto L do

begin

if a1[i]>a1[i+1] then

begin

x:=a1[i];

a1[i]:=a1[i+1];

a1[i+1]:=x;

for j:=0 to sizeM-1 do

begin

for k:=0 to sizeP-1 do

begin

y:=ad[i, j, k];

ad[i, j, k]:=ad[i+1,j, k];

ad[i+1,j, k]:=y;

pCount:=pCount+3; //прирощуємо кількість переміщень

end

end;

b:=i;

end;

L:=b+1;

end;

end;

end;

end.

3.2 Час сортування

Час наведено у «тіках» процесору, він є відносним.

3.2.1 Масив 100×100×100

Табл. 4.1 — Час сортування для масиву 100×100×100

3.2.2 Масив 100х500х500

Табл. 4.2 — Час сортування для масиву 100×500×500

3.3 Кількість переміщень елементів

Масив 100×500×500

Табл. 4.3 — Кількість переміщень елементів для масиву 100×500×500

3.4 Порівняння часу сортування для різних геометричних розмірів одного й тогож масиву

3.4.1 Масив 100×250×1000

Табл. 4.4 — Час сортування для масиву 100×250×1000

3.4.2 Масив 100×500×2000

Табл. 4.5 — Час сортування для масиву 100×1000×250

4 Висновки за отриманим результатами

4.1 Порівняння результатів сортування для різних станів масивів

1. Сортування відбувається найшвидше коли стан масиву впорядкований.

2. Сортування відбувається найдовше коли масив впорядкований у зворотньому порядку (ніж задано за варіантом).

4.2 Порівняння методів сортування на невпорядкованому масиві

1. Найшвидше, масив був відсортований методом «Вибру».

2. На другому та третьому місці - «сортування вставкою» та «сортування шейкером» відповідно. Хоча відмінність у часі між «сортування вставкою» та «сортування шейкером» порівняно невелике.

4.3 Порівняння методів сортування на впорядкованому масиві

Результати тестів свідчать, що на впорядкованому масиві алгоритми спрацьовують практично миттєво. Це пов’язано з тим, що переміщень елементів не відбувається, а отже основні затрати часу, які є в наявності для інших станів масиву (невпорядкований та зворотно впорядкований) тут відсутні.

Теоретично кількість порівнянь у методу обміну та шейкерного є меншою, ніж у алгоритму сортування вставкою із лінійним пошуком місця вставки зліва, оскільки для перших двох алгоритмів достатньо одного проходу по масиву, та для кожного з елементів порівняти його з наступним, тобто здійснити (n-1) порівнянь, для алгоритму вставки із пошуком місця вставки від кінця відсортованої частини, тобто з правого боку, для кожного і-того елементу ми порівнювали б його з попереднім елементом і одразу бачимо, що і-тий елемент вже стоїть на своєму місці, а отже кількість порівнянь також (n-1)).

4.4 Порівняння методів сортування на зворотно впорядкованому масиві

Результати тестів свідчать, що найшвидше відсортовує алгоритм сортування «вибором». Потім ідуть «сортування вставкою» та «сортування шейкером» з відносно невеликою різницею (результати наведені в табл. 4.1 та 4.2).

4.5 Порівняння часу сортування для різних геометричних розмірів масиву

Результати тестів свідчать, що для різних геометричних розмірів масиву тривалість сортування суттєво не відрізняється. Основний час при сортуванні витрачається на переміщення перерізів, що відбувається через одну змінну, отже при однаковій кількості елементів у перерізі переміщення перерізу буде займати приблизно однаково часу.

Отже, геометричні розміри перерізу масиву суттєво не впливають на тривалість сортування для даної задачі.

4.6 Кількість переміщень елементів

Як і у попередніх тестах, найкращій результат показав алгоритм «сорування вибором» — кількість його переміщень найменша. «сортування вставкою» та «сортування шейкером» майже не відрізняються.

вибір лінійний шейкерний програма

Список використаної літератури

1. Вирт Н. Алгоритмы и структуры данных: Пер с англ. — М.: Мир, 1989.

2. http://www.cyberguru.ru/

3. МЕТОДИЧЕСКИЕ УКАЗАНИЯ к лабораторному практикуму и самостоятельной работе по дисциплине «Программирование» для студентов направления подготовки 0915 -«Компьютерная инженерия»