AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

Heapsort Verfahren

Ein Thema von OrallY · begonnen am 30. Apr 2003
Antwort Antwort
Benutzerbild von OrallY
OrallY

Registriert seit: 29. Apr 2003
268 Beiträge
 
#1

Heapsort Verfahren

  Alt 30. Apr 2003, 14:51
Das Heapsort-Verfahren ist eines unter vielen Sortierverfahren. Es benutzt, um es in ein Bild zu fassen, einen Baumdiagramm mit folgenden Voraussetzungen:
Jeder Knoten hat höchstens 2 Nachfolgerknoten, wobei keiner der beiden Nachfolger größer sein darf, als der Knoten selbst. Ist diese Vorausetzung für jeden Knoten des Baumes gegeben, befindet sich an der Wurzel des Baumes der größte Wert.

Eine kleine "Skizze" um zu verdeutlichen, wie der Array in den Baum transferiert ist (hoffentlich kann man es erkennen ):
Code:
Syntax und Legende:
   o:Index

   o = knoten
  Index = Index des Werts im Array, der diesem Knoten zugeteilt wird
  /\ = Verbinungslinien die die Zugehörigkeit der Knoten andeutet


                                      o:0
                                    /   \ 
                                   o:1   o:2
                                 / \     / \
                                o:3 o:4 o:5 o:6
                               / \ / \ / \ / \
                                     usw.
Heapsort eignet sich vorallem für größere Datenmengen, erziehlt bei einer Vorsortierung sogar ein besseres Ergebnis als Quicksort, da es durch den Baumaufbau so oder so jede evtl. vorhandene Ordnung wieder zunichte macht . Qicksort weist schon bei einer geringen Vorsortierung eine schlechtere Laufzeit auf, als bei einem völlig unsortierten Array/Datenpacket.

Der Code:
Delphi-Quellcode:
{die AdjustHeap Prozedur ist dafür verantwortlich, die Baumstruktur aufzubauen}

procedure AdjustHeap(n: integer; var Data: array of integer; knot: integer);
var
  temp_knot_value, subknot: integer;
begin
  temp_knot_value := Data[knot];

  while knot < n div 2 do
  begin
    subknot := 2*knot+1; //Formel um Unterknoten herauszufinden, wobei 2*knot+2 der 2. Unterknoten ist.

    {Überprüfung, welcher der beiden Unterknoten größer ist; subknot wird der Index des größeren zugewiesen.}
    if (subknot < n - 1) and (Data[subknot] < Data[subknot + 1]) then
      Inc(subknot);


    {Wenn der größere der beiden Unterknoten nicht größer als der betrachtete Knoten ist, breche die Schleife ab ...}
    if temp_knot_value >= Data[subknot] then
      break;


    {... andernfalls tausche die Werte.}
    Data[knot] := Data[subknot];

    {Ein neuer Knotenindex wird gesetz, um eine Ebene im Baum tiefer zu wandern und den Unterknoten unter den gleichen Aspekten zu betrachten.}
    knot := subknot;

  end;
  Data[knot] := temp_knot_value;
end;

{eigentlich Prozedur}
procedure HeapSort(var Data: array of integer);
var
  knot, temp, i: integer;
begin
  i := Length(Data);

{Erstsortierung des Heaps/Baumes}
  knot := i div 2; //begonnen wird mit einem Knoten in der Mitte des Arrays
  while knot > 0 do
  begin
    Dec(knot);
    AdjustHeap(i, Data, knot);
  end;

  while i >= 0 do
  begin
    
    {da nun das erste Feld den größten Wert enthält, wird dieser mit dem letzten Feld vertauscht ...}
    temp := Data[0];
    Data[0] := Data[i];
    Data[i] := temp;

    AdjustHeap(i, Data, 0);
    Dec(i); {... und da der größte Wert nun am Ende steht, also schon einsortiert ist, wird der zu betrachtenden Bereich auf den noch unsortierten Teil festgesetzt}
  end;
end;
Bei jedem durchlauf von AdjustHeap ist der Wert mit dem Index 0 der größte Wert. Also wird er mit dem letzten Feld vertauscht. Da nun der Größte Wert am Schluss des Array steht, also schon einsortiert ist, braucht man dieses Feld nicht mehr in die Suche mit einzubeziehen. So erlangt der Array von hinten nache Vorne seine Ordnung.


Ich hoffe ich habe mit meinen Kommentaren helfen können, das nicht ganz so leicht zu durchblickende Verfahren verständlich zu machen. Am besten versteht man es, wenn man den Algorithmus Step by Step selbst mit Papier und Bleistift an einem kleinen Baum nachvollzieht. Ihr werdet staunen .
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 16:36 Uhr.
Powered by vBulletin® Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2019 by Daniel R. Wolf