Class TPCharSort (unit mwPCharSort)

Inherits from

TObject

Constructors


constructor create;

TPCharSort


Functions

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);


Properties

property Capacity : Integer


property Count : Integer


property Items : PChar


property Length : Integer


property Origin : PChar


property Position : Integer


property Token : PChar


Events

Variables

fCapacity : Integer;


FCount : Integer;


fOrigin : PChar;


FSorArray : PPCharArray;


SwapArray : PPCharArray;


TempArray : PPCharArray;



Constructors


constructor create;

TPCharSort


Functions


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);


Properties


property Capacity : Integer


property Count : Integer


property Items : PChar


property Length : Integer


property Origin : PChar


property Position : Integer


property Token : PChar


Events


Variables


fCapacity : Integer;


FCount : Integer;


fOrigin : PChar;


FSorArray : PPCharArray;


SwapArray : PPCharArray;


TempArray : PPCharArray;