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:

zusammenfalten · markieren

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)

zusammenfalten · markieren

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:

markieren

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:

zusammenfalten · markieren

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:

zusammenfalten · markieren

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

zusammenfalten · markieren

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

Sortieren

Sortieren

Forumregeln