a few very useful Binary Sort routines

By Morten Brendefu on Dec 12th, 2011 10:30 pm

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 :add the unit to the USES clause in your form/unit.
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.
Just start your code with:
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,ArrParamIndex: DynamicIntegerArray); OVERLOAD;
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.

This article has been dead for over three months

You