Binäre Suche

[Luckie]

Na das sieht doch schon ganz gut aus.

[alzaimar]

... sooo, nun eine kleine Kritik.

• Das Quicksort-Verfahren kann dahingehend optimiert werden, das nur ein rekursiver Aufruf erfolgt. Vorlage wäre die Quicksort-Routine von TStringlist. Ich meine, das die schneller/besser ist.
• Das Suchen mit vorherigem Sortieren ist Quark, denn das dauert länger (O(n log n) als eine Suche in einer unsortierten Liste (O(n)). Da der Anwender genau weiss, ob seine Liste sortiert ist, oder nicht, kann/muss er sie eben gleich selbst sortieren (lassen)
• Die hier angestrengen Überlegungen für eine allgemeine Listenklasse sind insofern kontraproduktiv, als das die daraus resultierende Klasse sehr behäbig seinen Dienst verrichten würde, da die für die Sortierung elementaren Operationen ('Swap') ausgelagert werden.

Ex-CodeGear! Her mit den Generics! Aber zack! Zack!

[gammatester]

Zitat von alzaimar:

Delphi-Quellcode:

function Search(const aItem: TElement; AArray: TElementArray; var aIndex: Integer): Boolean;
var
  L, R, M: integer; // Für Left, Right, Middle

begin
  L := Low(aItem);
  R := High(aItem);
...
end;

Sollte das nicht besser heißen

Delphi-Quellcode:

  
L := Low(AArray);
R := High(AArray);

Gruß Gammatester

[alzaimar]

Och.. äh... Spießer..

[p80286]

Hallo sx2008,

ich hab mir Deine Demo einmal angeschaut, und bin bei der Stringsuche irgenwie in der Botanik gelandet.
Ich hab dann ein wenig angepasst und jetzt läufts.

Gruß K-H

[gammatester]

Zitat von p80286:

Hallo sx2008,

ich hab mir Deine Demo einmal angeschaut, und bin bei der Stringsuche irgenwie in der Botanik gelandet.
Ich hab dann ein wenig angepasst und jetzt läufts.

Gruß K-H

Ich denke, daß zumindest Deine Quciksort-Routine unter einem bekannten Problem leidet:

Delphi-Quellcode:

procedure TBSearch.QuickSort(L, R: Integer);
var
  I, J, P: Integer;
begin
  repeat
    I := L;
    J := R;
    P := (L + R) shr 1;
    repeat
      while Compare(I, P) < 0 do
        Inc(I);
      while Compare(J, P) > 0 do
        Dec(J);
      if (I <= J) then
      begin
        Exchange(I, J);
        Inc(I);
        Dec(J);
      end;
    until (I > J);
    if (L < J) then
      QuickSort(L, J);
    L := I;
  until (I >= R);
end;

Beim Tauschen wird der Pivotindex nicht angepaßt, vgl http://www.delphipraxis.net/internal...ighlight=pivot

Nach Exchange sollte also eingefügt werden

Delphi-Quellcode:

{P muss weiter auf Pivot zeigen} 
if I=P then P:=J                 
else if J=P then P:=I;

Luckies Routine hat das Problem nicht, da direkt mit einem Array gearbeitet wird.

Gruß Gammatester