Quicksort

[Amateurprofi]

Zitat:

aber warum muss es "<=" sein ? wenn die doch gleich sind also auf einem "Punkt" stehen kann man die ja schlecht tauschen, also es macht keinen großen oder ?

Bonanza,
Schau Dir doch mal die Repeat Schleife an.
Nimm an, die beiden While Schleifen seien abgearbeitet und l_pos ist gleich r_pos.
Wenn jetzt weder l_pos noch r_pos verändert wird, dann wird die beim until definierte Abbruchbedingung ganz sicher nicht erfüllt.
Also wird die Repeat Schleife wiederholt, mit dem Ergebnis, daß sich an l_pos und r_pos nichts ändert.
Tja, und dann läuft dein Programm in einer Endlos-Schleife.

Wenn l_pos = r_pos ist müssen a[l_pos] und a[r_pos] nicht vertauscht werden (es ist aber auch nicht schädlich).
Wichtig ist nur, daß l_pos um erhöht und r_pos gesenkt wird.

Delphi-Quellcode:

   repeat
      while a[l_pos] < pivot do inc(l_pos);
      while a[r_pos] > pivot do dec(r_pos);
      if l_pos <= r_pos then begin
         temp := a[l_pos];
         a[l_pos] := a[r_pos];
         a[r_pos] := temp;
         inc(l_pos);
         dec(r_pos);
      end;
   until (l_pos > r_pos) ;

[bonanza]

ok das leuchtet ein...danke !

aber jetzt habe ich wieder das problem, dass Edit10 immer überschrieben wird und da immer "+ 1".
Hätte jemand eine idee warum ?

[Hawkeye219]

@Amateurprofi

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.

Gruß Hawkeye

[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.

[bonanza]

Ich habe noch einmal ein Problem und zwar will ich den jeweils veränderten Bereich (durch quicksort) in einem Stringgrid darstellen...
dazu haben ich folgendes geschrieben:

Delphi-Quellcode:

{....}
var
  Form1: TForm1;
  Zahlen : Array[1..100] of boolean;
  ZZahlen: Array[1..10] of boolean;
  SS_liste: Array[0..9] of integer;
  durchlauf : integer;
{...}
procedure akt_sg (a: array of integer; b, c:integer);
var j, start, ende: integer;
begin
if (b >= c) then begin start := c; ende:= b; end;
for j := start to ende do begin
form2.Stringgrid1.Cells[j+1, durchlauf] := IntToStr(ss_liste[j]);
end;
end;


{...vorderer Teil der QS-Prozedur...Rest siehe 3. letztes Posting (wollte dies hier nich zu voll packen)...}
                      temp := a[l_pos];
                      a[l_pos] := a[r_pos];
                      a[r_pos] := temp;
                      inc(durchlauf);
                      if (l_pos < pivot_feld) then akt_faktor := anfang else akt_faktor := ende;  //*1
                      akt_sg(a, akt_faktor, pivot);
{...danach folgender Teil...}

Ich hab mir da so gedacht, dass mit dem bei "*1*" markierten bereich kontrolliert wird, welcher Teil des gesamten verändert wurde ich dann mit der oberen "akt_sg" prozedur das in das Stringgrid übertrage, doch aus irgendeinem Grund funktioniert da schon etwas mit der parameter übergabe nicht so ganz, wie ich es haben möchte.

Wäre für eure Hilfe sehr dankbar

[Hawkeye219]

Zitat von bonanza:

if (b >= c) then begin start := c; ende:= b; end;

Und was ist bei b < c?

[Angel4585]

dann iss schon richtig rum un muss nich getauscht werden

[Hawkeye219]

er soll mit nicht initialisierten Variablen weiterarbeiten?