Heapsort funktioniert nicht

[spox]

Hallo! :)

Ich arbeite gerade an einen Heapsort-Algorithmus. Doch irgendwie will es nicht so wie es soll.

Ich benutze 2 Prozeduren. Die eine ist sozusagen eine Teilprozedur von Heapsort, nämlich diese:

Delphi-Quellcode:

procedure HeapBauen (VAR Feld:TFeld;
                        links, rechts:integer);
var
 oben,unten,lager:integer;
 ready:boolean;
begin
  ready:=false;
  oben:=links;
  unten:=2*oben;
  lager:=feld[oben];
  while (unten<=rechts) and not ready do
  begin
    if unten<rechts then
    begin
      if feld[unten+1]<feld[unten] then
      begin
        unten:=unten+1;
      end;
    end;
    if lager>feld[unten] then
    begin
      feld[oben]:=feld[unten];
      oben:=unten;
      unten:=2*oben;
    end
    else ready:=true
  end;
  feld[oben]:=lager;
end;

Die "Hauptprozedur" greift auf diese zu und sollte das Feld sortieren. Doch es will einfach nicht...

Delphi-Quellcode:

procedure heapen(var Feld:TFeld);
var
  i:integer;
begin
  for i:= ((anzahl DIV 2)-1) downto 1 do HeapBauen(Feld,1,Anzahl);
end;

Kann mir jmd. helfen? Ich steh grad auf'n Schlauch :gruebel:

[gammatester]

Drei Anmerkungen:

1. Es meist sinnvoll, Standardbezeichnungen zu verwenden, dann kann man fremden Code besser verstehen.
2. Ich würde mich wundern, wenn man ohne Vertauschungen auskommt.
3. Wenn Dein Algorithmus halbwegs Heapsort sein soll, muß noch eine zweite Phase in heapen auftreten, etwa so (Tausche mußt Du programmieren):

Delphi-Quellcode:

procedure heapen(var Feld:TFeld);
var
  i:integer;
begin
  for i:= ((anzahl DIV 2)-1) downto 1 do HeapBauen(Feld,1,Anzahl);
  for i:=anzahl downto 2 do begin
    Tausche(Feld[1], Feld[i])
    HeapBauen(Feld,1,i-1);
  end;
end.

Gruß Gammatester

[spox]

funktioniert leider nicht. Das Feld wird nicht sortiert. Eine Tauschprozedur hatte ich schon, weshalb ich diese verwenden konnte.

[gammatester]

Zitat:

Zitat von spox

funktioniert leider nicht. Das Feld wird nicht sortiert. Eine Tauschprozedur hatte ich schon, weshalb ich diese verwenden konnte.

Ich gehe davon aus, daß TFeld ein array of integer ist. Wenn heapen wie folgt geändert wird, funktionsierts bei mir.

Delphi-Quellcode:

procedure heapen(var Feld:TFeld);
var
  i: integer;
  t: integer;
begin
  for i:= (anzahl DIV 2) downto 1 do HeapBauen(Feld,i,Anzahl);
  for i:= anzahl downto 2 do begin
    t := Feld[1];
    Feld[1] := Feld[i];
    Feld[i] := t;
    HeapBauen(Feld,1,i-1);
  end;
end;

Unsortiert
1 4 87 21 28 68 32 17 38 43 9 48 8 85 6

Sortiert
87 85 68 48 43 38 32 28 21 17 9 8 6 4 1

Gruß Gammtester

[spox]

Boa supi. Funzt nu :thumb: