Erklärung - Heapsort (sift)

[Janine]

Hallo !

Habe diesmal eine Frage zu Heapsort, speziell die Prozedur Sift:

PROCEDURE sift (VAR f : tfeld; L,R : integer);
VAR
k : integer;
x : Byte;
begin
i := L;
k := L*2;
x := f(i);
if (k < R) and (f(k+1) > f(k)) then inc(k);
while (k <= R) and (f(k) > x) do
begin
f(i) := f(k);
i := k;
k := k*2;
if (k < R) and (f(k+1) > f(k)) then inc(k);
end;
f(i) := x;
end;

Was passiert in dieser Prozedur Sift ?


Vielen Dank im voraus und viele Grüße !
Janine

[TGGC]

Es wird ein Array übergeben, was den Binärbaum enthält, sowie zwei Knoten im Baum (L,R). Dann rücken die größeren Kindelemente unter L nach oben, bis es bei R ankommt oder kleiner als das ehemalige Element von L ist. Das kommt dann wiederum dort runter. Ich denke einfach mal Beispiel aufmalen und durchgehen.


Bye, TGGC

[Janine]

Okay, und was passiert dann in der procedure heapsort ?




PROCEDURE heapsort (VAR f : tfeld);
VAR
index : integer;
x : Byte;
begin
L := (max div 2) + 1;
R := max;
while (L > 1) do {WHILE - DO - Schleife}
begin
dec(L); //decrease=verringert den Wert einer Variablen um 1 ???
sift(f,L,R);
end;
for index := R downto 1 do {FOR - DOWNTO - DO - Schleife}
begin
tausch(f,1,index);
sift(f,1,index-1);
end;
end;




Vielen Dank schonmal und viele Grüße !
Janine

[DanDanger]

Hallo,

Im Netz gibt es tausende Seiten, die alle möglichen Sortierverfahren
(Shell-Sort, Quick-Sort, und was es sonst noch so alles gibt) extrem gut erklären (mit Bildern, animierten JAVA-Applets, Beispielcodes, etc.).

Schau mal hier :
-> Wikipedia Portal zu diversen Sortieralgorithmen :
http://de.wikipedia.org/wiki/Sortieralgorithmen

-> Ne' ganze HP, die sich nur um Sortieralgorithmen dreht :
http://www.sortieralgorithmen.de/

-> .... und natürlich :
http://www.google.de (ganz besonders nützlich, wenn man schon den Namen des Algo. kennt, über den man mehr Wissen möchte :)).


Gruss
DanDanger

[Janine]

Hallo !

Habe mir schon so viele Seiten durchgelesen, nur hätte ich gerne gewusst, an welcher Stelle in diesem Verfahren:

- ein Knoten mit seinem Nachfolgeknoten verglichen wird
- das erste Element mit dem letzten Element getauscht wird
- wo der Baum nur noch aus zwei Elementen besteht

?


Vielen Dank und viele Grüße !
Janine

[TGGC]

Siehst ja, das die Leute hier nicht so Plan haben....

ein Knoten mit seinem Nachfolgeknoten verglichen wird => f(k+1) > f(k)
das erste Element mit dem letzten Element getauscht wird => wird es nirgends im gezeigten Code
wo der Baum nur noch aus zwei Elementen besteht => wenn R/L die entsprechenden Werte erreichen


Bye, TGGC

[Janine]

Vielen Dank, das hat mir sehr weitergeholfen. :)


PS: Ich bin erst am lernen (d.h. nicht in Schule).


Viele Grüße !
Janine

[Janine]

Hallo !

Hätte noch einmal eine Frage zu Sift (oben).

Wieso gibt es dort zweimal if (k < R) and (f(k+1) > f(k)) then inc(k); ?

Es wird dort doch verglichen, welcher der beiden Nachfolger eines Knotens größer ist und dann getauscht, falls der größere Nachfolger auch größer als sein Knoten ist. Oder ?

Bedeutet das zweite Mal if (k < R) and (f(k+1) > f(k)) then inc(k); dann, dass falls es zu einem Tausch mit dem Nachfolger kommt, der ehemalige Knoten mit seinen neuen Nachfolgern noch einmal verglichen wird und gegebenfalls weiter nach unten sickert, bis entweder beide Nachfolger kleiner, oder der Knoten am Ende angelangt ist ? D.h. die Prozedor beginnt noch einmal links von der Mitte des Feldes ?


Vielen Dank und viele Grüße !
Janine