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) ;