Sitemap
Mitgliederliste Mitgliederliste
Gruppen Gruppen
Das Team Das Team
Museum Richtlinien
Synonyme Synonyme
Hilfe
Login
Registrieren
Heapsort "suboptimal" gelungen und Fehlerhaft
in Sonstige Programmierung » Algorithmen, Optimierung und Assembler
  • algorithmus
Autor Beitrag
Wegi
Hält's aus hier
Beiträge: 13

Win XP Pro
Delphi 7 Personal, Turbo Delphi 2006
BeitragVerfasst: Mo 10.09.07 08:50 
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.

markieren
ausblenden volle Höhe 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)

_________________
Zitat:
Zitat von: Ernst Waltemathe (*1935), dt. Politiker (SPD)Es gibt Leute, die haben immer schon eine Lösung, bevor überhaupt ein Problem da ist.
Tilo
ontopic starontopic starontopic starontopic starofftopic starofftopic starofftopic starofftopic star
Beiträge: 1098
Erhaltene Danke: 13

Win7 geg. WInXP oder sogar Win98
Rad2007
BeitragVerfasst: Mo 10.09.07 09:03 
Wie lautet der Index des 1.Feldes? Heapsort braucht als ersten Index 1 statt 0. außer dem ist

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


immer wahr.
da auch

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

immer wahr ist führt sink immer
markieren
ausblenden 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
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 4006
Erhaltene Danke: 7

Windows 10 64 bit
C# (Visual Studio 2019 Express)
BeitragVerfasst: Mo 10.09.07 09: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 Threadstarter
Hält's aus hier
Beiträge: 13

Win XP Pro
Delphi 7 Personal, Turbo Delphi 2006
BeitragVerfasst: Mo 10.09.07 16: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:

markieren
ausblenden volle Höhe 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.

_________________
Zitat:
Zitat von: Ernst Waltemathe (*1935), dt. Politiker (SPD)Es gibt Leute, die haben immer schon eine Lösung, bevor überhaupt ein Problem da ist.
Tilo
ontopic starontopic starontopic starontopic starofftopic starofftopic starofftopic starofftopic star
Beiträge: 1098
Erhaltene Danke: 13

Win7 geg. WInXP oder sogar Win98
Rad2007
BeitragVerfasst: Mo 10.09.07 18:45 
Probier es mal so:
markieren
ausblenden volle Höhe 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 Threadstarter
Hält's aus hier
Beiträge: 13

Win XP Pro
Delphi 7 Personal, Turbo Delphi 2006
BeitragVerfasst: Mo 10.09.07 19: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:

markieren
ausblenden volle Höhe 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.

_________________
Zitat:
Zitat von: Ernst Waltemathe (*1935), dt. Politiker (SPD)Es gibt Leute, die haben immer schon eine Lösung, bevor überhaupt ein Problem da ist.

Entwickler-Ecke.de rev.276b99aea638 based on phpBB
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!

Impressum | Datenschutzerklärung | Kontakt zum Team