Размещено на http://www.allbest.ru/

Программная реализация и сравнительный анализ сортировок, основанных на идее включения

Содержание

Введение

Постановка задачи

Теоретические сведения

Программная реализация и вычислительный эксперимент

Модуль Sortedlist

Модуль mainwindow

Модуль diagram

Вид главного окна программы

Вычислительный эксперимент

Заключение

Литература

Введение

В программировании часто возникает вопрос, связанный с переразмещением элементов (данных) в возрастающем или убывающем порядке. Как известно, память ЭВМ представляет собой некоторую последовательность ячеек (элементов), необходимых для размещения данных. Поэтому тот порядок, в котором данные находятся в памяти, напрямую влияет на скорость и простоту алгоритмов, предназначенных для их обработки.

Сам механизм переразмещения данных называется сортировкой. Слово «сортировка» (sorting) определяется как «распределение, отбор по сортам; деление на категории, сорта, разряды», но в программировании традиционно используют это слово в более узком смысле, обозначая им сортировку предметов в возрастающем или убывающем порядке. Как уже было сказано выше, расположение данных в памяти ЭВМ существенно влияет на время работы программ. Поэтому во многих программах перед обработкой данные, каким - либо образом сортируют. Но применение сортировок полностью не решает проблему рационального использования времени, так как сама сортировка требует временных затрат. Поставщики вычислительных машин считают, что в среднем более 25% машинного времени систематически тратится на сортировку. Во многих вычислительных системах на нее уходит больше половины машинного времени. Из этой статистики следует, что:

1. Либо сортировка имеет много важных применений;

2. Либо ею часто пользуются без нужды;

3. Либо применяются, в основном, неэффективные алгоритмы сортировки.

Во всяком случае, ясно, что сортировка заслуживает серьезного изучения с точки зрения ее практического использования. Поэтому в данной работе будет приведен ряд модернизированных алгоритмов сортировок применительно к соответствующей структуре данных с оценкой их временной сложности.

Постановка задачи

Требуется модернизировать три алгоритма сортировок вставками (базовую, двухпутевую и Шелла) для последующего их применения к структуре данных типа односвязный линейный список (ОЛС), реализованный связной схемой хранения, с приведением их сравнительного анализа, а также таблицы и графика практической зависимости числа сравнений от количества элементов в ОЛС.

Теоретические сведения

Линейный список (ЛС) -- это конечная последовательность однотипных элементов (узлов). Количество элементов в последовательности называется длиной списка, причем длина в процессе работы программы может изменяться, поэтому ЛС - динамическая структура.

Над СД ЛС определены следующие основные операции:

1. Инициализация.

2. Включение элемента.

3. Исключение элемента.

4. Чтение текущего элемента.

5. Переход в начало списка.

6. Переход в конец списка.

7. Переход к следующему элементу.

8. Переход к i -му элементу.

9. Определение длины списка.

10. Уничтожение списка.

На абстрактном уровне ЛС представляет собой линейную структуру - последовательность.

На физическом уровне ЛС может быть реализован последовательной или связной схемой хранения. Располагаться ЛС может в статической или динамической памяти. ЛС, реализованный последовательной схемой хранения, называется последовательным линейным списком (ПЛС). ЛС, реализованный связной схемой хранения, называется связным линейным списком (СЛС). Для реализации ПЛС используется вспомогательная встроенная СД - массив, элементы которого могут быть элементами ПЛС. Доступ к элементам ПЛС - прямой. Для реализации СЛС используется множество связанных элементов типа “запись”, связь между которыми устанавливается с помощью поля-указателя. Элементы СЛС могут располагаться в массиве или в динамической памяти. СЛС подразделяются на односвязные линейные списки (ОЛС) и двусвязные линейные списки (ДЛС). В ОЛС каждый элемент состоит из информационного поля (поле данных) и одного поля-указателя, содержащего адрес следующего элемента. В ДЛС каждый элемент состоит из информационного поля и двух полей-указателей, одно из которых содержит адрес следующего элемента в списке, а другое - предыдущего. Реализуется ОЛС, как правило, с первым фиктивным элементом, поле данных которого не используется, а ДЛС - с первым и последним фиктивным элементом. Введение фиктивных элементов позволяет упростить реализацию некоторых операций над ЛС.

Временная сложность (ВС) алгоритма - это зависимость времени выполнения алгоритма от количества обрабатываемых входных данных. Здесь представляет интерес среднее и худшее время выполнения алгоритма. ВС можно установить с различной точностью. Наиболее точной оценкой является аналитическое выражение для функции: t=t(N), где t - время, N - количество входных данных (размерность). Данная функция называется функцией временной сложности (ФВС).

Например: t = 5N2 + 32N + 1. Такая оценка может быть сделана только для конкретной реализации алгоритма в конкретной вычислительной системе и не пригодна для оценки алгоритма. Для сравнения алгоритмов достаточно определить лишь порядок функции временной сложности t(N).

Две функции f1(N) и f2(N) -- одного порядка, если

Иначе это записывается в виде: f1(N)=О(f2(N)) (Читается " О большое ").

Порядок функции, заданной многочленом, определяется только тем членом, который растет быстрее других с увеличением N, причём коэффициент при нём не учитывается.

Для определения порядка функции ВС алгоритма достаточно найти зависимость числа выполнения того оператора от количества исходных данных, который выполняется в алгоритме чаще других.

Для оценки алгоритмов можно использовать функцию зависимости числа операций сравнения C=C(N) от количества обрабатываемых данных, т.к. функции t(N) и C(N) - функции одного порядка.

Сортировка - это процесс перестановки элементов данного множества в определенном порядке. Сортировка является идеальным примером огромного разнообразия алгоритмов, выполняющих одну и ту же задачу, многие из которых в некотором смысле являются оптимальными, а большинство имеет какие-либо преимущества по сравнению с остальными. Поэтому на примере сортировки убеждаются в необходимости проведения сравнительного анализа алгоритмов.

Формулировка задачи может быть записана следующим образом.

Если даны элементы а1, а2 ,…, аn, то сортировка означает перестановку этих элементов в массив ак1, ак2,…,акn, где при заданной функции упорядочения f справедливы отношения f(ак1)f(ак2) …f(акn). Обычно функция упорядочения f не вычисляется по какому-то специальному правилу, а является значением элемента.

Метод сортировки называется устойчивым, если относительный порядок элементов с одинаковыми значениями не меняется при сортировке; неустойчивым - в противном случае.

Методы сортировки, в зависимости от лежащего в их основе приема, можно разбить на три базовых класса:

сортировка вставками;

сортировка выбором;

сортировка обменом.

Алгоритм сортировки вставками:

1. Запоминаем элемент, подлежащий вставке.

2. Перебираем справа налево отсортированные элементы и сдвигаем каждый элемент вправо на одну позицию, пока не освободится место для вставляемого элемента.

3. Вставляем элемент на освободившееся место. Пункты 1-3 выполняем для всех элементов массива, кроме первого.

При поиске подходящего места для элемента x удобно чередовать сравнения и пересылки, т. е. как бы "просеивать"x, сравнивая его с очередным элементом m[j] и либо вставляя x, либо пересылая m[j] вправо. Просеивание может быть закончено при двух различных условиях:

1) найден элемент аi с ключом меньшим, чем ключ x,

2) достигнут левый конец готовой последовательности.

Анализ сортировки вставками:

Если первоначальный массив отсортирован, то на каждом просмотре делается только одно сравнение, так что эта сортировка имеет порядок O(N). Если массив первоначально отсортирован в обратном порядке, то данная сортировка имеет порядок O(N2), поскольку общее число сравнений равно

1+2+3+...+(N-2)+(N-1)=(N-1)*N/2, что составляет O(N2).

Чем ближе к отсортированному виду, тем более эффективной становится сортировка простыми вставками. Среднее число сравнений в сортировке простыми вставками также составляет O(N2).

Двухпутевые вставки:

Данный метод был предложен в начале 50-х годов. Здесь первый элемент помещается в середину области вывода, и место для последующих элементов освобождается при помощи сдвигов влево или вправо, туда, куда удобнее. Таким образом, удается сэкономить примерно половину времени работы по сравнению с простыми вставками за счет некоторого усложнения программы. Можно применять этот метод, используя не больше памяти, чем требуется для N записей.

Сортировка Шелла:

Сортировка Шелла - это улучшенный метод сортировки вставками. Был предложен Д.Л. Шеллом в 1959 г. Рассмотрим этот метод на примере.

При первом просмотре группируются и сортируются элементы, отстоящие друг от друга на 5 позиций: (Х1,Х6), (Х2,Х7), (Х3), (Х4), (Х5); при втором проходе -- элементы, отстоящие друг от друга на три позиции: (Х1,Х4,Х7), (Х2,Х5), (Х3,Х6); при третьем -- на 1 позицию.

Поскольку первый в сортировке Шелла используемый шаг является большим, отдельные подмассивы достаточно малы по отношению к исходному. Таким образом, сортировка включением над этими подмассивами работает достаточно быстро - O(N2) (эффективно при малом N). Сортировка каждого подмассива приводит к тому, что весь массив становиться ближе к отсортированному виду, что также делает эффективным использование сортировки включением. Так как массив становится более упорядоченным, то O(N) < порядок ФBC <O(N2).

Если некоторый массив частично отсортирован с использованием шага k, а затем сортируется частично с использованием шага j, то данный массив остается частично отсортированным по шагу k, т.е. последующие частичные сортировки не нарушают результата предыдущих сортировок. Следующий шаг отличается от предыдущего следующим образом: ht=1, hi+1<hi.

Анализ сортировки Шелла:

Анализ сортировки Шелла математически сложен. В случае правильного выбора шагов порядок ФВС будет выглядеть как O(N1.2). Д. Кнут предложил выбирать шаги из следующего ряда: 1, 4, 13, 40, 121, … , а вычислять их по следующей формуле: hk-1 = 3 hk +1; ht = 1; t = [log 3 N] - 1 (количество просмотров), где N - размерность исходного массива. Т.е. элементы должны быть взаимно простыми числами. Исходя из этого порядок сортировки может быть аппроксимирован величиной О(N(log 2 N)).

Программная реализация

программирование память алгоритм линейный список

Модуль SortedList:

Unit SortedList;

{************************************************}

INTERFACE

{************************************************}

Uses

Classes, SysUtils, Dialogs;

Const

Ok = 0;

NotMem = 1;

ListEnd = 2;

Empty = 3;

Type

BaseType = Integer;

PtrEl = ^Element;

Element = Record

Data: BaseType;

Next: PtrEl

end;

TSortEvent = procedure ( Sender: TObject; SName: String ) of Object;

TSortedList = Class(TObject)

Private

AOnChange: TNotifyEvent;

AOnSort: TSortEvent;

ACount: LongInt;

Error: Byte;

Procedure Changed;

Procedure Sorted ( SName: String );

Protected

Ptr, Start: PtrEl;

Published

Property OnChange: TNotifyEvent read AOnChange write AOnChange;

Property OnSort: TSortEvent read AOnSort write AOnSort;

Public

Constructor Create;

Procedure Put ( E: BaseType );

Procedure Get ( var E: BaseType );

Procedure MovePtr;

Procedure MoveTo ( Pos: Word );

Procedure BeginPtr;

Procedure EndPtr;

Function IsEnd: Boolean;

Function ReadData: BaseType;

Property IsError: Byte read Error;

Property Count: LongInt read ACount;

Function InsertSort: Word;

Function TwoWayInsSort: Word;

Function ShellSort: Word;

Procedure Reinit ( Mas: Array of BaseType; Size: Word );

Destructor Done;

end;

{************************************************}

IMPLEMENTATION

{************************************************}

Function TSortedList.ReadData;

begin

Result := Ptr^.Data

end;

{------------------------------------------------------------------------------}

Procedure TSortedList.Changed;

begin

if Assigned(OnChange) then OnChange(Self)

end;

{------------------------------------------------------------------------------}

Procedure TSortedList.Sorted;

begin

if Assigned(OnSort) then OnSort(Self, SName)

end;

{------------------------------------------------------------------------------}

Constructor TSortedList.Create;

var

P: PtrEl;

begin

try

New(P)

except

on EOutOfMemory do

begin

Error := NotMem;

Exit

end

end;

ACount := 0;

Error := Ok;

AOnChange := NIL;

AOnSort := NIL;

P^.Data := 666;

P^.Next := NIL;

Ptr := P;

Start := P

end;

{------------------------------------------------------------------------------}

Procedure TSortedList.Put;

var

P: PtrEl;

begin

try

New(P)

except

on EOutOfMemory do

begin

Error := NotMem;

Changed;

Exit

end

end;

Error := Ok;

P^.Data := E;

P^.Next := Ptr^.Next;

Ptr^.Next := P;

ACount := ACount + 1;

Changed

end;

{------------------------------------------------------------------------------}

Procedure TSortedList.Get;

var

P: Pointer;

begin

E := -333;

if ACount > 0 then

if Ptr^.Next <> NIL then

begin

Error := Ok;

E := Ptr^.Next^.Data;

P := Ptr^.Next^.Next;

Dispose(Ptr^.Next);

Ptr^.Next := P;

ACount := ACount - 1

end

else Error := ListEnd

else Error := Empty;

Changed

end;

{------------------------------------------------------------------------------}

Procedure TSortedList.MovePtr;

begin

Error := Ok;

if Ptr^.Next <> NIL then Ptr := Ptr^.Next

else Error := ListEnd;

Changed

end;

{------------------------------------------------------------------------------}

Procedure TSortedList.MoveTo;

var

i: Word;

begin

if Pos <= ACount then

begin

Error := Ok;

Ptr := Start^.Next;

for i := 2 to Pos do Ptr := Ptr^.Next

end

else Error := ListEnd;

Changed

end;

{------------------------------------------------------------------------------}

Procedure TSortedList.BeginPtr;

begin

Error := Ok;

Ptr := Start^.Next;

Changed

end;

{------------------------------------------------------------------------------}

Procedure TSortedList.EndPtr;

var

i: Word;

begin

Error := Ok;

Ptr := Start;

i := 1;

While (i <= ACount) and (Ptr^.Next <> NIL ) do

begin

Ptr := Ptr^.Next;

i := i + 1

end;

Changed

end;

{------------------------------------------------------------------------------}

Function TSortedList.IsEnd;

begin

Result := Ptr^.Next = NIL

end;

{------------------------------------------------------------------------------}

Function TSortedList.InsertSort;

var

CmpCnt, i: Word;

P: PtrEl;

Temp: Pointer;

F: Boolean;

begin

CmpCnt := 0;

P := Start^.Next;

for i := 2 to ACount do

begin

F := True;

Ptr := Start;

While Ptr <> P do

begin

CmpCnt := CmpCnt + 2;

if Ptr^.Next^.Data > P^.Next^.Data then

begin

Temp := P^.Next^.Next;

P^.Next^.Next := Ptr^.Next;

Ptr^.Next := P^.Next;

P^.Next := Temp;

F := False;

Break

end

else Ptr := Ptr^.Next

end;

if F then P := P^.Next;

CmpCnt := CmpCnt + 2;

end;

Sorted('После сортировки вставками:');

Result := CmpCnt

end;

{------------------------------------------------------------------------------}

Function TSortedList.TwoWayInsSort;

var

CmpCnt, i: Word;

S, P: PtrEl;

Temp: Pointer;

F: Boolean;

begin

CmpCnt := 0; ;

P := Start^.Next;

S := Start^.Next;

for i := 2 to ACount do

begin

CmpCnt := CmpCnt + 2;

if P^.Next^.Data < S^.Data then

begin

Ptr := Start;

While (Ptr^.Next <> S) and (Ptr^.Next^.Data <= P^.Next^.Data) do

begin

Ptr := Ptr^.Next;

CmpCnt := CmpCnt + 2

end;

Temp := P^.Next^.Next;

P^.Next^.Next := Ptr^.Next;

Ptr^.Next := P^.Next;

P^.Next := Temp

end

else

begin

Ptr := S;

F := True;

While Ptr <> P do

begin

if Ptr^.Next^.Data > P^.Next^.Data then

begin

Temp := P^.Next^.Next;

P^.Next^.Next := Ptr^.Next;

Ptr^.Next := P^.Next;

P^.Next := Temp;

F := False;

Break

end

else Ptr := Ptr^.Next;

CmpCnt := CmpCnt + 2

end;

if F then P := P^.Next;

CmpCnt := CmpCnt + 1

end

end;

Sorted('После двухпутевой сортировки:');

Result := CmpCnt

end;

{------------------------------------------------------------------------------}

Function TSortedList.ShellSort;

var

CmpCnt, k, l, t: Word;

i, j: LongInt;

ListMas: Array of PtrEl;

H: Array of Word;

P: PtrEl;

begin

SetLength(ListMas, ACount+1);

Ptr := Start;

for i := 0 to ACount do

begin

ListMas[i] := Ptr;

Ptr := Ptr^.Next

end;

t := trunc(ln(ACount) / ln(2)) - 1;

SetLength(H, t+1);

H[t] := 1;

for i := (t - 2) downto 0 do H[i] := 2 * H[i + 1] + 1;

CmpCnt := 0;

for l:= 0 to t do

begin

k := H[l];

CmpCnt := CmpCnt + 1;

for i := k + 1 to ACount do

begin

CmpCnt := CmpCnt + 1;

P := ListMas[i];

j := i - k;

while (j > 0) and (P^.Data < ListMas[j].Data) do

begin

ListMas[j + k] := ListMas[j];

j := j - k;

CmpCnt := CmpCnt + 2

end;

ListMas[j + k] := P;

end;

end;

Finalize(H);

Ptr := ListMas[0];

for i := 1 to ACount do

begin

Ptr^.Next := ListMas[i];

Ptr := Ptr^.Next

end;

Finalize(ListMas);

Sorted('После сортировки Шелла:');

Result := CmpCnt

end;

{------------------------------------------------------------------------------}

Procedure TSortedList.Reinit;

var

i: Word;

begin

if Size <= ACount then

begin

Ptr := Start^.Next;

for i := 0 to Size - 1 do

begin

Ptr^.Data := Mas[i];

Ptr := Ptr^.Next

end

end

else Error := ListEnd;

Changed

end;

{------------------------------------------------------------------------------}

Destructor TSortedList.Done;

var

P: Pointer;

i: Word;

begin

if ACount >= 0 then

begin

Error := Ok;

for i := 0 to ACount do

begin

P := Start^.Next;

Dispose(Start);

Start := P

end;

ACount := -1

end

else Error := Empty;

Changed

end;

{------------------------------------------------------------------------------}

end.

Модуль MainWindow:

unit MainWindow;

{************************************************}

INTERFACE

{************************************************}uses

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

Dialogs, ComCtrls, StdCtrls, Buttons, Grids, SortedList, Diagram,

ExtCtrls;

const

ELCOUNT = 100;

MAXPOSITIVE = 500;

MINNEGATIVE = 0;

type

TMyForm = class(TForm)

PageControl: TPageControl;

Init: TTabSheet;

View: TTabSheet;

Test: TTabSheet;

GroupBox1: TGroupBox;

Check: TCheckBox;

InitCaptions: TStringGrid;

bRunInit: TBitBtn;

GroupBox2: TGroupBox;

bBeginPtr: TBitBtn;

bEndPtr: TBitBtn;

bMovePtr: TBitBtn;

GroupBox3: TGroupBox;

ElemNum: TEdit;

bMoveTo: TBitBtn;

ListCaptions: TStringGrid;

bExit: TBitBtn;

bInfo: TBitBtn;

MyOutput: TMemo;

StaticText1: TStaticText;

GroupBox4: TGroupBox;

bBaseSort: TBitBtn;

b2WaySort: TBitBtn;

bShellSort: TBitBtn;

Statistic: TStringGrid;

bRunTest: TBitBtn;

bShowDiagram: TBitBtn;

StaticText2: TStaticText;

GroupBox5: TGroupBox;

InsDataEl: TEdit;

bPutElem: TBitBtn;

GroupBox6: TGroupBox;

DelDataEl: TEdit;

bDelElem: TBitBtn;

bShowData: TBitBtn;

OGroup: TRadioGroup;

bClrMyOutput: TBitBtn;

procedure FormCreate(Sender: TObject);

procedure CheckClick(Sender: TObject);

procedure FormDestroy(Sender: TObject);

procedure bRunInitClick(Sender: TObject);

procedure bPutElemClick(Sender: TObject);

procedure bDelElemClick(Sender: TObject);

procedure bBeginPtrClick(Sender: TObject);

procedure bEndPtrClick(Sender: TObject);

procedure bMovePtrClick(Sender: TObject);

procedure bMoveToClick(Sender: TObject);

procedure bInfoClick(Sender: TObject);

procedure bExitClick(Sender: TObject);

procedure bShowDataClick(Sender: TObject);

procedure bShowDiagramClick(Sender: TObject);

procedure bBaseSortClick(Sender: TObject);

procedure b2WaySortClick(Sender: TObject);

procedure bRunTestClick(Sender: TObject);

procedure bShellSortClick(Sender: TObject);

procedure bClrMyOutputClick(Sender: TObject);

private

List1: TSortedList;

List2: TSortedList;

List3: TSortedList;

MyList: TSortedList;

Flag, CheckFlag: Boolean;

procedure ListChange(Sender: TObject);

procedure ListSort(Sender: TObject; SName: String);

procedure CopyList(FromL: TSortedList; var ToL: TSortedList);

procedure PtrElEnabled;

procedure PtrElDisabled;

end;

var

MyForm: TMyForm;

{************************************************}

IMPLEMENTATION

{************************************************}

{$R *.dfm}

procedure TMyForm.FormCreate(Sender: TObject);

begin

MyList := TSortedList.Create;

MyList.OnChange := ListChange;

MyList.OnSort := ListSort;

Flag := False;

CheckFlag := False;

InitCaptions.Enabled := False;

bRunInit.Enabled := False;

bBeginPtr.Enabled := False;

bEndPtr.Enabled := False;

bMovePtr.Enabled := False;

ElemNum.Enabled := False;

bMoveTo.Enabled := False;

bBaseSort.Enabled := False;

b2WaySort.Enabled := False;

bShellSort.Enabled := False;

Statistic.Enabled := False;

bShowDiagram.Enabled := False;

DelDataEl.Enabled := False;

bDelElem.Enabled := False;

bShowData.Enabled := False;

bClrMyOutput.Enabled := False;

With InitCaptions do

begin

Cells[0, 0] := ' Свойство';

Cells[1, 0] := ' Значение';

Cells[0, 1] := ' Кол-во элементов';

Cells[0, 2] := ' MAX положительное';

Cells[0, 3] := ' MIN отрицательное';

Cells[1, 1] := IntToStr(ELCOUNT);

Cells[1, 2] := IntToStr(MAXPOSITIVE);

Cells[1, 3] := IntToStr(MINNEGATIVE)

end;

With ListCaptions do

begin

Cells[0, 0] := ' Свойство';

Cells[1, 0] := ' Значение';

Cells[0, 1] := 'Count';

Cells[0, 2] := 'Ptr^.Data';

Cells[0, 3] := 'Error';

Cells[1, 1] := '0'

end;

With Statistic do

begin

Cells[0, 0] := ' Кол-во эл-тов';

Cells[0, 1] := ' 5';

Cells[0, 2] := ' 10';

Cells[0, 3] := ' 15';

Cells[0, 4] := ' 20';

Cells[0, 5] := ' 25';

Cells[0, 6] := ' 30';

Cells[0, 7] := ' 35';

Cells[0, 8] := ' 40';

Cells[0, 9] := ' 45';

Cells[1, 0] := ' Базовая';

Cells[2, 0] := ' Двухпутевая';

Cells[3, 0] := ' Шелла'

end

end;

{------------------------------------------------------------------------------}

procedure TMyForm.PtrElEnabled;

begin

if not Flag then

begin

bBeginPtr.Enabled := True;

bEndPtr.Enabled := True;

bMovePtr.Enabled := True;

ElemNum.Enabled := True;

bMoveTo.Enabled := True;

DelDataEl.Enabled := True;

bDelElem.Enabled := True;

bBaseSort.Enabled := True;

b2WaySort.Enabled := True;

bShellSort.Enabled := True

end

end;

{------------------------------------------------------------------------------}

procedure TMyForm.PtrElDisabled;

begin

if Flag then

begin

bBeginPtr.Enabled := False;

bEndPtr.Enabled := False;

bMovePtr.Enabled := False;

ElemNum.Enabled := False;

bMoveTo.Enabled := False;

DelDataEl.Enabled := False;

bDelElem.Enabled := False;

bBaseSort.Enabled := False;

b2WaySort.Enabled := False;

bShellSort.Enabled := False

end

end;

{------------------------------------------------------------------------------}

procedure TMyForm.ListChange;

begin

if MyList.Count > 0 then

With ListCaptions do

begin

Cells[1, 1] := IntToStr(MyList.Count);

Cells[1, 2] := IntToStr(MyList.ReadData);

Case MyList.IsError of

Ok: Cells[1, 3] := 'Ok';

NotMem: Cells[1, 3] := 'NotMem';

ListEnd: Cells[1, 3] := 'ListEnd';

Empty: Cells[1, 3] := 'Empty'

end

end;

if MyList.Count > 1 then

begin

PtrElEnabled;

Flag := True

end

else

begin

PtrElDisabled;

Flag := False

end

end;

{------------------------------------------------------------------------------}

procedure TMyForm.ListSort;

var

S: String;

i: Word;

begin

S := '';

With List1 do

begin

BeginPtr;

for i := 0 to Count-1 do

begin

S := Concat(S, IntToStr(ReadData), ' ');

MovePtr

end

end;

MyOutput.Lines.Append(SName);

MyOutput.Lines.Append(S)

end;

{------------------------------------------------------------------------------}

procedure TMyForm.CheckClick(Sender: TObject);

begin

if Check.Checked then

begin

InitCaptions.Enabled := True;

bRunInit.Enabled := True;

InsDataEl.Enabled := False;

bPutElem.Enabled := False

end

else

begin

InitCaptions.Enabled := False;

bRunInit.Enabled := False;

InsDataEl.Enabled := True;

bPutElem.Enabled := True

end

end;

{------------------------------------------------------------------------------}

procedure TMyForm.FormDestroy(Sender: TObject);

begin

MyList.Free

end;

{------------------------------------------------------------------------------}

procedure TMyForm.bRunInitClick(Sender: TObject);

var

MaxPos, MinNeg: Integer;

C: LongInt;

begin

With InitCaptions do

begin

try

C := StrToInt(Cells[1, 1])

except

on EConvertError do

begin

MessageDlg('Вводимое число должно быть целым!', mtError, [mbOk], 0);

Cells[1, 1] := IntToStr(ELCOUNT);

Exit

end

end;

if C < 0 then

begin

MessageDlg('Вводимое число должно быть положительным!', mtError, [mbOk], 0);

Cells[1, 1] := IntToStr(ELCOUNT);

Exit

end;

try

MaxPos := StrToInt(Cells[1, 2])

except

on EConvertError do

begin

MessageDlg('Вводимое число должно быть целым!', mtError, [mbOk], 0);

Cells[1, 2] := IntToStr(MAXPOSITIVE);

Exit

end

end;

try

MinNeg := StrToInt(Cells[1, 3])

except

on EConvertError do

begin

MessageDlg('Вводимое число должно быть целым!', mtError, [mbOk], 0);

Cells[1, 3] := IntToStr(MINNEGATIVE);

Exit

end

end

end;

Randomize;

While C > 0 do

begin

MyList.Put(Random(MaxPos) - MinNeg);

MyList.MovePtr;

C := C - 1

end;

if not bShowData.Enabled then bShowData.Enabled := True;

if not bClrMyOutput.Enabled then bClrMyOutput.Enabled := True;

InsDataEl.Enabled := True;

bPutElem.Enabled := True;

Check.Enabled := False;

InitCaptions.Enabled := False;

bRunInit.Enabled := False

end;

{------------------------------------------------------------------------------}

procedure TMyForm.bPutElemClick(Sender: TObject);

var

E: Integer;

begin

if Check.Enabled then Check.Enabled := False;

try

E := StrToInt(InsDataEl.Text)

except

on EConvertError do

begin

MessageDlg('Вводимое число должно быть целым!', mtError, [mbOk], 0);

InsDataEl.Text := '0';

Exit

end

end;

MyList.Put(E);

if not bShowData.Enabled then bShowData.Enabled := True;

if not bClrMyOutput.Enabled then bClrMyOutput.Enabled := True;

MyOutput.Clear

end;

{------------------------------------------------------------------------------}

procedure TMyForm.bDelElemClick(Sender: TObject);

var

E: Integer;

begin

MyList.Get(E);

DelDataEl.Text := IntToStr(E);

MyOutput.Clear

end;

{------------------------------------------------------------------------------}

procedure TMyForm.bBeginPtrClick(Sender: TObject);

begin

MyList.BeginPtr

end;

{------------------------------------------------------------------------------}

procedure TMyForm.bEndPtrClick(Sender: TObject);

begin

MyList.EndPtr

end;

{------------------------------------------------------------------------------}

procedure TMyForm.bMovePtrClick(Sender: TObject);

begin

MyList.MovePtr

end;

{------------------------------------------------------------------------------}

procedure TMyForm.bMoveToClick(Sender: TObject);

var

Pos: LongInt;

begin

try

Pos := StrToInt(ElemNum.Text)

except

on EConvertError do

begin

MessageDlg('Вводимое число должно быть целым!', mtError, [mbOk], 0);

ElemNum.Text := '0';

Exit

end

end;

if Pos > 0 then MyList.MoveTo(Pos)

else

begin

MessageDlg('Вводимое число должно быть больше нуля!', mtError, [mbOk], 0);

ElemNum.Text := '1'

end

end;

{------------------------------------------------------------------------------}

procedure TMyForm.bInfoClick(Sender: TObject);

begin

Application.MessageBox('Выполнил Лубенский Александр, гр. ПВ-21. ', ' Информация', MB_ICONINFORMATION)

end;

{------------------------------------------------------------------------------}

procedure TMyForm.bExitClick(Sender: TObject);

begin

Application.Terminate

end;

{------------------------------------------------------------------------------}

procedure TMyForm.bShowDataClick(Sender: TObject);

var

S: String;

i: Word;

begin

S := '';

With MyList do

begin

BeginPtr;

for i := 0 to Count-1 do

begin

S := Concat(S, IntToStr(ReadData), ' ');

MovePtr

end

end;

MyOutput.Lines.Append('До сортировки:');

MyOutput.Lines.Append(S)

end;

{------------------------------------------------------------------------------}

procedure TMyForm.bShowDiagramClick(Sender: TObject);

begin

MyForm.Left := 562;

MyForm.Top := 115;

Form1.Left := 1;

Form1.Top := 63;

Form1.Visible := True

end;

{------------------------------------------------------------------------------}

procedure TMyForm.bBaseSortClick(Sender: TObject);

begin

List1 := TSortedList.Create;

List1.OnSort := ListSort;

CopyList(MyList, List1);

List1.InsertSort;

List1.Free

end;

{------------------------------------------------------------------------------}

procedure TMyForm.b2WaySortClick(Sender: TObject);

begin

List1 := TSortedList.Create;

List1.OnSort := ListSort;

CopyList(MyList, List1);

List1.TwoWayInsSort;

List1.Free

end;

{------------------------------------------------------------------------------}

procedure TMyForm.CopyList;

var

i: Word;

begin

FromL.BeginPtr;

for i := 1 to FromL.Count do

begin

ToL.Put(FromL.ReadData);

ToL.MovePtr;

FromL.MovePtr

end

end;

{------------------------------------------------------------------------------}

procedure TMyForm.bRunTestClick(Sender: TObject);

const

MAXCNT = 45;

DIAP = 100;

var

Mas: Array of BaseType;

D: BaseType;

CmpCnt, K: Word;

i, j: LongInt;

begin

Form1.DataClear;

SetLength(Mas, MAXCNT);

List1 := TSortedList.Create;

List2 := TSortedList.Create;

List3 := TSortedList.Create;

Case OGroup.ItemIndex of

0: begin

Randomize;

for i := 0 to MAXCNT - 1 do Mas[i] := Random(DIAP)

end;

1: for i := 0 to MAXCNT - 1 do Mas[i] := i + 1;

2: for i := 0 to MAXCNT - 1 do Mas[i] := MAXCNT - i

end;

i := 5; K := 1;

While i <= MAXCNT do

begin

for j := i - 5 to i - 1 do

begin

D := Mas[j];

List1.Put(D);

List1.MovePtr;

List2.Put(D);

List2.MovePtr;

List3.Put(D);

List3.MovePtr

end;

CmpCnt := List1.InsertSort;

Form1.ChartInit(0, i, CmpCnt);

Statistic.Cells[1, K] := IntToStr(CmpCnt);

List1.Reinit(Mas, i);

List1.EndPtr;

CmpCnt := List2.TwoWayInsSort;

Form1.ChartInit(2, i, CmpCnt);

Statistic.Cells[2, K] := IntToStr(CmpCnt);

List2.Reinit(Mas, i);

List2.EndPtr;

CmpCnt := List3.ShellSort;

Form1.ChartInit(1, i, CmpCnt);

Statistic.Cells[3, K] := IntToStr(CmpCnt);

List3.Reinit(Mas, i);

List3.EndPtr;

i := i + 5;

K := K + 1

end;

List1.Free;

List2.Free;

List3.Free;

Finalize(Mas);

bShowDiagram.Enabled := True

end;

{------------------------------------------------------------------------------}

procedure TMyForm.bShellSortClick(Sender: TObject);

begin

List1 := TSortedList.Create;

List1.OnSort := ListSort;

CopyList(MyList, List1);

List1.ShellSort;

List1.Free

end;

{------------------------------------------------------------------------------}

procedure TMyForm.bClrMyOutputClick(Sender: TObject);

begin

MyOutput.Clear

end;

{------------------------------------------------------------------------------}

end.

Модуль Diagram:

unit Diagram;

{************************************************}

INTERFACE

{************************************************}uses

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

Dialogs, ExtCtrls, TeeProcs, TeEngine, Chart, Series;

type

TForm1 = class(TForm)

MyChart: TChart;

Series1: TBarSeries;

Series2: TBarSeries;

Series3: TBarSeries;

public

Procedure ChartInit ( Index: Byte; X, Y: Word );

Procedure DataClear;

end;

var

Form1: TForm1;

{************************************************}

IMPLEMENTATION

{************************************************}

{$R *.dfm}

Procedure TForm1.ChartInit;

begin

MyChart.SeriesList[Index].AddXY(X, Y)

end;

{------------------------------------------------------------------------------}

Procedure TForm1.DataClear;

begin

MyChart.SeriesList[0].Clear;

MyChart.SeriesList[1].Clear;

MyChart.SeriesList[2].Clear

end;

{------------------------------------------------------------------------------}

end.

Вычислительный эксперимент

Упорядоченный массив

Сортировка	Количество элементов в массиве
	5	10	15	20	25	30	35	40	45
Базовая	28	108	238	418	648	928	1258	1638	2068
Двухпутевая	24	99	224	399	624	899	1224	1599	2024
Шелла	11	31	46	79	99	119	168	193	218

Массив, упорядоченный в обратном порядке

Сортировка	Количество элементов в массиве
	5	10	15	20	25	30	35	40	45
Базовая	16	36	56	76	96	116	136	156	176
Двухпутевая	8	18	28	38	48	58	68	78	88
Шелла	31	121	256	207	299	449	378	441	530



Неупорядоченный массив

Сортировка	Количество элементов в массиве
	5	10	15	20	25	30	35	40	45
Базовая	22	68	158	278	392	582	764	1000	1218
Двухпутевая	12	38	79	127	178	253	352	472	579
Шелла	21	83	148	171	241	301	334	401	492

Заключение

В данном проекте были произведены исследования базовой сортировки вставками и двух ее модернизаций: двухпутевой сортировки и сортировки Шелла, применительно к структуре данных типа ОЛС. Из приведенных выше таблиц зависимости количества сравнений от количества элементов в ОЛС видно, что базовая сортировка является наиболее неэффективной, так как с увеличением числа элементов в ОЛС количество сравнений стремительно растет. В худшем случае, когда элементы ОЛС отсортированы по возрастанию, количество сравнений в ней пропорционально N2. В двухпутевой сортировке дело обстоит немного лучше. При сортировке ею произвольно упорядоченного ОЛС, а также ОЛС упорядоченного по убыванию, она в два раза эффективнее базовой. Но на ОЛС, упорядоченном по возрастанию его элементов, она дает почти такой же результат, как и базовая. Поэтому в худшем случае количество сравнений также пропорционально N2. Что касается сортировки Шелла, то она является относительно « ровной » сортировкой. Это означает, что количество элементов в ОЛС почти не влияет на количество сравнений, то есть она эффективна как на ОЛС с малым количеством элементов, так и на ОЛС с относительно большим числом элементов. Все вышеуказанное дает сортировке Шелла преимущество по отношению к базовой и двухпутевой сортировкам. Но все же есть одно « но ». При сортировке ОЛС, элементы которого расположены в убывающем порядке, она показывает худшие результаты относительно базовой и двухпутевой сортировок.

В заключение, хотелось бы дать некоторую рекомендацию по использованию вышеуказанных сортировок:

1. Если количество элементов в ОЛС относительно мало и элементы в ОЛС располагаются в произвольном порядке, лучше использовать базовую, либо двухпутевую сортировку.

2. Если количество элементов в ОЛС велико и элементы в ОЛС располагаются в произвольном порядке, то для сортировки лучше всего подойдет сортировка Шелла.

Эти рекомендации всего лишь помогут рациональнее использовать время работы программы, но не в коей мере не предписывают строго им следовать, так как выбор того или иного метода сортировки полностью ложится на плечи программиста.

Список литературы

1. Кнут Д. «Искусство программирования» 3 том «Поиск и сортировка»;

2. Ахо А. «Структуры данных и алгоритмы»;

3. Кормен Т. «Алгоритмы: построение и анализ»;

4. Вирт Н. «Алгоритмы + структуры данных = программы»

5. Сведения из всемирной компьютерной сети Internet.

Размещено на Allbest.ru