Frage zu HeapSort

[Scharfrichter]

Hi,

ich darf bald eine 12-Seitige Facharbeit für Informatik an meinen Fachlehrer abliefern, wobei bald relativ ist, ich hab glaube ich noch so um die 4 Wochen, aber egal. Das Rahmenthema meiner Facharbeit ist wie ihr euch bestimmt denken könnt das Sortierverfahren Heapsort und ich soll zusätzlich zu dem theoretisch/schriftlichen Teil noch ein kleines Programm basteln was den Alogrithmus veranschaulicht und seine funktionsweise erklärt. Jetzt wusste ich aus dem Unterricht nur was ein Heap ist und wie diese aufgebaut ist und den Algorithmus soll ich selber verfassen. Jetzt hab ich mir in den letzten Tagen x-Seiten von literatur aus nem Buch und ausm Netz zu dem Thema reingezogen und hab gestern ne kleine Testumgebung gebaut und versucht den Algorithmus selbst zu proggen, hat eigentlich auch fast alles perfekt geklappt, nur dieses "fast" steht mir im Wege. Hier erstmal der code fürs Versickern und für den Heapsort selber

Delphi-Quellcode:

Procedure TSSBaum.Versickern(knot,niveau: integer);
var tempknot,subknot: integer;
Begin
  tempknot := self.Value(knot);
  While knot < round(niveau / 2) do
    Begin
      subknot := 2*knot;
      If (subknot <= N -1) and (self.Value(subknot) < self.Value(subknot+1)) then
        Inc(subknot);
      If tempknot >= self.Value(subknot) then
        break
      else
        self.Note(knot,self.Value(subknot));
      knot := subknot;
    end;
  self.Note(knot,tempknot);
end;

Procedure TSSBaum.Heapsort();
var
  knot, temp, i, t,m : integer;
begin
  i := N;
  knot := i div 2;
  For t :=  (n div 2) downto 1 do
    versickern(t,i);
   For m:= N downto 1 do
    Begin
      temp := self.value(1);
      self.Note(1,self.value(m));
      self.Note(m,temp);
      versickern(1, m-1);
    end;
end;

Erklärung: Also mein Heapsort greift auf ein Array als abgeleitetes Objekt einer anderen Unit zu, deswegen kann ich das Array an sich nur über festgelegte Befehle die mir mein Lehrer vorgegeben hat ansteuern, dass sind: Empty, Value(K: integer):integer und note(k,b: integer); Empty überprüft ob, dass Array leer ist, value gibt für die den index k den jeweiligen integer wert des array-items zurück und note schreibt auf den index k den wert b. Jetzt hab ich dazu ne Testumgebung gebastelt die erstmal nur über ein festes 31iger Array verfügt was in der Heapunit festgelegt ist. Das Array wird Anfangs mit zufälligen Zahlen voll gestopft und soll dann über den Aufruf von Heapsort; geordnet werden. Das Ganze klappt auch wunderbar, nur so ca. bei jedem 3ten oder 4ten zufällig erzeugten Array sind die letzten beiden(also die kleinsten) Werte im Array nicht richtig sortiert wurden, da steht dann mal ne 3 vor na 9 oder ne 2 vor na 8(Der größte Index 31 beherbergt den größten Wert und den kleinste Index 1 den niedrigsten Wert). Ich hab keine Ahnung warum das Heapsort mal perfekt klappt und alles wunderbar geordnet ist und mal die kleinsten Werte nicht richtig sortiert sind.
Wenn es geklappt haben sollte, ist anbei die .exe zur Testumgebung. Einfach im Menü oben auf Belegung->Zufällig und dann unter Funktionen-> Heapsort, dann sollte links im Label der Array angezeigt werden, mal mehr mal weniger geordnet.
Ich hoffe ihr könnt mir sagen was für einen Fehler ich mache.

[Scharfrichter]

Hier mal die dazu gehörigen Units damit ihr euch ein gesammt Bild machen könnt von dem Mist den ich da wieder verzapft habe. Dazu ist zu sagen, dass die Unit Sbaum nicht verändert werden darf und das ich nur über die Unit SSBAum arbeiten kann, um neue Funktinen hinzuzufügen wie z.B. Das Sortieren, deswegen geht der direkte Zugriff auf das Array auch ehr nicht.

[Klaus01]

Na, wenn Du schon Literatur gelsen hast..

anbei ein Link zu einem Nassi-Schneidermanndiagramm zum Thema heapsort:

http://www.bildung.hessen.de/abereic...t/heapalg.html

Vielleicht bringt es ja etwas Licht ins Dunkle

grüße
Klaus

[Scharfrichter]

Danke für den Tipp, dass Diagramm ist zwar ganz schön gestaltet und präsentiert Heapsort auch sehr gut, nur zur Heapsort Logik, also was dahitner steckt etc., hab ich eigentlich keine Probleme mehr, es geht jetzt nur um die Implementation wie ich sie zurvor beschreiben hab.