Class TPCharSort (unit mwPCharSort) |
Inherits from
TObject
constructor create;
- TPCharSort
function Add(Item: PChar):Integer;
procedure Clear;
procedure CombSortW(SorCompare: TPCHarSortCompare);
Driver for the " Comb " routine.
destructor Destroy;
procedure MergeSort(SorCompare: TPCharSortCompare);
Non-recursive Mergesort.
procedure Pack;
procedure QuickSort(SorCompare: TPCHarSortCompare);
Based on a non-recursive QuickSort from the SWAG-Archive.
procedure Tokenize(OriginPtr: PChar; StartCapacity: Integer);
function GetItems(Index: Integer):PChar;
procedure SetItems(Index: Integer; Item: PChar);
function Comb(jumpsize0: Integer; SorCompare: TPCHarSortCompare): boolean;
Multipication by 0.
procedure Expand;
function GetLength(Index: Integer):Integer;
function GetPosition(Index: Integer):Integer;
function GetToken(Index: Integer):PChar;
procedure Merge(PosA, PosB, PosLastA, PosLastB: LongInt; SorCompare: TPCharSortCompare);
Unfortunately the " Merge " routine needs additional memory
An Algorithm to perform merging in linear time without extra space
is described in:
B.
procedure SetCapacity(NewCapacity:Integer);
property Capacity : Integer
property Count : Integer
property Items : PChar
property Length : Integer
property Origin : PChar
property Position : Integer
property Token : PChar
fCapacity : Integer;
FCount : Integer;
fOrigin : PChar;
FSorArray : PPCharArray;
SwapArray : PPCharArray;
TempArray : PPCharArray;
constructor create;
TPCharSort
function Add(Item: PChar):Integer;
procedure Clear;
procedure CombSortW(SorCompare: TPCHarSortCompare);
Driver for the " Comb " routine.
Based on routines from the SWAG-Archive.
Very fast, for a smaller number of items with large keys
" Comb " may outperform Quicksort.
( Only a few thousends
destructor Destroy;
procedure MergeSort(SorCompare: TPCharSortCompare);
Non-recursive Mergesort.
Very fast, if enough memory available.
The number of comparisions used is nearly optimal, about 3/4 of QuickSort.
If comparision plays a very more important role than exchangement,
it outperforms QuickSort in any case.
( Large keys or a time intensive comparision like AnsiCompareText )
From all Algoritms with O(N lg N) it's the only stable, meaning it lefts
equal keys in the order of input. This may be important in some cases.
procedure Pack;
procedure QuickSort(SorCompare: TPCHarSortCompare);
Based on a non-recursive QuickSort from the SWAG-Archive.
( TV Sorting Unit by Brad Williams )
procedure Tokenize(OriginPtr: PChar; StartCapacity: Integer);
function GetItems(Index: Integer):PChar;
procedure SetItems(Index: Integer; Item: PChar);
function Comb(jumpsize0: Integer; SorCompare: TPCHarSortCompare): boolean;
Multipication by 0.76 gives a slightly better result than
division by 1.3.
Because of the FOR loop it runs faster on arrays starting with one
procedure Expand;
function GetLength(Index: Integer):Integer;
function GetPosition(Index: Integer):Integer;
function GetToken(Index: Integer):PChar;
procedure Merge(PosA, PosB, PosLastA, PosLastB: LongInt; SorCompare: TPCharSortCompare);
Unfortunately the " Merge " routine needs additional memory
An Algorithm to perform merging in linear time without extra space
is described in:
B. Huang and M. Langston, " Practical In-place Merging ",
Communications of the ACM 31(1988), 348-352.
procedure SetCapacity(NewCapacity:Integer);
property Capacity : Integer
property Count : Integer
property Items : PChar
property Length : Integer
property Origin : PChar
property Position : Integer
property Token : PChar
fCapacity : Integer;
FCount : Integer;
fOrigin : PChar;
FSorArray : PPCharArray;
SwapArray : PPCharArray;
TempArray : PPCharArray;