Варіант №
|
Задача
|
Методи
|
Способи обходу
|
Стан масиву
|
3
|
7
|
1, 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-го
елементу
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 ;;;;
{=====
//створення одновимірного масиву із сум елементів кожного
перерізу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
|
Невпорядкований
|
Впорядкований
|
Зворотно
впорядкований
|
Дані по сортуванню
вставкою
|
0141
|
0
|
0313
|
Сортування вибором
|
0016
|
0
|
0000
|
Шейкерне сортування
|
0250
|
0
|
0547
|
3.2.2 Масив 100х500х500
Табл. 4.2
- Час сортування для масиву 100х500х500
|
Невпорядкований
|
Впорядкований
|
Зворотно
впорядкований
|
Дані по сортуванню
вставкою
|
5500
|
0
|
12297
|
Сортування вибором
|
0 0093
|
0
|
0094
|
Шейкерне сортування
|
6938
|
0
|
14672
|
3.3
Кількість переміщень елементів
Масив
100х500х500
Табл. 4.3 - Кількість переміщень елементів для
масиву 100х500х500
|
Невпорядкований
|
Впорядкований
|
Зворотно
впорядкований
|
Дані по сортуванню
вставкою
|
649500000
|
0
|
1287000000
|
Сортування вибором
|
1806000000
|
0
|
3712500000
|
Шейкерне сортування
|
1806000000
|
0
|
3712500000
|
.4
Порівняння часу сортування для різних геометричних розмірів одного й тогож
масиву
3.4.1 Масив 100х250х1000
Табл. 4.4 - Час сортування для масиву 100х250х1000
|
Невпорядкований
|
Впорядкований
|
Зворотно
впорядкований
|
Дані по сортуванню
вставкою
|
5453
|
0
|
11485
|
Сортування вибором
|
0094
|
0
|
0094
|
Шейкерне сортування
|
6922
|
0
|
14187
|
3.4.2 Масив 100х500х2000
Табл. 4.5 - Час сортування для масиву 100х1000х250