Sortierung unwirksam

[marabu]

Hi,

Zitat von Neutral General:

... Hab mich hieran ... orientiert. ...

ich komme zu folgendem Ergebnis, wenn ich den Wikipedia-Algorithmus implementiere - ich habe versucht so viel wie möglich von deinem Code beizubehalten:

Delphi-Quellcode:

procedure SortArray(var CombiArray: TCombis; l, r: Integer);

  function Divide(l, r: Integer): Integer;

    procedure Exchange(s,t: Integer);
    var tmp: TList;
    begin
      tmp := CombiArray[s];
      CombiArray[s] := CombiArray[t];
      CombiArray[t] := tmp;
    end;

  var
    pivot: Integer;
  begin
    // Dec(l); // muss wech!
    pivot := r;
    while l < r do
    begin
      while CombiArray[l].Count < CombiArray[pivot].Count do
        Inc(l);
      while (l < r) and (CombiArray[r].Count > CombiArray[pivot].Count) do
        Dec(r);
      if l < r then
        Exchange(l, r);
    end;
    Exchange(l, pivot);
    Result := l;
  end;

Du hast dich offensichtlich von der visuellen Ähnlichkeit des Pseudo-Codes "wiederhole block solange bedingung" mit einer REPEAT-Schleife täuschen lassen. Tatsächlich ist es aber eine WHILE-Schleife.

Freundliche Grüße

[Neutral General]

Hi,

Danke. Aber das Problem ist: Das funktioniert auch nicht. Bekomme in der Zeile

while CombiArray[l].Count < CombiArray[Pivot].Count do irgendwann ne AV. Ist eigentlich auch logisch bei ner while schleife weil da erst geprüft wird und dann ausgeführt.. d.h. man fängt mit CombiArray[-1] an, wohingegen man bei repeat bei 0 anfängt weil vorher geinct wird. Wenn ich das dec weglasse hab ich ne Endlosschleife.

Naja hab das gefunden was unser Info-Lehrer uns gegeben hat:

*klick*

da wirds auch mit repeat gemacht und mit <= und >= ...

Mein Quelltext sieht jetzt so aus:

Delphi-Quellcode:

procedure SortArray(var CombiArray: TCombis; l,r: Integer);

  function Divide(l,r: Integer): Integer;

    procedure Exchange(s,t: Integer);
    var tmp: TPriceList;
    begin
      tmp := CombiArray[s];
      CombiArray[s] := CombiArray[t];
      CombiArray[t] := tmp;
    end;

  var pivot: Integer;
      k: Integer;
  begin
    dec(l);
    pivot := r;
    while l < r do
    begin
      while CombiArray[l].Count < CombiArray[Pivot].Count do
        inc(l);
      while (l < r) and (CombiArray[r].Count > CombiArray[Pivot].Count) do
        dec(r);
      if l < r then
        Exchange(l,r);

      { Form1.ListBox1.Clear;
      for k := 0 to High(CombiArray) do
      begin
        Form1.ListBox1.Items.Add(IntToStr(CombiArray[k].Count));
        Application.ProcessMessages;
      end;
      sleep(10); }
    end;
    Exchange(l,pivot);
    Result := l;
  end;

var m: Integer;
begin
  if r > l then
  begin
    m := Divide(l,r);
    SortArray(CombiArray,l,m-1);
    SortArray(CombiArray,m+1,r);
  end;
end;

Gruß
Neutral General

[marabu]

Hi,

bei meinen drei Tests ist zwar der Fehler nicht aufgetreten, aber du hast Recht: Der Lower Bound Index darf beim Start von SortArray() nicht verringert werden.

Ob du nun REPEAT oder WHILE verwendest, dass ist gehoppt wie gesprungen, wenn du die Abbruchbedingungen und die Initialwerte richtig angepasst hast. Insofern ist der Wikipedia Pseudo-Code sowas wie "REPEAT Block WHILE Bedingung".

Freundliche Grüße