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

 

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

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

Факультет прикладної математики

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

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

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

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

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

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

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

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

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

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

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

Варіант №ЗадачаМетодиСпособи обходуСтан масиву371, 3, 7---------------1, 2, 3

Задача

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

Методи

1. Вибір.

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

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

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 i := 1 to count - 1 do

begin j := i + 1 to count do

if a[j] > a[i] then

begin:= a[i];[i] := a[j];[j] := x;

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 i := 2 to count do

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

// впорядкованими та невпорядкованими частинами масиву a[i] < a[i-1] then

begin

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

x := a[i];

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

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

repeat

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

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

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

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

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

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

a[j] := x;

end;;;

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

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

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

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

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

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

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

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

unit unitSort3D;, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,,StdCtrls,UnitDop,sort3DArrayDop;D = class(TForm): TLabel;: TLabel;: TMemo;: TEdit;: TButton;: TMemo;: TEdit;: TEdit;: TButton;: TButton;: TButton;: TGroupBox;: TLabel;: TLabel;: TLabel;: TGroupBox;: TLabel;: TLabel;: TLabel;FormCreate(Sender: TObject);btnCreateTestArraysClick(Sender: TObject);btnLaunchSortClick(Sender: TObject);btnCompareSortingbyOperationsClick(Sender: TObject);btnCalculateForAlternateSizeClick(Sender: TObject);

{ Private declarations }

{ Public declarations };D: TfrmSort3D;,ad1,ad2,ad3:TArrayDyn;

{$R *.dfm}TfrmSort3D.FormCreate(Sender: TObject);.Text:='100';.Text:='100';.Text:='100';;TfrmSort3D.btnCreateTestArraysClick(Sender: TObject);,j,k,sizeN,sizeM,sizeP: integer;

//Очистити поле результатів.clear;.clear;:=StrToInt(edtSizeN.Text);:=StrToInt(edtSizeM.Text);:=StrToInt(edtSizeP.Text);(ad,sizeN,sizeM,sizeP);(ad1,sizeN,sizeM,sizeP);;i :=0 to sizeN-1 doj :=0 to sizeM-1 dok:=0 to sizeP-1 do[i,j,k]:=Random(100);[i,j,k]:= ad[i,j,k];;.Lines.Append('Масив ' +InttoStr(SizeN)+'x' +InttoStr(SizeM)+'x' +InttoStr(SizeP)+ ' створено');(sizeN<5) and (sizeM<5) and (sizeP<5) then(ad,sizeN,sizeM,sizeP,memSortDetails);(ad1,sizeN,sizeM,sizeP,memSortDetails);;;TfrmSort3D.btnLaunchSortClick(Sender: TObject);sizeN,sizeM,sizeP: integer;

//Зчитати розмір масиву:=StrToInt(edtSizeN.Text);:=StrToInt(edtSizeM.Text);:=StrToInt(edtSizeP.Text);

//запускаємо процедуру сортування та виведення масиву(ad,ad1,sizeN,sizeM,sizeP,memSortResults,memSortDetails);TfrmSort3D.btnCompareSortingbyOperationsClick(Sender: TObject);i,j,k,sizeN,sizeM,sizeP: integer;,pCountSelection,pCountShaker:int64;

//Зчитати розмір масиву:=StrToInt(edtSizeN.Text);:=StrToInt(edtSizeM.Text);:=StrToInt(edtSizeP.Text);

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

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

+InttoStr(sizeN) + 'x'+InttoStr(sizeM)+'x'+InttoStr(sizeP));.Lines.Append('Вставка |Обмін| Шейкер');:=0;:=0;:=0;

//зчитати масив ad1 з adi:=0 to sizeN-1 doj:=0 to sizeM-1 dok:=0 to sizeP-1 do[i,j,k]:=ad[i,j,k];

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

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

//Сортувати невпорядкований масив вставкою із підрахунком кількості переміщень(ad1,pCountByInsertion,sizeN,sizeM,sizeP);

//зчитати масив ad1 з adi:=0 to sizeN-1 doj:=0 to sizeM-1 dok:=0 to sizeP-1 do[i,j,k]:=ad[i,j,k];

//Сортувати невпорядкований масив вибором із підрахунком кількості переміщень(ad1,pCountSelection,sizeN,sizeM,sizeP);

//зчитати масив ad1 з adi:=0 to sizeN-1 doj:=0 to sizeM-1 dok:=0 to sizeP-1 do[i,j,k]:=ad[i,j,k];

//Сортувати невпорядкований масив шейкером із підрахунком кількості переміщень(ad1,pCountShaker,sizeN,sizeM,sizeP);.Lines.Append('----Переміщень для випадкового масиву-------');.Lines.Append(format(' %1.4d %1.4d %1.4d ',

[pCountByInsertion,pCountSelection,pCountShaker]));:=0;:=0;:=0;

//Сортувати впорядкований масив вставкою із підрахунком кількості переміщень(ad1,pCountByInsertion,sizeN,sizeM,sizeP);

//Сортувати впорядкований масив вибором із підрахунком кількості переміщень(ad1,pCountSelection,sizeN,sizeM,sizeP);

//Сортувати впорядкований масив шейкером із підрахунком кількості переміщень(ad1,pCountShaker,sizeN,sizeM,sizeP);.Lines.Append('----Переміщень для відсортованого масиву-------');.Lines.Append(format(' %1.4d %1.4d %1.4d ',

[pCountByInsertion,pCountSelection,pCountShaker]));:=0;:=0;:=0;

//Сортувати зворотно впорядкований масив вставкою із підрахунком кількості переміщень(ad1,sizeN,sizeM,sizeP);(ad1,pCountByInsertion,sizeN,sizeM,sizeP);

//Сортувати зворотно впорядкований масив вибором із підрахунком кількості переміщень(ad1,sizeN,sizeM,sizeP);(ad1,pCountSelection,sizeN,sizeM,sizeP);

//Сортувати зворотно впорядкований масив шейкером із підрахунком кількості переміщень(ad1,sizeN,sizeM,sizeP);(ad1,pCountShaker,sizeN,sizeM,sizeP);.Lines.Append('--Переміщень для зворотно відсортованого масиву----');.Lines.Append(format(' %1.4d %1.4d %1.4d ',

[pCountByInsertion,pCountSelection,pCountShaker]));;TfrmSort3D.btnCalculateForAlternateSizeClick(Sender: TObject);sizeN,sizeM,sizeP,,sizeMad2,sizePad2,,j,k,j_ad2,k_ad2:integer;

//зчитати розмір масиву:=StrToInt(edtSizeN.Text);:=StrToInt(edtSizeM.Text);:=StrToInt(edtSizeP.Text);

//задати довжину для масивів:=sizeN;:=sizeM div 2;:=sizeP*2;(ad2,sizeNad2,sizeMad2,sizePad2);(ad3,sizeNad2,sizeMad2,sizePad2);

//зчитати массив з ad в ad2 и ad3 з урахуванням зміни геометричних розмірів перерізуi:=0 to sizeN-1 do_ad2:=0;j:=0 to sizeM-1 doj mod 2 = 0k_ad2:=0k_ad2:=sizeP;k:=0 to sizeP-1 do[i,j_ad2,k_ad2]:=ad[i,j,k];[i,j_ad2,k_ad2]:=ad[i,j,k];_ad2:=k_ad2+1;;j mod 2 = 1j_ad2:=j_ad2+1;;;.Lines.Append('Масив набув нових геометричних розмірів:'+(sizeNad2)+ 'x'+ IntToStr(sizeMad2)+'x' +IntToStr(sizePad2) );

//Якщо масив невеликий, відображаємо його(sizeNad2<11) and (sizeMad2 <11) and (sizePad2<11) then.Lines.Append('Новий масив:'+ IntToStr(sizeNad2)+ 'x'+(sizeMad2)+'x' +IntToStr(sizePad2) );(ad2,sizeNad2,sizeMad2,sizePad2,memSortDetails);;

//запускаємо процедуру сортування та виведення масиву(ad2,ad3,sizeNad2,sizeMad2,sizePad2,memSortResults,memSortDetails);

//задать длину для массивов:=sizeN;:=sizeM*2;:=sizeP div 2;(ad2,sizeNad2,sizeMad2,sizePad2);(ad3,sizeNad2,sizeMad2,sizePad2);

//зчитати массив з ad в ad2 и ad3 з урахуванням зміни геометричних розмірів перерізуi:=0 to sizeN-1 do_ad2:=0;j:=0 to sizeM-1 do_ad2:=0;k:=0 to sizeP-1 do[i,j_ad2,k_ad2]:=ad[i,j,k];[i,j_ad2,k_ad2]:=ad[i,j,k];

//if row ended atart from next rowk=sizePad2-1j_ad2:=j_ad2+1;_ad2:=0;_ad2:=k_ad2+1;;_ad2:=j_ad2+1;;.Lines.Append('Масив набув нових геометричних розмірів:'+(sizeNad2)+ 'x'+ IntToStr(sizeMad2)+'x' +IntToStr(sizePad2) );

//Якщо масив невеликий, відображаємо його(sizeNad2<50) and (sizeMad2 <50) and (sizePad2<50) then.Lines.Append('Новый массив:'+ IntToStr(sizeNad2)+ 'x'+(sizeMad2)+'x' +IntToStr(sizePad2) );(ad2,sizeNad2,sizeMad2,sizePad2,memSortDetails);;

//запускаємо процедуру сортування та виведення масиву(ad2,ad3,sizeNad2,sizeMad2,sizePad2,memSortResults,memSortDetails);.

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

sort3DArrayDop;, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,, StdCtrls;D = Array[0..1000000] of integer;= Array of Array of Array of integer;showArrayDyninMemo(a: TArrayDyn;sizeN,sizeM,sizeP: integer;m: Tmemo);sortArrayAndShowResultsInMemo(a,a1: TArrayDyn;sizeN,sizeM,sizeP: integer;memSortResults,memSortDetails: Tmemo);sortDynByInsertion(var ad:TArrayDyn; sizeN,sizeM,sizeP: integer);sortDynByInsertionReverse(var ad:TArrayDyn; sizeN,sizeM,sizeP: integer);sortDynSelection(var ad:TArrayDyn; sizeN,sizeM,sizeP: integer);sortDynSelectionReverse(var ad:TArrayDyn; sizeN,sizeM,sizeP: integer);sortDynShaker(var ad:TArrayDyn; sizeN,sizeM,sizeP: integer);sortDynShakerReverse(var ad:TArrayDyn; sizeN,sizeM,sizeP: integer);sortDynByInsertionCount(var ad:TArrayDyn; var pCount:int64; sizeN,sizeM,sizeP: integer);sortDynSelectionCount(var ad:TArrayDyn; var pCount:int64; sizeN,sizeM,sizeP: integer);sortDynShakerCount(var ad:TArrayDyn; var pCount:int64; sizeN,sizeM,sizeP: integer);showArrayDyninMemo(a: TArrayDyn;sizeN,sizeM,sizeP: integer;m: Tmemo);i,j,k: integer;: string;i:=0 to sizeN-1 do.lines.append(IntToStr(i));j:=0 to sizeM-1 do:=inttostr(a[i,j,0]);k:=1 to sizeP-1 do:=str+' ' + IntToStr(a[i,j,k]);.lines.append(str);;;;sortArrayAndShowResultsInMemo(a,a1: TArrayDyn;sizeN,sizeM,sizeP: integer;memSortResults,memSortDetails: Tmemo);i,j,k,t1,t2,t,tSumInsertRandom,tSumInsertSorted,tSumInsertSortedReverse,,tSumSelectionSorted,tSumSelectionSortedReverse,,tSumShakerSorted,tSumShakerSortedReverse:integer;

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

Заголовок результатів}.Lines.Append('Результати сортування массиву' +InttoStr(sizeN) + 'x'+InttoStr(sizeM)+'x'+InttoStr(sizeP));.Lines.Append('Невпорядкований|Впорядкований|Зворотно впорядкований');:=0;:=0;:=0;:=0;:=0;:=0;:=0;:=0;:=0;

//зчитати масив a1 з ai:=0 to sizeN-1 doj:=0 to sizeM-1 dok:=0 to sizeP-1 do[i,j,k]:=a[i,j,k];(sizeN<=10) and (sizeM<=10) and (sizeP<=10)begin.Lines.append('Вихідний невпорядкований масив для сортування вибором');(a1,sizeN,sizeM,sizeP,memSortDetails);.Lines.append('');;

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

Сортувати випадковий масив вибором}:=GetTickCount;(a1,sizeN,sizeM,sizeP);:=GetTickCount;:=t2-t1;:=tSumSelectionRandom+t;(sizeN<=10) and (sizeM<=10) and (sizeP<=10)begin.Lines.append('Відсортований неупорядкований масив для сортування вибором');(a1,sizeN,sizeM,sizeP,memSortDetails);.Lines.append('');;

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

сортувати впорядкований масив вибором}:=GetTickCount;(a1,sizeN,sizeM,sizeP);:=GetTickCount;:=t2-t1;:=tSumSelectionSorted+t;(sizeN<=10) and (sizeM<=10) and (sizeP<=10)begin.Lines.append('Впорядкований впорядкований масив для сортування вибором');(a1,sizeN,sizeM,sizeP,memSortDetails);.Lines.append('');;

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

Сортувати зворотно впрорядкований масив вибором}(a1,sizeN,sizeM,sizeP);(sizeN<=10) and (sizeM<=10) and (sizeP<=10)begin.Lines.append('Вихідний зворотно впорядкований масив для сортування вибором');(a1,sizeN,sizeM,sizeP,memSortDetails);.Lines.append('');;:=GetTickCount;(a1,sizeN,sizeM,sizeP);:=GetTickCount;:=t2-t1;:=tSumSelectionSortedReverse+t;(sizeN<=10) and (sizeM<=10) and (sizeP<=10)begin.Lines.append('Впорядкований зворотно впорядкований масив для сортування вибором');(a1,sizeN,sizeM,sizeP,memSortDetails);.Lines.append('');;

//зчитуємо масив ad1 з adi:=0 to sizeN-1 doj:=0 to sizeM-1 dok:=0 to sizeP-1 do[i,j,k]:=a[i,j,k];(sizeN<=10) and (sizeM<=10) and (sizeP<=10)begin.Lines.append('Вихідний невпорядкований масив для сортування шейкером');(a1,sizeN,sizeM,sizeP,memSortDetails);.Lines.append('');;

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

сортувати невпорядкований масив шейкером}:=GetTickCount;(a1,sizeN,sizeM,sizeP);:=GetTickCount;:=t2-t1;:=tSumShakerRandom+t;(sizeN<=10) and (sizeM<=10) and (sizeP<=10)begin.Lines.append('Впорядкований неупорядовкований масив для сортування шейкером');(a1,sizeN,sizeM,sizeP,memSortDetails);.Lines.append('');;

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

сортувати впорядкований масив шейкером}:=GetTickCount;(a1,sizeN,sizeM,sizeP);:=GetTickCount;:=t2-t1;:=tSumShakerSorted+t;(sizeN<=10) and (sizeM<=10) and (sizeP<=10)begin.Lines.append('Впорядкований впорядкований масив для сортування шейкером');(a1,sizeN,sizeM,sizeP,memSortDetails);.Lines.append('');;

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

сортувати зворотно впорядкований масив шейкером}(a1,sizeN,sizeM,sizeP);(sizeN<=10) and (sizeM<=10) and (sizeP<=10)begin.Lines.append('Вихідний зворотно впорядкований масив для сортування шейкером');(a1,sizeN,sizeM,sizeP,memSortDetails);.Lines.append('');;:=GetTickCount;(a1,sizeN,sizeM,sizeP);:=GetTickCount;:=t2-t1;:=tSumShakerSortedReverse+t;(sizeN<=10) and (sizeM<=10) and (sizeP<=10)begin.Lines.append('Впорядкований зворотно впорядкований масив для сортування вибором');(a1,sizeN,sizeM,sizeP,memSortDetails);.Lines.append('');;

//зчитати масив ad1 з adi:=0 to sizeN-1 doj:=0 to sizeM-1 dok:=0 to sizeP-1 do[i,j,k]:=a[i,j,k];(sizeN<=10) and (sizeM<=10) and (sizeP<=10)begin.Lines.append('Вихідний невпорядкований масив для сортування вставкою');(a1,sizeN,sizeM,sizeP,memSortDetails);.Lines.append('');;

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

сортувати невпорядкований масив вставкою}:=GetTickCount;(a1,sizeN,sizeM,sizeP);:=GetTickCount;:=t2-t1;:=tSumInsertRandom+t;(sizeN<=10) and (sizeM<=10) and (sizeP<=10)begin.Lines.append('Відсортований невпорядкований масив для сортування вставкою');(a1,sizeN,sizeM,sizeP,memSortDetails);.Lines.append('');;

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

сортувати впорядкований масив вставкою}:=GetTickCount;(a1,sizeN,sizeM,sizeP);:=GetTickCount;:=t2-t1;:=tSumInsertSorted+t;(sizeN<=10) and (sizeM<=10) and (sizeP<=10)begin.Lines.append('Відсортований упорядкований масив для сортування вставкою');(a1,sizeN,sizeM,sizeP,memSortDetails);.Lines.append('');;

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

сортувати зворотно впорядкований масив вставкою}(a1,sizeN,sizeM,sizeP);(sizeN<=10) and (sizeM<=10) and (sizeP<=10)begin.Lines.append('Вихідний зворотно впорядкований масив для сортування вставкою');(a1,sizeN,sizeM,sizeP,memSortDetails);.Lines.append('');;:=GetTickCount;(a1,sizeN,sizeM,sizeP);:=GetTickCount;:=t2-t1;:=tSumInsertSortedReverse+t;(sizeN<=10) and (sizeM<=10) and (sizeP<=10)begin.Lines.append('Впорядкований зворотно впорядкований масив для сортування вставкою');(a1,sizeN,sizeM,sizeP,memSortDetails);.Lines.append('');;.Lines.Append('----дані по сортуванню вставкою-------');.Lines.Append(format(' %1.4d %1.4d %1.4d ',

[tSumInsertRandom,tSumInsertSorted,tSumInsertSortedReverse]));.Lines.Append('----дані по сортуванню вибором-------');.Lines.Append(format(' %1.4d %1.4d %1.4d ',

[tSumSelectionRandom, tSumSelectionSorted, tSumSelection Sorted Reverse]));.Lines.Append('----дані по сортуванню шейкром-------');.Lines.Append(format(' %1.4d %1.4d %1.4d ',

[tSumShakerRandom,tSumShakerSorted,tSumShakerSortedReverse]));;

{=====

сортування вставкою перерезів за НЕспаданням сум їх елементів}sortDynByInsertion(var ad:TArrayDyn; sizeN,sizeM,sizeP: integer);a1: TArray1D;,j,k,sum,b,c,l:integer;

//створення одновимірного масиву із сум елементів кожного перерізуi:=0 to sizeN-1 do:=0;j:=0 to sizeM-1 dok:=0 to sizeP-1 do:=sum+ad[i,j,k];;;[i]:=sum;;

//пошук місця вставкиi:=1 to sizeN-1 do:=0;:=a1[i];a1[c]<b do:=c+1;;a1[c]=a1[i] then continuebegin

//зсув елементів одновимірного масивуl:=i downto c+1 do[l]:=a1[l-1];;

//вставка на місце, що звільнилося[c]:=b;

//зсув елементів тривімирного масиву і вставка на місце, що звільнилосяj:=0 to sizeM-1 dok:=0 to sizeP-1 do:=ad[i,j,k];l:=i downto c+1 do[l,j,k]:=ad[l-1,j,k];;[c,j,k]:=b;;;;;

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

сортування вставкою перерізів за НЕзростанням суми їх елементів}sortDynByInsertionReverse(var ad:TArrayDyn; sizeN,sizeM,sizeP: integer);a1: TArray1D;,j,k,sum,b,c,l:integer;

//створення одновимірного масиву із сум елементів кожного перерізуi:=0 to sizeN-1 do:=0;j:=0 to sizeM-1 dok:=0 to sizeP-1 do:=sum+ad[i,j,k];;;[i]:=sum;;

//пошук місця вставкиi:=1 to sizeN-1 do:=0;:=a1[i];a1[c]>b do:=c+1;;a1[c]=a1[i] then continuebegin

//зсув елементів одновимірного масивуl:=i downto c+1 do[l]:=a1[l-1];;

//вставка на місце, що звільнилося[c]:=b;

//зсув елементів тривімирного масиву і вставка на місце, що звільнилосяj:=0 to sizeM-1 dok:=0 to sizeP-1 do:=ad[i,j,k];l:=i downto c+1 do[l,j,k]:=ad[l-1,j,k];;[c,j,k]:=b;;;;;;

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

Сортування вибором із запам'ятовуванням місця останньої перестановки перерізів за НЕспаданням суми їх елементів}sortDynSelection(var ad:TArrayDyn; sizeN,sizeM,sizeP: integer);a1:TArray1D;,j,k,sum,x,y,l:integer;

//створення одновимірного масиву із сум елементів кожного перерізуi:=0 to sizeN-1 do:=0;j:=0 to sizeM-1 dok:=0 to sizeP-1 do:=sum+ad[i,j,k];;;[i]:=sum;;

// процедура сортування методом виборуl:=i+1 to sizeN doa1[l]>a1[i] then

//міняємо місцями елементи одновимірного масиву:=a1[i];[i]:=a1[l];[l]:=x;

//міняємо місцями перерізи тривимірного масивуj:=0 to sizeM-1 dok:=0 to sizeP-1 do:=ad[i,j,k];[i,j,k]:=ad[i+1,j,k];[i+1,j,k]:=y;

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

Сортування вибором із запам'ятовуванням місця останньої перестановки перерізів за НЕзростанням суми їх елементів}sortDynSelectionReverse(var ad:TArrayDyn; sizeN,sizeM,sizeP: integer);a1:TArray1D;,j,k,sum,x,y,l,R:integer;

//створення одновимірного масиву із сум елементів кожного перерізуi:=0 to sizeN-1 do:=0;j:=0 to sizeM-1 dok:=0 to sizeP-1 do:=sum+ad[i,j,k];;;[i]:=sum;;

// процедура сортування методом виборуl:=i+1 to sizeN doa1[l]<a1[i] then

//міняємо місцями елементи одновимірного масиву:=a1[i];[i]:=a1[l];[l]:=x;

//міняємо місцями перерізи тривимірного масивуj:=0 to sizeM-1 dok:=0 to sizeP-1 do:=ad[i,j,k];[i,j,k]:=ad[i+1,j,k];[i+1,j,k]:=y;;

{=======

Сортування шейкером перерізів за НЕзростанням суми їх елементів}sortDynShaker(var ad:TArrayDyn; sizeN,sizeM,sizeP: integer);a1: TArray1D;,j,k,sum,x,y,L,R,b:integer;

//створення одновимірного масиву із сум елементів кожного перерізуi:=0 to sizeN-1 do:=0;j:=0 to sizeM-1 dok:=0 to sizeP-1 do:=sum+ad[i,j,k];;;[i]:=sum;;

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

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

//R - права границя невідсортованої частини:=0; L:=0;R:=sizeN-1;L<R do begini:=L to R-1 doa1[i]>a1[i+1] then //якщо порядок розташування сусідніх елементів порушено

//міняємо місцями елементи одновимірного масиву:=a1[i];[i]:=a1[i+1];[i+1]:=x;

//міняємо місцями перерізи тривимірного масивуj:=0 to sizeM-1 dok:=0 to sizeP-1 do:=ad[i,j,k];[i,j,k]:=ad[i+1,j,k];[i+1,j,k]:=y;;:=i;;:=b;;

//Зворотний прохідi:=R-1 downto L doa1[i]>a1[i+1] then //якщо порядок розташування сусідніх елементів порушено

//міняємо місцями елементи одновимірного масиву:=a1[i];[i]:=a1[i+1];[i+1]:=x;

//міняємо місцями перерізи тривимірного масивуj:=0 to sizeM-1 dok:=0 to sizeP-1 do:=ad[i,j,k];[i,j,k]:=ad[i+1,j,k];[i+1,j,k]:=y;;:=i;;:=b+1;;;;

{========

Сортування шейкером перерізів за НЕспаданням суми їх елементів}sortDynShakerReverse(var ad:TArrayDyn; sizeN,sizeM,sizeP: integer);a1: TArray1D;,j,k,sum,x,y,L,R,b:integer;

//створення одновимірного масиву із сум елементів кожного перерізуi:=0 to sizeN-1 do:=0;j:=0 to sizeM-1 dok:=0 to sizeP-1 do:=sum+ad[i,j,k];;;[i]:=sum;;

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

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

//R - права границя невідсортованої частини:=0; L:=0;R:=sizeN-1;L<R do begini:=L to R-1 doa1[i]<a1[i+1] then //якщо порядок розташування сусідніх елементів порушено

//міняємо місцями елементи одновимірного масиву:=a1[i];[i]:=a1[i+1];[i+1]:=x;

//міняємо місцями перерізи тривимірного масивуj:=0 to sizeM-1 dok:=0 to sizeP-1 do:=ad[i,j,k];[i,j,k]:=ad[i+1,j,k];[i+1,j,k]:=y;;:=i;;:=b;;

//Зворотний прохідi:=R-1 downto L doa1[i]<a1[i+1] then //якщо порядок розташування сусідніх елементів порушено

//міняємо місцями елементи одновимірного масиву:=a1[i];[i]:=a1[i+1];[i+1]:=x;

//міняємо місцями перерізи тривимірного масивуj:=0 to sizeM-1 dok:=0 to sizeP-1 do:=ad[i,j,k];[i,j,k]:=ad[i+1,j,k];[i+1,j,k]:=y;;:=i;;:=b+1;;;

{==========

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

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

sortDynByInsertionCount(var ad:TArrayDyn; var pCount:int64; sizeN,sizeM,sizeP: integer);a1: TArray1D;,j,k,sum,b,c,l:integer;:=0;

//створення одновимірного масиву із сум елементів кожного перерізуi:=0 to sizeN-1 do:=0;j:=0 to sizeM-1 dok:=0 to sizeP-1 do:=sum+ad[i,j,k];;;[i]:=sum;;i:=1 to sizeN-1 do:=0;:=a1[i];a1[c]<b do:=c+1;;a1[c]=a1[i] then continuebeginl:=i downto c+1 do[l]:=a1[l-1];;[c]:=b;j:=0 to sizeM-1 dok:=0 to sizeP-1 do:=ad[i,j,k];:=pCount+1; //прирощуємо кількість переміщеньl:=i downto c+1 do[l,j,k]:=ad[l-1,j,k];:=pCount+1; //прирощуємо кількість переміщень;[c,j,k]:=b;:=pCount+1; //прирощуємо кількість переміщень;;

{=======

Сортує масив методом вибору так, як задано за варіантом із підрахунком кількості переміщень елементів}sortDynSelectionCount(var ad:TArrayDyn; var pCount:int64; sizeN,sizeM,sizeP: integer);a1:TArray1D;,j,k,sum,x,y,l,R:integer;:=0;

//створення одновимірного масиву із сум елементів кожного перерізуi:=0 to sizeN-1 do:=0;j:=0 to sizeM-1 dok:=0 to sizeP-1 do:=sum+ad[i,j,k];;;[i]:=sum;;:=sizeN-1;R>0 do begin:=0;i:=0 to R-1 doa1[i]>a1[i+1] then:=a1[i];[i]:=a1[i+1];[i+1]:=x;j:=0 to sizeM-1 dok:=0 to sizeP-1 do:=ad[i,j,k];[i,j,k]:=ad[i+1,j,k];[i+1,j,k]:=y;:=pCount+3 //прирощуємо кількість переміщень;:=i+1;;;:=l ;;;;

{=====

Сортує масив шейкерним методом так, як задано за варіантом із підрахунком кількості переміщень елементів}sortDynShakerCount(var ad:TArrayDyn; var pCount:int64; sizeN,sizeM,sizeP: integer);a1: TArray1D;,j,k,sum,x,y,L,R,b:integer;:=0;

//створення одновимірного масиву із сум елементів кожного перерізуi:=0 to sizeN-1 do:=0;j:=0 to sizeM-1 dok:=0 to sizeP-1 do:=sum+ad[i,j,k];;;[i]:=sum;;:=0; L:=0;R:=sizeN-1;L<R do begini:=L to R-1 doa1[i]>a1[i+1] then:=a1[i];[i]:=a1[i+1];[i+1]:=x;j:=0 to sizeM-1 dok:=0 to sizeP-1 do:=ad[i,j,k];[i,j,k]:=ad[i+1,j,k];[i+1,j,k]:=y;:=pCount+3; //прирощуємо кількість переміщень;:=i;;:=b;;i:=R-1 downto L doa1[i]>a1[i+1] then:=a1[i];[i]:=a1[i+1];[i+1]:=x;j:=0 to sizeM-1 dok:=0 to sizeP-1 do:=ad[i,j,k];[i,j,k]:=ad[i+1,j,k];[i+1,j,k]:=y;:=pCount+3; //прирощуємо кількість переміщень;:=i;;:=b+1;;;;.

.2 Час сортування

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

3.2.1Масив 100х100х100

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

НевпорядкованийВпорядкованийЗворотно впорядкованийДані по сортуванню вставкою014100313Сортування вибором001600000Шейкерне сортування025000547

3.2.2Масив 100х500х500

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

НевпорядкованийВпорядкованийЗворотно впорядкованийДані по сортуванню вставкою5500 012297 Сортування вибором0 0093 00094 Шейкерне сортування6938 014672 3.3 Кількість переміщень елементів

Масив 100х500х500

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

НевпорядкованийВпорядкованийЗворотно впорядкованийДані по сортуванню вставкою649500000 01287000000 Сортування вибором1806000000 03712500000 Шейкерне сортування1806000000 03712500000

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

3.4.1 Масив 100х250х1000

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

НевпорядкованийВпорядкованийЗворотно впорядкованийДані по сортуванню вставкою5453 011485 Сортування вибором0094 00094 Шейкерне сортування6922 014187

3.4.2 Масив 100х500х2000

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

НевпорядкованийВпорядкованийЗворотно впорядкованийДані по сортуванню вставкою6672 014250 Сортування вибором0109 00093 Шейкерне сортування7000 014110 4.Висновки за отриманим результатами

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Больше работ по теме: