problem mit quicksort

[ch4mp1on]

Hallo,

also ich bin grad dabei den quicksort zu programmieren. Hab schon einige Beispiele im i-net zu hilfe genommen und allerhand ausprobiert, aber irgendwie krieg ich den nicht ans laufen.
Ich hab immer einen stack overflow, aber die Abbruchbedingung müßte eigentlich stimmen.

Delphi-Quellcode:

procedure TfrmRahmen.quicksort(var Zahlenliste:TZahlenliste; var unterePos:integer; var oberePos:integer);
var
  Pivot, links, rechts, temp:integer;
begin
  Pivot:=Zahlenliste[anzahl div 2];
  links:=unterePos;
  rechts:=oberePos;

  While (links < rechts) do
    begin
      While (Zahlenliste[links]<Pivot) do links:=links+1;
      While (Zahlenliste[rechts]>Pivot) do rechts:=rechts-1;       // wandern
      If (links < rechts-1) then
        begin
          temp:=Zahlenliste[links];
          Zahlenliste[links]:=Zahlenliste[rechts];   // tauschen
          Zahlenliste[rechts]:=temp;
          links:=links+1;
          rechts:=rechts-1;
        end;
    end; // while

    If unterePos<rechts then quicksort(Zahlenliste,unterePos,rechts);
    If links<oberePos then quicksort(Zahlenliste,links,oberePos);

end; { Quicksort }

[marabu]

Herzlich willkommen in der Delphi-PRAXiS, champion.

Bei deiner Implementierung scheinen dir zwei Flüchtigkeitsfehler unterlaufen zu sein, wenn ich nicht irre:

Delphi-Quellcode:

// ...
  While (links <= rechts) do
// ...
      If (links < rechts + 1) then
// ...

Freundliche Grüße vom marabu

[ch4mp1on]

Hmm, die Änderungen machen nicht wirklich Sinn.
Der Fehler bleibt hartnäckig der gleiche.

[marabu]

Die Änderungen machen schon Sinn. Zusätzlich ändere deine Berechnung des Pivot-Elementes noch ab:

Delphi-Quellcode:

Pivot := Zahlenliste[(unterePos + oberePos) div 2];

marabu

[wursthunter]

Ich bevorzuge BubbleSort! *g*

[stoxx]

schau mal hier : http://www.thedelphimagazine.com/disks.php

Issue 37, Sep (223Kb) von 1998 runterladen, da ist Quellcode zu Quicksort in reinstform mit drin.
Wunderschön und funktioniert ;-)

[alzaimar]

Ich empfehle auch immer wieder diese nette Seite über Sortieralgorithmen

[ch4mp1on]

Ok Danke Leute! Es funzt!

Jetzt werd ich mich mal am Heap und MergeSort versuchen.