Tutorial: Sortier-Algorithmen I+II

[Udontknow]

Wir müssen uns nochmal mit dem Fehler in der Routine "Partition" beschäftigen.

Was ist mit der Initialisierung "j:=r"?

Deine Funktion "Partition" schlägt fehl, wenn das letzte Element Data[r] die kleinste Wertigkeit hat.

Nimm mal folgende Zahlenfolge an :

Data[1]:=1200;
Data[2]:=1100;
Data[3]:=1000;

Führe nun Partition[1,3] durch.
Die Initialisierung belegt dann

v=Data[r]=1000,
i=l-1=0
und j=r=3.

Nachdem i einmal inkrementiert und dann die Abbruchbedingung Data[i]>=v) erfüllt wurde, gerätst du in eine Endlosschleife, die j immer weiter senkt:
Du senkst zunächst j um 1. Ab diesem Zeitpunkt ist (zumindest innerhalb der Arraygrenzen) deine Abbruchbedingung Data[j]<=v gar nicht mehr erfüllbar, da eben der niedrigste Wert der Zahlenfolge das letzte Element (r) ist, du aber eine Prüfung immer erst beim vorletzten Element ansetzt!
Bei einem TList-Objekt wie bei mir ist sowas halb so schlimm, ich bekomme dann eine Exception, bei einem Array aber "sortierst" du plötzlich Speicherbereiche, die gar nicht zum Array gehören (wenn z.B. zufälligerweise Data[-5043]=900 ist, tauscht du dann an dieser Stelle die Werte aus ).

Bei einer Initialisierung mit "j:=r+1" wäre das natürlich dann korrekt.

Was meinst du?

Cu,
Udontknow