Tutorial: Sortier-Algorithmen I+II

[Udontknow]

Hallo, Daniel!

Ich habe mir mal den Quicksort zu Gemüte geführt und treffe da auf ein paar Probleme, vielleicht kannst du mir weiterhelfen:


Ich bekomme beim Ausführen den Hinweis "Listenindex überschreitet das Maximum" (habe anstelle eines Arrays ein TList-Objekt, habe also deine Routinen dementsprechend angepasst).

Du hast ja die Routinen Quicksort und Partition gepostet.
Bei der Funktion Partition glaube ich einen Fehler entdeckt zu haben.

Du initialisierst folgende Werte :

Code:

  
i:= l-1; 
j:= r;

i entspricht dem ersten Element in der Menge -1; Da du sofort in einer repeat-until-Schleife um 1 erhöhst, erhälst du dann als erstes den Index des ersten Elementes.
Wieso tust du das aber nicht mit j? Du willst ja anscheinend zunächst das letzte Element erhalten, da aber erstmal wieder in einer Repeat-Until-Schleife Dec(j) erfolgt, setzt du doch hier (fälschlicherweise?) beim vorletzten Element an, oder?

Nachdem ich also die Zeile "j:=r" durch "j:=r+1" ersetzt hatte, traten keine Fehler mehr auf, die Liste ist dann aber immer noch nicht komplett sortiert. Hast du auf Anhieb ne Idee, woran das liegen könnte?

Ich poste mal meine Partition-Routine, vielleicht hilft´s ja:

Code:

function TStempIDComponentList.Partition(l, r: Integer): Integer;
var v,i,j : Integer;
var t:Pointer;
Begin
  v:= Items[r].ID;
  i:= l-1;
  j:= r+1;
  Repeat

    Repeat
      inc( i );
    Until (Items[i].ID >= v);

    Repeat
      dec( j );
    Until (Items[j].ID <= v);

    t:= Items[i];
    Items[i]:=Items[j];
    Items[j]:= t;

  Until (j<=i);

  Items[j]:= Items[i];
  Items[i]:= Items[r];
  Items[r]:= t;

  Result:= i;
End;

Cu & thx im voraus,
Udontknow