Interface

Begin

Begin

Begin

Begin

Begin

Begin

Begin

Begin

Begin

Begin

Implementation

Interface

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

Finalization

Initialization

Except

Finally

Repeat

Try

Try

Begin

Var

Finally

Try

Begin

Var

TF: TextFile;

i: LongWord;

AssignFile(TF, FileName);

ReWrite(TF);

for i:=0 to List.Count-1 do

Writeln(TF, LongWord(List.Items[i]^));

CloseFile(TF);

end;

end;

{ Чтение содержимого выборки из текстового файла и инициализация массива }

function OpenList(FileName: string; var Size: LongWord): Boolean;

TF: TextFile;

pw: ^LongWord;

Size:=0;

Result:=True;

AssignFile(TF, FileName);

Reset(TF);

New(pw);

Readln(TF, pw^);

List.Add(pw);

until Eof(TF);

CloseFile(TF);

Size:=List.Count;

end;

Result:=False;

end;

end;

List:=TList.Create;

DisposeList;

end.

Модуль содержит реализации различных алгоритмов поиска по критерию отсортированных и неотсортированных объектов в списковом объекте класса TList. Все приведенные алгоритмы были рассмотрены в главе 4 и не требуют дополнительных пояснений.

unit srch;

uses Classes, Common;

{ Алгоритмы поиска }

function LineNonSortedSearch(aList: TList;

aItem: Pointer; aCompare: TCompareFunc): Integer;

function LineSortedSearch(aList: TList;

aItem: Pointer; aCompare: TCompareFunc): Integer;

function BinarySearch(aList: TList;

aItem: Pointer; aCompare: TCompareFunc): Integer;

function BinaryRecurSearch(aList: TList;

aItem: Pointer; L,R: Integer; aCompare: TCompareFunc): Integer;

{ Линейный поиск в неотсортированном массиве }

function LineNonSortedSearch;

var i: Integer;

Result:=-1;

for i:=0 to aList.Count-1 do

if aCompare(aList.List[i],aItem) = 0 then

Result:=i;

Break;

end;

end;

{ Линейный поиск в отсортированном массивом }

function LineSortedSearch;

var i, CompareResult: Integer;

Result:=-1;

{ Искать первый элемент, больший или равный искомому }

for i:=0 to aList.Count-1 do

CompareResult:=aCompare(aList.List[i], aItem);

if CompareResult >= 0 then

if CompareResult = 0 then

Result:=i else

Result:=-1;

Exit;

end;

end;

end;

{ Двоичный поиск }

function BinarySearch;

var L, R, M, CompareResult: Integer;

{ Значения индексов первого и последнего элементов }

L:=0; R:=aList.Count-1;

while L <= R do

{ Индекс среднего элемента }

M:=(L + R) div 2;

{ Сравнить значение среднего элемента с искомым }

CompareResult:=aCompare(aList.List[M], aItem);

{ Если значение среднего элемента меньше искомого -

переместить левый индекс на позицию до среднего индекса }

if CompareResult < 0 then

L:=M+1 else

{ Если значение среднего элемента больше искомого -

переместить правый индекс на позицию после среднего индекса }

if CompareResult > 0 then

R:=M-1 else

Result:=M;

Exit;

end;

end;

Result:=-1;

end;

{ Рекурсивный алгоритм двоичного поиска }

function BinaryRecurSearch;

var i, CompareResult: Integer;

{ Проверка ширины интервала }

if L > R then

Result:=-1 else

i:=(L + R) div 2;

CompareResult:=aCompare(aList.List[i], aItem);

{ Ключ найден, возврат индекса }

if CompareResult = 0 then

Result:=i else

if CompareResult = -1 then

{ Поиск в правом подинтервале }

Result:=BinaryRecurSearch(aList,aItem,i+1,R,aCompare) else

{ Поиск в левом подинтервале }

Result:=BinaryRecurSearch(aList,aItem,L,i-1,aCompare);

end;

end;

end.

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

unit sort;

uses Classes, Common;

{ Медленные алгоритмы сортировки }

procedure InsertionStdSort(aList, bList: TList; aCompare: TCompareFunc);

procedure InsertionBublSort(aList: TList;

aFirst, aLast: Integer; aCompare: TCompareFunc);

procedure InsertionOptSort(aList: TList;

aFirst, aLast: Integer; aCompare: TCompareFunc);

procedure SelectionStdSort(aList, bList: TList; aCompare: TCompareFunc);

procedure SelectionSort(aList: TList;

aFirst, aLast: Integer; aCompare: TCompareFunc);

procedure BubbleSort(aList: TList;

aFirst, aLast: Integer; aCompare: TCompareFunc);

procedure ShakerSort(aList: TList;

aFirst, aLast: Integer; aCompare: TCompareFunc);

{ Быстрые алгоритмы сортировки }

procedure ShellSort(aList: TList; aCompare: TCompareFunc);

procedure ShellKnuthSort(aList: TList;

aFirst, aLast: Integer; aCompare: TCompareFunc);

{ Самые быстрые алгоритмы сортировки }

procedure QuickHoarStd1Sort(aList: TList;

aFirst, aLast: Integer; aCompare: TCompareFunc);

procedure QuickHoarStd2Sort(aList: TList;

aFirst, aLast: Integer; aCompare: TCompareFunc);

procedure QuickHoarRNDSort(aList: TList;

aFirst, aLast: Integer; aCompare: TCompareFunc);

procedure QuickHoarMDNSort(aList: TList;

aFirst, aLast: Integer; aCompare: TCompareFunc);

procedure QuickHoarNonRecursiveSort(aList: TList;

aFirst, aLast: Integer; aCompare: TCompareFunc);

procedure MSS(aList: TList; aFirst, aLast: Integer;

aCompare: TCompareFunc; aTempList: PPointerList);

procedure DigitSort(aList: TList);

Дата добавления: 2014-01-07