Sortieren

[schlecki]

Hallo,

hier mal eine komfortable Möglichkeit, verschiedene Sortieralgorithmen in einem Programm verwenden zu können.
Das System baut auf Interfaces auf, so dass hier im Grunde beliebige Daten sortiert werden können. Im Grunde muß es natürlich nicht mit Interfaces aufgebaut werden, ich wollte das aber mal ausprobieren, außerdem finde ich die "automatische" Freigabe ganz nett.

Wir brauchen also zuerst einmal die Schnittstellen:

Delphi-Quellcode:

type
  ISortable = interface(IInterface)
    ['{7BC38DE8-2EDD-4F89-9E1E-1D3F635584E7}']
    function Compare(const Index1, Index2: Integer): Integer;
    procedure Exchange(const Index1, Index2: Integer);
    function GetItemCount(): Integer;
  end;

  ISorterClass = interface(IInterface)
    ['{75DB926E-8D44-4F3C-B7A8-0DA049DD1B92}']
    procedure SetSortable(const Sortable: ISortable);
    function GetSortable(): ISortable;
    function Execute(): TSortableCount;
    function GetSortName: string;
  end;

ISortable wird also von den zu sortierenden Klassen implementiert, ISorterClass hingegen von unseren Algorithmen.

Dann erstellen wir eine Basisklasse für die Algorithmen und eine einfache Implementierung (hier einfach mal ein BubbleSort)

Delphi-Quellcode:

  TCustomSortClass = class(TInterfacedObject, ISorterClass)
  private
    FExchangeCount: Integer;
    FCompareCount: Integer;
    FSortable: ISortable;
    FStartTime: TDateTime;
    procedure InitSort;
    function DoCompare(const Index1, Index2: Integer): Integer;
    procedure DoExchange(const Index1, Index2: Integer);
    function GetSortable: ISortable;
    procedure SetSortable(const Value: ISortable);
  protected
    procedure DoSort(L, R: Integer); virtual; abstract;
  public
    property CompareCount: Integer read FCompareCount;
    property ExchangeCount: Integer read FExchangeCount;
    property Sortable: ISortable read GetSortable write SetSortable;
    function Execute(): TSortableCount;
    function GetSortName: String;
  end;

  TBubbleSort = class(TCustomSortClass)
  protected
    procedure DoSort(L: Integer; R: Integer); override;
  end;

Die beiden Count-Variablen und der DateTime werden für eine einfache Auswertung verwendet. TSortableCount ist ein einfacher Record der die gesammelten Daten (Anzahl Vergleiche, Vertauschungen und Dauer) kompakt zurückliefert.

TBubbleSort muß dann einfach nur noch die DoSort implementieren. Er greift nur auf DoCompare und DoExchange zu. Dadurch muß der eigentlich Algorithmus keinerlei Information über die eigentlichen Daten besitzen. Um das zu zeigen hier die Implementierung:

Delphi-Quellcode:

procedure TBubbleSort.DoSort(L, R: Integer);
var
  i: Integer;
  j: Integer;
begin
  for i := R downto L do
    for j := 1 to i do
      if DoCompare(j - 1, j) > 0 then
        DoExchange(j - 1, j);
end;

Zu beachten ist hier lediglich, dass DoCompare einen Wert < 0 liefert, wenn die Daten von "j - 1" kleiner als die Daten "j" sind, 0 bei Gleichheit und ansonsten positive Werte. Der genaue Wert ist für den BubbleSort nicht relevant.

Doch wie kann nun damit sortiert werden? Das möchte ich jetzt am Beispiel einer Stringlist, die sortiert werden soll zeigen. Dazu brauchen wir noch eine weitere Klasse, die die eigentlichen Vergleiche und Vertauschungen vornehmen kann:

Delphi-Quellcode:

  TStringsSorter = class(TInterfacedObject, ISortable)
  private
    FStrings: TStrings;
    FLog: TStrings;
  public
    constructor Create(const ALines: TStrings; const Log: TStrings); reintroduce; virtual;
    function Compare(const Index1: Integer; const Index2: Integer): Integer;
    procedure Exchange(const Index1: Integer; const Index2: Integer);
    function GetItemCount: Integer;
    property List: TStrings read FStrings;
  end;

Diese Klasse implementiert wie oben bereits angesprochen ISortable. Der Konstruktor nimmt zwei Stringlisten, die erste wird sortiert, in die zweite werden wir mitloggen, welche Aufrufe vom Algorithmus aufgerufen wurden.
Die Implementierung der kompletten Klasse ist:

Delphi-Quellcode:

{ TStringsSorter }

function TStringsSorter.Compare(const Index1, Index2: Integer): Integer;
var
  v1: String;
  v2: String;
begin
  v1 := FStrings[Index1];
  v2 := FStrings[Index2];
  Result := AnsiCompareStr(v1, v2);
  if Assigned(FLog) then
    FLog.Add(Format('Compare on Indices [%d] and [%d] - values %s  and %s; Result = %d', [Index1, Index2, v1, v2, Result]));
end;

constructor TStringsSorter.Create(const ALines, Log: TStrings);
begin
  inherited Create;
  FLog := Log;
  FStrings := ALines;
end;

procedure TStringsSorter.Exchange(const Index1, Index2: Integer);
begin
  if Assigned(FLog) then
    FLog.Add(Format('*** Exchange index %d and %d', [Index1, Index2]));
  FStrings.Exchange(Index1, Index2);
end;

function TStringsSorter.GetItemCount: Integer;
begin
  Result := FStrings.Count;
end;

Das eigentliche Herzstück ist Compare. Diese Methode bekommt zwei Indices, die es zu vergleichen gilt. Wir verwenden dazu AnsiCompareStr. Diese Funktion liefert uns ein Ergebnis genau, wie wir es brauchen. Auch die Methode Exchange bekommt zwei Indices und vertauscht diese in der Liste. Wie zu sehen ist, kann für die Variable Log im Konstruktor auch nil übergeben werden, dann erfolg einfach keine Ausgabe.

Damit sind wir gerüstet, um beliebige Stringlisten zu sortieren (und natürlich beliebig andere Datenstrukturen, wenn entsprechende TSorter erstellt werden!)

Delphi-Quellcode:

var
  Sortable: ISortable;
  Sorter: ISorterClass;
  Count: TSortableCount;
begin
  FillDataToSort(lstToSort);
  Sortable := TStringsSorter(lstToSort, Memo1.Lines);
  Sorter := TBubbleSort.Create;

  Sorter.SetSortable(Sortable);
  Count := Sorter.Execute;
  Memo1.Lines.Add(Format('=== %s Compare: %d, Exchange: %d, Time: %s', [Sorter.GetSortName, Cnt.CompareCount, Cnt.ExchangeCount, FormatDateTime('HH:MM:SS.ZZZ', Cnt.TimeNeeded)]));
end;

Viel Spaß beim Sortieren

wünscht
schlecki03