quicksort hängt sich auf

[rory fluegler]

hallo, ich hab ein problem mit quicksort... das programm hängt sich beim sortieren auf. wäre toll, wenn ihr mir schnell antworten könntet..

Delphi-Quellcode:

procedure TForm1.Quicksort (l,r:Integer);
var i,j,Merke,Mitte: Integer;
begin
  i:= L;
  j:= R-1;
  Mitte:= Wert[(L+R)div 2];

  //vergleich
  repeat
  while (Mitte <= Wert[j]) and (j>i) do
  begin
    dec (j);
    counter_Vergleich:=counter_Vergleich+1;
  end;
  while (Mitte >= Wert[i]) and (i<j) do
  begin
    inc (i);
    counter_Vergleich:=counter_Vergleich+1;
  end;

  //tauschen
  if i > j then
  begin
      Merke:=Wert[i];
      Wert[i]:= Wert[j];
      Wert[j]:= Merke;
      counter_Tausch:=counter_Tausch+1;
  {if j > i then
    dec (j);}
  end;

  until i < j;

  //Rekursion

  Quicksort(i+1,R);
  Quicksort(L,j-1);

end;

schon mal vielen dank.

lg

[DelphiDeveloper]

Dann schau Dir mal den Source in der Delphi VCL an:

z.b. ListAcnts.pas (muesste auch bei Delphi 5 im Verzeichnis ..Source\Vcl liegen

Hier ein kleiner Auschnitt:

Delphi-Quellcode:

procedure TListControlItems.QuickSort(L, R: Integer; SCompare: TListItemsCompare);
var
  I, J, P: Integer;
begin
  repeat
    I := L;
    J := R;
    P := (L + R) shr 1;
    repeat
      while SCompare(Self, I, P) < 0 do Inc(I);
      while SCompare(Self, J, P) > 0 do Dec(J);
      if I <= J then
      begin
        ExchangeItems(I, J);
        if P = I then
          P := J
        else if P = J then
          P := I;
        Inc(I);
        Dec(J);
      end;
    until I > J;
    if L < J then QuickSort(L, J, SCompare);
    L := I;
  until I >= R;
end;

Dann wirst du deinen Algo auch lauffähig kriegen.

mfg
Delphideveloper

[Noobinator]

Dein Code ist ja soweit In Ordnung.

Wenn sich das Programm "aufhängt" also nicht mehr Reagiert, deutet das ziemlich wahrscheinlich auf eine Endlosschleife/Endlosrekursion hin.

bei dir eher ne Endlosrekursion, aber den Fehler solltest du mit dem Code von DelphiDeveloper schnell finden ;)

[QuickAndDirty]

Du rufst immer wieder die Rekursion auf.
Da muss eine Bedingung rein wann du damit aufhören musst, eine so genannte Abbruchbedingung.

[alzaimar]

Abbruchbedingung: Beim Quicksort unterteilst Du die Liste L in zwei Teillisten A und B, wobei jedes Element aus A kleiner als jedes Element aus B ist. Anschließend rufst Du Quicksort für A und B auf.

Bei Dir fehlt die Abfrage, ob A und B leer sind bzw. nur aus einem Element besteht.