a few very useful Binary Sort routines

There are many places on internet for great help regarding many things.
Proper implementation of really fast routines for sorting data however is not common.
I am not claiming these routines to be the fastest around, but their ease of implementation and use may make them welcome.

As a thank you to this site for great help regarding some of my questions, I am now posting my own developed routines for making a sorted index of either Integers or Strings.
A binary sort routine is basically like what I have written. Coincidence may make the routines look like something previously developed by other people. This is however my own work, hence why I now choose to make them freely available through this site.

The implementation of this is easy.
All you need to do is :

2. Instead of creating a fixed array of Integer or a fixed array of Strings, you must make a dynamic array with either of the predefined types listed in this unit.

If you already have a list of 10.000 records of strings that you want sorted, then:
DynamicCreateIndex(StringArray,IndexArray);
Within not long at all you have an index of your data in rizing order.

Same with Integers:
DynamicCreateIndex(IntegerArray,IndexArray);

If you are entering new data one by one, then you do not need to sort everything every time.
SetLength(IntegerArray,0);
SetLength(IndexArray,0);

For every time you want to add an integer to the Integer Array use this routine:
DynamicExtendAndStore(IntegerArray,IndexArray,NewValue);
The IntegerArray and IndexArray is automatically extended and index is updated for just the one new value.

For strings, you use same approach:
DynamicExtendAndStore(StringArray,IndexArray,NewValue);

:icon_exclaim:
In order to make a full sort on arrays, the array can not contain empty records.
With this I just mean that you can not have an array of 6000 records and only sort the first 3700.
If doing so, then the remaining 2300 records will also be indexed.

If you have any problems with these routines, then please make a remark and I will try to help you out.
If you feel something is not explained well enough, then please make a remark.
If you like these routines, then please make a remark. That make me smile :-)

Best regards,
Morten Brendefur, Norway

``````unit BinarySort; // Quite helpful and lightning fast creating of sorted indexes of your data.

interface
TYPE
DynamicIntegerArray = ARRAY OF INTEGER;
DynamicStringArray = ARRAY OF STRING;
PROCEDURE DynamicCreateIndex(VAR ArrParam:DynamicStringArray; VAR ArrParamIndex: DynamicIntegerArray); OVERLOAD;
PROCEDURE DynamicExtendAndStore(VAR ArrParam,ArrParamIndex: DynamicIntegerArray; CONST NewValue:INTEGER); OVERLOAD;
PROCEDURE DynamicExtendAndStore(VAR ArrParam:DynamicStringArray; VAR ArrParamIndex: DynamicIntegerArray; CONST NewValue:STRING); OVERLOAD;

implementation
VAR
Lo, Mid, Hi : INTEGER; // Local variables for this unit only.

FUNCTION FindMid:INTEGER; {Indented routines are not interfaced. ie: Only a local procedure}
BEGIN
FindMid:=Lo+((Hi-Lo) DIV 2);
END;

PROCEDURE BinarySortIndex(VAR ArrParam,ArrParamIndex: DynamicIntegerArray; CONST HighBound:INTEGER); OVERLOAD;
VAR
x       : INTEGER;
TempVar : INTEGER;
BEGIN
Lo:=0; Hi:=HighBound; Mid:=FindMid;
TempVar := ArrParam[HighBound];
REPEAT
IF TempVar>ArrParam[ArrParamIndex[Mid]] THEN Lo:=Mid ELSE Hi:=Mid;
Mid:=FindMid;
UNTIL (Mid=Lo) OR (Mid=Hi);
IF TempVar>ArrParam[ArrParamIndex[Mid]] THEN INC(Mid);// We always need a last check just in case.
FOR x:=HighBound-1 DOWNTO Mid DO ArrParamIndex[x+1] := ArrParamIndex[x];// Shift the index.
ArrParamIndex[Mid]:=HighBound;// Store the pointer to index at its sorted place
END;
PROCEDURE BinarySortIndex(VAR ArrParam:DynamicStringArray; VAR ArrParamIndex: DynamicIntegerArray; CONST HighBound:INTEGER); OVERLOAD;
VAR
x       : INTEGER;
TempVar : STRING;
BEGIN
Lo:=0; Hi:=HighBound; Mid:=FindMid;
TempVar := ArrParam[HighBound];
REPEAT
IF TempVar>ArrParam[ArrParamIndex[Mid]] THEN Lo:=Mid ELSE Hi:=Mid;
Mid:=FindMid;
UNTIL (Mid=Lo) OR (Mid=Hi);
IF TempVar>ArrParam[ArrParamIndex[Mid]] THEN INC(Mid);// We always need a last check just in case.
FOR x:=HighBound-1 DOWNTO Mid DO ArrParamIndex[x+1] := ArrParamIndex[x];// Shift the index.
ArrParamIndex[Mid]:=HighBound;// Store the pointer to index at its sorted place
END;

PROCEDURE DynamicCreateIndex(VAR ArrParam,ArrParamIndex: DynamicIntegerArray);
VAR
x,TempLo,TempHi : INTEGER;
BEGIN
Templo:=0; TempHi:=HIGH(ArrParamIndex);
FOR x:=TempLo TO TempHi DO BinarySortIndex(ArrParam,ArrParamIndex,x);
END;
PROCEDURE DynamicCreateIndex(VAR ArrParam:DynamicStringArray; VAR ArrParamIndex: DynamicIntegerArray);
VAR
x,TempLo,TempHi : INTEGER;
BEGIN
Templo:=0; TempHi:=HIGH(ArrParamIndex);
FOR x:=TempLo TO TempHi DO BinarySortIndex(ArrParam,ArrParamIndex,x);
END;

PROCEDURE DynamicExtendAndStore(VAR ArrParam,ArrParamIndex: DynamicIntegerArray; CONST NewValue:INTEGER);
VAR ArrSize:INTEGER;
BEGIN
ArrSize:=HIGH(ArrParam)+1;
SetLength(ArrParam,ArrSize+1);
SetLength(ArrParamIndex,ArrSize+1);
ArrParam[ArrSize]:=NewValue;
BinarySortIndex(ArrParam,ArrParamIndex,ArrSize);
END;
PROCEDURE DynamicExtendAndStore(VAR ArrParam:DynamicStringArray; VAR ArrParamIndex: DynamicIntegerArray; CONST NewValue:STRING);
VAR ArrSize:INTEGER;
BEGIN
ArrSize:=HIGH(ArrParam)+1;
SetLength(ArrParam,ArrSize+1);
SetLength(ArrParamIndex,ArrSize+1);
ArrParam[ArrSize]:=NewValue;
BinarySortIndex(ArrParam,ArrParamIndex,ArrSize);
END;
end.``````
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.