Zitat von
Apollonius:
Sollten das nicht eher Klassenmethoden sein?
Im Moment vielleicht schon; die Klasse TBSearch hat z.Zt. nur die Aufgabe den Code zusammenzuhalten.
Aber das könnte sich ändern.
Das Grundlegende an der Binären Suche ist doch, dass ein beliebiges Element aus einem Array mit einem Schlüssel verglichen wird.
Diesen Vergleich könnte man in eine virtuelle Methode auslagern, so dass der Algorithmus für alle denkbaren Datentypen erweiterbar ist.
Die Basisklasse sieht dann so aus (ungetestet):
Delphi-Quellcode:
TBSearch = class(TObject)
private
FSorted : Boolean;
protected
FLeft : Integer; // untere Grenze der Daten (meist 0)
FRight : Integer; // obere Grenze der Daten
// Rückgabewert von KeyCompare()
// Key < daten[index] => -1 (negative Zahl)
// Key = daten[index] => 0
// Key > daten[index] => +1 (positive Zahl)
function KeyCompare(index:integer):integer;virtual;abstract;
public
procedure QuickSort(Start, Stop: Integer);
function Search: Integer; overload;
function Search(out found:TBFound): Integer; overload;
property Sorted : Boolean read FSorted;
end;
Für jeden Datentyp, nach dem man suchen möchte, muss eine eigene Klasse abgeleitet werden.
Hier ein Beispiel für Integer:
Delphi-Quellcode:
TIntArray = array of Integer;
TBSearchInteger = class(TBSearch)
private
FData : TIntArray;
procedure SetData(const value:TIntArray);
protected
function KeyCompare(index:integer):integer;override;
public
Key : Integer; // der Wert nach dem gesucht werden soll
property Data : TIntArray read FData write SetData(value:TIntArray); // die Daten
end;
procedure TBSearchInteger.SetData(const value:TIntArray);
begin
FLeft := Low(value); // untere
FRight:= High(value); // und obere Grenze merken
FData := value;
end;
function TBSearchInteger.KeyCompare(index:integer):integer;
begin
if Key < FData[index] then Result := -1
else if Key > FData[index] then Result := 1
else Result := 0;
// möglich wäre auch: Result := Key - FData[index]
end;
Jetzt ergibt sich aber das Problem, das Quicksort nicht mehr funktioniert,
denn Quicksort hat zwei Grundoperationen: Vergleichen und Tauschen.
Also brauchen wir zwei weitere virtuelle Methoden in der Basisklasse:
Delphi-Quellcode:
function Compare(a,b:integer):integer;virtual;abstract; // vergleiche Element A mit B
procedure Exchange(a,b:integer);virtual;abstract; // tausche Element A mit B
Das war jetzt vielleicht ein bißchen viel auf einmal, drum höre ich jetzt auf. 8)