Mirror

Write sorting/search methods that can be re-used (Views: 100)


Problem/Question/Abstract:

I find that alot of developers that use sorting and search algorithms, taking the Quick Sort algorithm for an example, will reimplement it for every use.

Answer:

Sorting algorithms rarely depend on actual knowledge what they are sorting, and when we require an algorithm and implement it, why restrict the algorithm to a specific use, as the algorithm itself will never change.

They are only dependent on an index of which they then need to compare and exchange the information that resides at those indexes.

The quick sort algorithm for the example would require only 3 main factors of which could be passed to a quick sort method.

Start and End indexes
Method for Comparing points
Method for Exchanging points

This going to apply for practially all sorting/searching algorithms.

All that is required is that we specify the types that will define the Compare and Exchange methods.

type
  TIndexCompare = function(const ixA, ixB: integer): integer of object;
  TIndexExchange = procedure(const ixA, ixB: integer) of object;
  //-- Also these methods could be also reused for multiple sort algorythms.
  //-- e.g
  //-- procedure InsertionSortByIndex(ixLo, ixHi: Integer;
  //--                                IndexCompare: TIndexCompare;
  //--                                IndexExchange: TIndexExchange);
  //--  etc....

procedure QuickSortByIndex(ixLo, ixHi: Integer;
  IndexCompare: TIndexCompare;
  IndexExchange: TIndexExchange);
implementation

procedure QuickSortByIndex(ixLo, ixHi: Integer;
  IndexCompare: TIndexCompare;
  IndexExchange: TIndexExchange);

  procedure SortIndex(aLo, aHi: Integer);
  var
    I, J, P: Integer;
    tmpInt: Integer;
  begin
    repeat
      I := aLo;
      J := aHi;
      P := (aLo + aHi) shr 1;
      repeat
        while (I < aHi) and (IndexCompare(I, P) < 0) do
          Inc(I);
        while (J > aLo) and (IndexCompare(J, P) > 0) do
          Dec(J);
        if I <= J then
        begin
          IndexExchange(I, J);
          if P = I then
            P := J
          else if P = J then
            P := I;
          Inc(i);
          Dec(j);
        end;
      until I > J;
      if aLo < J then
        SortIndex(aLo, J);
      aLo := I;
    until I >= aHi;
  end;

begin
  SortIndex(ixLo, ixHi);
end;

Now to use this..lets say i want to sort a listbox for the example(rather than using  the Listbox standard sorting)

type
  TMyForm = class(TForm)
  private
    ListBox1: TListBox;
    btnSort: TButton;
    .....
    public
    function IndexCompare(const ixA, ixB: integer): integer;
    procedure IndexExchange(const ixA, ixB: integer);
  end;
  ..

implementation

function TMyForm.IndexCompare(const ixA, ixB: integer): integer;
//-- Source to compare items.
begin
  Result := AnsiCompareText(ListBox1.Items[ixA], ListBox1.items[ixB]);
end;

procedure TMyForm.IndexExchange(const ixA, ixB: integer);
// -- Source to exchange items.
var
  tmpStr: string;
begin
  tmpStr := ListBox1.Items[ixA];
  ListBox1.Items[ixA] := ListBox1.Items[ixB];
  ListBox1.Items[ixB] := tmpStr;
end;

procedure TMyForm.btnSortClick(Sender: TObject);
begin
  with ListBox1.items do
  begin
    BeginUpdate;
    try
      if UseQuickSort then
        QuickSortByIndex(0, count - 1, IndexCompare, IndexExchange)
      else
        InsertionSortByIndex(0, count - 1, IndexCompare, IndexExchange);
    finally
      EndUpdate;
    end;
  end;
end;

//----

Well hopefully that might of been some use

Later All

<< Back to main page