Fehler bei Quicksort

[Cöster]

Hallo erstmal!
Ich wollte ein Quicksort-Programm programmieren. Hier der Quelltext (ist teilweise von Wikipedia abgeschrieben):

Delphi-Quellcode:

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
  StdCtrls, Grids;

type
  TForm1 = class(TForm)
    StringGrid1: TStringGrid;
    BtSortieren: TButton;
    BtGenerate: TButton;
    procedure FormCreate(Sender: TObject);
    procedure BtGenerateClick(Sender: TObject);
    procedure QuickSort(von, bis: Integer);
    procedure BtSortierenClick(Sender: TObject);
  private
    { Private-Deklarationen }
  public
    { Public-Deklarationen }
  end;

const
  Menge = 7;

var
  Form1: TForm1;
  Feld: Array[1..Menge] of Integer;

implementation

procedure TForm1.QuickSort(von, bis: Integer);
var l, r, v, hilf: integer;
begin
  l := von;
  r := bis;
  v := (l + r) div 2;
  while l <= r do
  begin
    while (Feld[l] < Feld[v]) do
      l := l + 1;
    while (Feld[r] > Feld[v]) do
      r := r - 1;
    If l <= r then
    begin
      hilf := Feld[r];
      Feld[r] := Feld[l];
      Feld[l] := hilf;
      l := l + 1;
      r := r - 1;
    end;
  end;
  If von < r then QuickSort(von, r);
  If bis > l then QuickSort(l, bis);
end;

{$R *.DFM}

procedure TForm1.FormCreate(Sender: TObject);
begin
  Randomize;
end;

procedure TForm1.BtGenerateClick(Sender: TObject);
var i: integer;
begin
  For i := 1 to Menge do
  begin
    Feld[i]:=random(10);
    StringGrid1.Cells[i-1, 0] := IntToStr(Feld[i]);
  end;
end;

procedure TForm1.BtSortierenClick(Sender: TObject);
var i: Integer;
begin
  QuickSort(1, Menge);
  For i := 1 to Menge do
    StringGrid1.Cells[i-1, 0] := IntToStr(Feld[i]);
end;

end.

Meistens sortiert er es auch schon richtig, aber nicht immer. Wenn die Zahlenfolge z.B. 8731342 lautet, muss ich zweimal den Sortieren-Button klicken, damit die Zahlen richtig sortiert sind.
Was muss ich an dem Quelltext denn noch ändern, damit's klappt?
Ich hoffe, mir kann jemand helfen.

[Klaus01]

Delphi-Quellcode:

procedure TForm1.QuickSort(von, bis: Integer);
var l, r, v, hilf: integer;
begin
  l := von;
  r := bis;
  v := Feld[(l + r) div 2];
  while l <= r do
  begin
    while (Feld[l] < v) do
      l := l + 1;
    while (Feld[r] > v) do
      r := r - 1;
    If l <= r then
    begin
      hilf := Feld[r];
      Feld[r] := Feld[l];
      Feld[l] := hilf;
      l := l + 1;
      r := r - 1;
    end;
  end;
  If von < r then QuickSort(von, r);
  If bis > l then QuickSort(l, bis);
end;

Versuch es mal so.

Dein Fehler ist gewesen, dass Du mit dem Feld[v] vergleichst.
Das Feld[v] kann sich aber in der while do Schleife ändern,
es sollte sich aber dort nicht ändern.

Deshalb ist es besser vor der while Schleife den Wert von Feld[v] zu speichern
und damit zu vergleichen.
Ist in Wikipedia aber auch so beschrieben.

Hier noch ein Quicksort mit Repeat until: http://www.dsdt.info/tipps/?id=380

Grüße
Klaus

[shmia]

Bei Quicksort kann man viele Fehler machen.
Gut möglich, dass ein Quicksort Algorithmus richtig sortiert
aber er ist (manchmal abhängig von den Daten) nicht wirklich "quick".
Man muss also immer gut aufpassen, was man da abschreibt, kopiert oder selber hinschreibt.

[Cöster]

@ Klaus:
Danke, das war's. Hab nicht dran gedacht, dass sich Feld[v] ja ändert, als mich am Wiki-Code orientiert hab.

[Cöster]

Zitat:

Zitat von shmia

Bei Quicksort kann man viele Fehler machen.
Gut möglich, dass ein Quicksort Algorithmus richtig sortiert
aber er ist (manchmal abhängig von den Daten) nicht wirklich "quick".
Man muss also immer gut aufpassen, was man da abschreibt, kopiert oder selber hinschreibt.

Ich hab den BubbleSort auch ins Programm reingepackt und dann mal die Sortierzeiten für 100.000 Ziffern (0 bis 9) gemessen. Das Ergebnis:
QuickSort : 16 ms
BubbleSort: 83390 ms

Da zeigen sich dann doch "leichte" Vorteile beim QuickSort in Bezug auf die Quickness. :wink:

[shmia]

Zitat:

Zitat von Cöster

Da zeigen sich dann doch "leichte" Vorteile beim QuickSort in Bezug auf die Quickness. :wink:

Na ja, so habe ich das nicht gemeint.
Sondern eher so (fiktives Beispiel)
Quicksort Algo #1: 529 Vertauschungen, 1901 Vergleiche
Quicksort Algo #2: 620 Vertauschungen, 12970 Vergleiche
Man sieht, das der Algorithmus #2 wesentlich mehr Vergleiche braucht,
weil irgendein ungeschickter Fehler enthalten ist.
Trotzdem sortieren beide richtig und man merkt den Unterschied bei kleinen Datenmengen nicht.

Aber dass Bubblesort eine schlechte Performance hat ist klar.
Und es gibt noch schlechtere: z.B. Stoogesort