Quicksort

[Amateurprofi]

Zitat:

Vielleicht könntest du dir die Delphi-Implementierung auf dieser Seite einmal ansehen bzw. sie korrigieren. Laut Diskussion ist man sich dort auch nicht ganz einig, welcher Vergleichsoperator nun der richtige ist.

@Hawkeye:

Diese Prozedur aus Wikipedia meinst Du?!

Delphi-Quellcode:

procedure quicksort(var a:array of integer;l,r:integer);
var lpos,rpos,tmp,pivot:integer;
begin
  pivot:=a[(l+r) div 2];
  lpos:=l;
  rpos:=r;

  while lpos<=rpos do
    begin
      while a[lpos]<pivot do inc(lpos);
      while a[rpos]>pivot do dec(rpos);
      if lpos<rpos then
        begin
          tmp:=a[lpos];
          a[lpos]:=a[rpos];
          a[rpos]:=tmp;
          inc(lpos);
          dec(rpos);
        end;
    end;
  if l<rpos then quicksort(a,l,rpos);
  if lpos<r then quicksort(a,lpos,r);
end

Um ehrlich zu sein, ich habe mir nie die Mühe gemacht, Quicksort wirklich zu verstehen - mir hat es immer gereicht, daß die Prozedur, so wie ich sie einsetze, funktioniert.

Anders als die "Bonanza-Version" verwendet die "Wikipedia-Version" als "outer loop" nicht ein Repeat-Until sondern ein While Do Konstrukt, das auch den Fall lpos=rpos abfängt, somit tritt auch keine Endlos-Schleife auf. Rein gefühlsmäßig hätte ich aber Bedenken gegen die "Wikipedia-Version".
Warum?:
Quicksort teilt das zu sortierende Feld jeweils in 2 Teilfelder auf, die dann, jedes für sich sortiert werden.
Wenn die "outer loop" abgebrochen wird dann folgt.

Delphi-Quellcode:

if l<rpos then quicksort(a,l,rpos);
if lpos<r then quicksort(a,lpos,r);

und wenn der Abbruch der "outer loop" erfolgte, weil lpos=rpos ist, dann würde a[lpos], das ja identisch ist mit a[rpos]
zu beiden neuen Teilfeldern gehören. Weiß nicht, ob das kritisch ist, aber nach meinem Verständnis ist dann keine saubere Trennung der einzelnen Teilfelder gegeben.

Wenn ich mal viel Zeit habe, werde ich mich damit eingehender befassen - zur Zeit solltest Du obigen Text als "aus der Hüfte geschossen" betrachten.