Umsetzung eines Sortier algorithmus

[hendy]

Nu ja ich habe in Informatik die Aufgabe bekommen, einen Sortieralgorithmus zu programmieren, den ich schon als Struktogramm habe.
Dabei zeigen sich allerdings ein paar schwierigkeiten mit Laz.
hier ist der code, er schmeißt mir immer SIGSEV entgegen

Code: Alles auswählen

function Groesser( i:integer):Integer;
  procedure Aufruecken(i:integer);
  procedure Tournamentsort();
var
  Fenster: TFenster;
  Sortiere: array of integer;
  Elemente:Integer;
implementation
 
 
{ TFenster }
 
procedure Tournamentsort();
var i,j,k,temp:integer;
var Sort:array of integer;
begin
  setlength(Sort,Elemente*2);
  for i:= Elemente-1 to Elemente*2-1 do
  Sort[i]:=Sortiere[i-(Elemente-1)];
  for i:= Elemente-2 downto 0 do
  begin
    temp:=Groesser(i);
    Sort[i]:=Sort[temp];
    Sort[temp]:=-1;
    Aufruecken(i);
  end;
  for j:=0 to Elemente-1 do
  begin
    Fenster.Ausgabe.Items.Add('Ausgabe: '+inttostr(Sort[0]));
    Sort[0]:=-1;
    Aufruecken(0);
  end;
  for i:=0 to 2*Elemente do
  Fenster.Ausgabe.Items.Add(inttostr(i)+' '+inttostr(Sort[i]));
end;
//function Groesser bestimmt den Größeren nachfolgeknoten
//und gibt dessen position zurück
function Groesser( i:integer):Integer;
begin
  if Sortiere[2*i+1] >= Sortiere[2*i+2] then
     Result:= 2*i+1
     else
     Result:=2*i+2;
end;
 
//function Aufruecken fängt bei Position i an
//die leeren Stellen des Baumes
//nach Tournamentregeln zu füllen(mit Kinderknoten)
procedure Aufruecken(i:integer);
var temp:Integer; //Hier wird die Position des größeren Elements gespeichert
begin
  if  (2*i+2 <= 2*Elemente) then
  begin
    if (not ((Sortiere[2*i+1] = -1) and (Sortiere[2*i+2] = -1)))
    and (Sortiere[i] <> -1) then
    begin
      temp := Groesser(i);
      Sortiere[i]:= Sortiere[temp];
      Sortiere[temp]:=-1; //"Leeren" des Feldes
      Aufruecken(temp);
    end;
  end;
end;
 
procedure TFenster.SortierenClick(Sender: TObject);
var i:integer;
begin
randomize;
  Setlength(Sortiere,16);
  Elemente := 16;
  for i:=0 to 16 do
  begin
    Sortiere[i]:=random(100);
    Ausgabe.Items.Add(inttostr(i)+' '+inttostr(Sortiere[i]));
  end;
    Tournamentsort();
end;

TFenster heißt die Form

[Socke]

Wenn du eine SIGSEGV erhältst, erhälst du üblicherweise auch eine Zeilennummer!
Ein paar allgemeine Tipps zum Programmierstil:

• Wenn eine Funktion mit irgendetwas etwas tun soll, dann sollte irgendetwas übergeben werden
• Für einen Sortieralgorithmus sollte nur eine Funktion öffentlich sichtbar sein, alle anderen können eingebettet werden
• Auch nach einer for-Schleife, ohne begin..end kann man einrücken.
• Das Sortieren hat nichts mit deren Ausgabe zu tun

for i:=0 to 2*Elemente do ... manchmal sieht man den Index vor lauter Variablen nicht mehr:D!

[theo]

Das Problem fängt bei SortierenClick schon an.
Du reservierst 16 Elemente, loopst dann aber durch 17 (0..16).

[hendy]

oh du hast recht theo.
Und danke für die vorschläge socke

[theo]

Tipp: Schalte bei Projekteinstellungen -> Codegenerierung die Überprüfungen ein.
Bereich und Überlauf z.B. dann siehst du besser wo's jeweils knallt.

[hendy]

mmmh mach ich mal.
Bis jetzt schmeißt er immer noch SIGSEV ohne Zeile, auch wenn ich 17 platz beanspruche -.-
Muss nochmal den Algorithmus überarbeiten

[Socke]

Bis jetzt schmeißt er immer noch SIGSEV ohne Zeile, auch wenn ich 17 platz beanspruche -.-
Muss nochmal den Algorithmus überarbeiten

Wenn du keine Zeile erhälst, kannst du mit F7 jeden einzelnen Schritt deines Programmes mitverfolgen. Über Ansicht->Debuggerfenster->Lokale Variablen erhälst du ein Fenster, in dem alle lokalen Variablen angzeigt werden.

[hendy]

Anscheinend hakt es hier:

Code: Alles auswählen

for j:=0 to Elemente-1 do
  begin
    Fenster.Ausgabe.Items.Add('Ausgabe: '+inttostr(Sort[0]));
    Sort[0]:=-1;
    Aufruecken(0);
  end;

Wenn ich dortt breakpoints setze, macht er das ein paar mal, und macht dann SIGSEV.
Ich bin mit dem Latein am Ende

[Euklid]

Hallo hendy,

SIGSEGV ist eine Zugriffsverletzung. Ich vermute, dass sie im "Aufruecken"-Algorithmus geschieht, da hier mit Sortiere[2*i+1] = -1 auch auf Elemente außerhalb des Arrays zugegriffen werden kann.

Hier noch ein programmiertechnischer Tipp:
Bei SIGSEGV-Fehlern einfach die heaptrc im Menü Compilereinstellungen --> Linken mit einspannen. Dann das Programm von einer Konsole aus ausführen. Beim Schließen des Programms wird dann der Aufrufstack ausgegeben. Über diesen kann die Zugriffsverletzung sehr gut nachvollzogen werden - unter anderem werden Dateien und Zeilennummern, die mit dem Fehler in Verbindung stehen, ausgegeben.

Viele Grüße, Alexander

[hendy]

ich habe das heute nochmal anders umgesetzt, aber nun ist das Ergebnis, dass nur das höchste Element an der ersten stele steht, der rest ist mit -1 gefüllt, das sollte eigentlich nicht sein.
Kann mir jemand helfen?

Code: Alles auswählen

var
  Fenster: TFenster;
  Sortiere: array of integer;
  Sort:array of integer;
  Elemente:Integer;
implementation
 
 
{ TFenster }
 
procedure Tournamentsort();
var temp,Ausgegeben,i:integer; //Zwischenspeicher für Position
begin
  Ausgegeben := 0;
  setlength(Sort,Elemente*2-1);
  for i:= Elemente-1 to Elemente*2-2 do
  begin
    Sort[i]:=Sortiere[i-Elemente+1];
    Fenster.Ausgabe.Items.Add('Eingabe bei '+inttostr(i)+': '+
    inttostr(Sort[i]));
  end;
  for i:= Elemente-2 downto 0 do
  begin
    Fenster.Ausgabe.Items.Add('Prev: '+inttostr(Sort[i]));
    temp:=Groesser(i);
    Sort[i]:=Sort[temp];
    Sort[temp]:=-1;
    Aufruecken(temp);
 
  end;
  while Ausgegeben < Elemente do
  begin
    Fenster.Ausgabe.Items.Add('res #'+inttostr(Ausgegeben)+' '+
    inttostr(Sort[0]));
    Sort[0]:=-1;
    Aufruecken(0);
    inc(Ausgegeben);
  end;
end;
//function Groesser bestimmt den Größeren nachfolgeknoten
//und gibt dessen position zurück
function Groesser( i:integer):Integer;
begin
  if not(i*2+2 > Elemente*2) then
  begin
    if Sort[2*i+1] >= Sort[2*i+2] then
       Result:= 2*i+1
       else
       Result:=2*i+2;
  end;
  if Sort[Result] = 0 then
  Result:=i;
end;
 
//function Aufruecken fängt bei Position i an
//die leeren Stellen des Baumes
//nach Tournamentregeln zu füllen(mit Kinderknoten)
procedure Aufruecken(i:integer);
var temp:Integer; //Hier wird die Position des größeren Elements gespeichert
begin
  if  not (2*i+2 > 2*Elemente) then
  begin
    if  not((Sort[2*i+1]<> -1) and (Sort[2*i+2] <> -1)) then
    begin
      if Sort[i] = -1 then
      begin
        //Fenster.Ausgabe.Items.Add('Vorher #'+inttostr(i)+' = '+inttostr(Sort[i]));
        temp := Groesser(i);
        Sort[i]:= Sort[temp];
        Sort[temp]:=-1; //"Leeren" des Feldes
        {Fenster.Ausgabe.Items.Add('Nachher #'+inttostr(i)+' = '+
        inttostr(Sort[i]));
        }Aufruecken(temp);
      end;
    end;
  end;
end;
 
procedure TFenster.SortierenClick(Sender: TObject);
var i:integer;
begin
randomize;
  Setlength(Sortiere,16);
  Elemente := 16;
  for i:=0 to 15 do
  begin
    Sortiere[i]:=random(100);
  end;
    Tournamentsort();
end;