Entwickler-Ecke

Algorithmen, Optimierung und Assembler - Heapsort "suboptimal" gelungen und Fehlerhaft


Wegi - Mo 10.09.07 07:50
Titel: Heapsort "suboptimal" gelungen und Fehlerhaft
Guten Tag,

Ich weiß das mein Heapsort nicht gerade Optimal ist, aber ich wollte es erstmal ohne verwendung des Internet Implementieren, allerdings gibt mir mein Compiler immer eine "Speicherzugriffsverletzung" in Zeile 76. Ich hoffe jemand sieht was daran falsch ist, ich kriege es nämlich partou nicht raus.


Delphi-Quelltext 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
 
unit Unit2;

interface
uses Classes, SysUtils;

Type     THeap = class
           private
             Feld : Array of integer;
             Ausgabe : TStringList;
             procedure CreateArray ();
             procedure sink(knoten : Integer);
           public
             constructor Create ();
             function GetAusgabe : TStringList;
             function GetLaenge : integer;
             procedure CreateHeap();

         end;

implementation


{ THeap }

constructor THeap.Create ();
begin
  CreateArray ();                  // Zufällige Vorbesetzung
  Ausgabe := TStringList.Create ();
end;

procedure THeap.CreateArray;
var i,la : integer;
begin
  randomize;
  la := random (100) + 1;
  SetLength (Feld,la);
  for i := 0 to la - 1 do
      Feld [i] := random (10000);
end;

procedure THeap.CreateHeap();
var max, min, i : Integer;
begin
  max := high(Feld) DIV 2;
  min := low(Feld);
  for i := max downto min do
    begin
      if i < (i*2 or i*2+1) then
        sink(i);
    end;
end;

function THeap.GetAusgabe: TStringList;
var
  i: Integer;
begin
  Ausgabe.Clear;
  for i := 0 to Length(Feld) - 1 do
    Ausgabe.Add(IntToStr(Feld[i]));
  Result := Ausgabe;
end;

function THeap.GetLaenge: integer;
begin
  Result := Length (Feld);
end;

procedure THeap.sink(knoten: Integer);
var temp : integer;
begin
  if knoten*2 < knoten*2+1 then
    begin
      if knoten < knoten*2+1 then
        begin
          temp := Feld[knoten];
          Feld[knoten] := Feld[knoten*2+1];
          Feld[knoten*2+1] := temp;
          sink(knoten*2+1);
        end;
    end
    else if knoten*2 > knoten*2+1 then
      begin
        if knoten < knoten*2 then
          begin
            temp := Feld[knoten];
            Feld[knoten] := Feld[knoten*2];
            Feld[knoten*2] := temp;
            sink(knoten*2);
          end;
      end
      else;
end;

end.


Zur Optimierung könnte man noch evtl. später kommen, da ich noch zusätzliche Methoden implementieren muss.

Umgebungsentwicklung: Borland Developer Studio 2006 (Turbo Delphi)


Tilo - Mo 10.09.07 08:03
Wie lautet der Index des 1.Feldes? Heapsort braucht als ersten Index 1 statt 0. außer dem ist


Delphi-Quelltext 
1:
 
if knoten*2 < knoten*2+1 then


immer wahr.
da auch


Delphi-Quelltext 
1:
 
if knoten < knoten*2+1 then

immer wahr ist führt sink immer

Delphi-Quelltext 
1:
2:
3:
4:
5:
6:
 
        begin
          temp := Feld[knoten];
          Feld[knoten] := Feld[knoten*2+1];
          Feld[knoten*2+1] := temp;
          sink(knoten*2+1);
        end;

aus.

Bei aufruf von Sink müsstest Du folgendes machen:
Test ob knoten*2> Anzahl der Felder im Heap ist. Wenn ja dann keine Kinder existent ->Abbruch
ermitteln des größten Kindes. Standard mäßig hier das linke Kind auswählen(Knoten*2), dann prüfen ob rechtes Kind(Knoten*2+1) vorhanden wenn ja Vergleich mit linken Kind. ->Den Index des größten Kind merken.
Das Größte Kind mit Knoten vergleichen. Ist Knoten größer als Kind so Ende, sonst Tausch Knoten<>Kind und sink mit Index des Kindes(welches nun den Wert des Knoten hat) aufrufen.

Dies gilt für MAxHeap, bei MinHeap die Relationen einfach umdrehen.


AXMD - Mo 10.09.07 08:04
Ich tippe mal auf den Zugriff auf ein Array-Element, das "nicht existiert". knoten*2 + 1 kann unter Umständen größer sein als die Größe deines Arrays - daher der Speicherzugriffsfehler.

AXMD


Wegi - Mo 10.09.07 15:14
Erstmal vielen Dank euch beiden, ich habe 2 Anfängerfehler auf einmal gemacht. 1. Nicht überprüft ob die Stelle des Arrays existiert, die ich betrachte und 2. habe ich die Indizes des Arrays verglichen anstatt den Inhalt. Nun läuft das programm auch, allerdings scheint es die Binäre Struktur nicht einzuhalten. Beim ersten testlauf hatte ich folgende Struktur raus, die ja nicht die eines heaps ist:

9290, 8343, 0, 578, 8087, 7144, 2478, 2511, 8752, 9150

Hier nochmal der veränderte Code:


Delphi-Quelltext 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
 
unit Unit2;

interface
uses Classes, SysUtils;

Type     THeap = class
           private
             Feld : Array of integer;
             Ausgabe : TStringList;
             procedure CreateArray ();
             procedure sink(knoten, max : Integer);
           public
             constructor Create ();
             function GetAusgabe : TStringList;
             function GetLaenge : integer;
             procedure CreateHeap();

         end;

implementation


{ THeap }

constructor THeap.Create ();
begin
  CreateArray ();                  // Zufällige Vorbesetzung
  Ausgabe := TStringList.Create ();
end;

procedure THeap.CreateArray;
var i,la : integer;
begin
  randomize;
  la := random (100) + 1;
  SetLength (Feld,la);
  for i := 1 to high(Feld) do
      Feld [i] := random (10000);
end;

procedure THeap.CreateHeap();
var max, min, i : Integer;
begin
  max := high(Feld) DIV 2;
  min := low(Feld);
  for i := max downto min do
    begin
      if Feld[i] < (Feld[i*2] or Feld[i*2+1]) then
        sink(i, max);
    end;
end;

function THeap.GetAusgabe: TStringList;
var
  i: Integer;
begin
  Ausgabe.Clear;
  for i := 0 to Length(Feld) - 1 do
    Ausgabe.Add(IntToStr(Feld[i]));
  Result := Ausgabe;
end;

function THeap.GetLaenge: integer;
begin
  Result := Length (Feld);
end;

procedure THeap.sink(knoten, max: Integer);
var temp : integer;
begin
  if knoten*2 < max then
  begin
    if knoten*2+1 < max then
    begin
      if Feld[knoten*2] > Feld[knoten*2+1] then
      begin
        if Feld[knoten] < Feld[knoten*2] then
        begin
          temp := Feld[knoten];
          Feld[knoten] := Feld[knoten*2];
          Feld[knoten*2] := temp;
          sink(knoten*2, max);
        end;
      end else
        begin
          if Feld[knoten] < Feld[knoten*2+1] then
          begin
            temp := Feld[knoten];
            Feld[knoten] := Feld[knoten*2+1];
            Feld[knoten*2+1] := temp;
            sink(knoten*2+1, max);
          end;
        end;
    end else
      begin
        if Feld[knoten] < Feld[knoten*2] then
        begin
          temp := Feld[knoten];
          Feld[knoten] := Feld[knoten*2];
          Feld[knoten*2] := temp;
          sink(knoten*2, max);
        end;
      end;
  end;
end;

end.


Tilo - Mo 10.09.07 17:45
Probier es mal so:

Delphi-Quelltext 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
 
procedure THeap.CreateHeap();
var max, min, i : Integer;
begin
  max := high(Feld) ;
  min := low(Feld);
  for i := (max div 2) downto min do
    begin
      if Feld[i] < (Feld[i*2] or Feld[i*2+1]) then
        sink(i, max);
    end;
end;


procedure THeap.sink(knoten, max: Integer);
var maxi : integer;//Index des Größten Kindes
    temp:integer;
    lk,rk:integer;//index der Kinder
begin
  lk=knoten*2; rk=lk+1;// sollte es Fehler geben probiere mal "lk=(knoten+1)*2-1;"

  if lk < max then //Linkes Kind Existiert
  begin
    maxi=lk;//Annahme lk ist max.
    if rk < max then //rechtes Kind Existiert
     if Feld[rk]>Feld[lk] then //rechte Kind ist größer als linkes Kind
      maxi=rk;
    if Feld[maxi] >Feld[knoten] then //Vater ist kleiner als größtes Kind
    begin
     temp=Feld[knoten];
     Feld[knoten]=Feld[maxi];
     Feld[maxi]=temp;
     sink(maxi,max);
    end;
  end;
end;

end.


Ich kann es im Moment nich testen da ich kein Delphi installiert habe -> Lappi war auf Reparatur


Wegi - Mo 10.09.07 18:15
Ok, danke so funktioniert es, musste noch an der Ausgabe etwas ändern, damit er die erste Stelle nicht ausgibt. Jedenfalls vielen Dank für alles. Problem gelöst.

Funktionierender Code:


Delphi-Quelltext 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
 
unit Unit2;

interface
uses Classes, SysUtils;

Type     THeap = class
           private
             Feld : Array of integer;
             Ausgabe : TStringList;
             procedure CreateArray ();
             procedure sink(knoten, max : Integer);
           public
             constructor Create ();
             function GetAusgabe : TStringList;
             function GetLaenge : integer;
             procedure CreateHeap();

         end;

implementation


{ THeap }

constructor THeap.Create ();
begin
  CreateArray ();                  // Zufällige Vorbesetzung
  Ausgabe := TStringList.Create ();
end;

procedure THeap.CreateArray;
var i,la : integer;
begin
  randomize;
  la := random (100) + 1;
  SetLength (Feld,la);
  for i := 1 to high(Feld) do
      Feld [i] := random (10000);
end;

procedure THeap.CreateHeap();
var max, min, i : Integer;
begin
  max := high(Feld) ;
  min := 1;
  for i := (max div 2) downto min do
    begin
      if Feld[i] < (Feld[i*2] or Feld[i*2+1]) then
        sink(i, max);
    end;
end;


function THeap.GetAusgabe: TStringList;
var
  i: Integer;
begin
  Ausgabe.Clear;
  for i := 1 to high(Feld) do
    Ausgabe.Add(IntToStr(Feld[i]));
  Result := Ausgabe;
end;

function THeap.GetLaenge: integer;
begin
  Result := Length (Feld);
end;

procedure THeap.sink(knoten, max: Integer);
var maxi : integer;//Index des Größten Kindes
    temp:integer;
    lk,rk:integer;//index der Kinder
begin
  lk := knoten*2;
  rk := lk+1;// sollte es Fehler geben probiere mal "lk=(knoten+1)*2-1;"
  if lk < max then //Linkes Kind Existiert
  begin
    maxi := lk;//Annahme lk ist max.
    if rk < max then //rechtes Kind Existiert
     if Feld[rk]>Feld[lk] then //rechte Kind ist größer als linkes Kind
      maxi := rk;
    if Feld[maxi] >Feld[knoten] then //Vater ist kleiner als größtes Kind
    begin
     temp := Feld[knoten];
     Feld[knoten] := Feld[maxi];
     Feld[maxi] := temp;
     sink(maxi,max);
    end;
  end;
end;

end.


Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2026 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!