Bottom Up Heapsort direkt auf array

[Hybrid666]

Hi,

wir sollen an der Uni den Bottom Up Heapsort algorhytmus schreiben, sollen allerdings KEINEN Baum aufbauen, sondern direkt auf dem array arbeiten.
Kann mir einer sagen wie das genau geht? weil ich finde immer nur anleitungen und beispiele auf einem Baum. Klasse wäre auch ein Delphi beispiel (keine angst, will nicht das ihr meine aufgaben löst, ich muss das ohnehin in einer anderen sprache machen, aber ich brauche einfach was um mir das zu veranschaulichen). Und dann noch eine generelle Frage zu dem algo: Wie lange muss ich das sortierverfahren (austauschen und absickern) ausführen, bis der array sortiert ist? So oft, wie ich elemente habe, nur halb so oft oder muss ich jedesmal manuell prüfen, ob er sortiert ist (was keinen sinn machen würde, weil wir den bottom-up machen sollen wegen weniger vergleichen als heapsort).

EDIT: Habe noch was vergessen: Als vergleichsoperatoren dürfen wir NUR kleiner als verwenden, also vergleich mit = oder > sind nicht möglich, da wir ein genereisches paket machen sollen und doppelte elemente dürfen NICHT im array sein (davon kann man von vornerein ausgehen).

Danke für eure hilfe,

MfG Hybrid666

[gammatester]

Im Kapitel 4 der Vorlesung http://www.informatik.uni-freiburg.d...o2/slides.html wird unter anderem Bottom-up Heapsort beschrieben. Da wird zwar ein Sortable a verwendet, man kann's aber leicht auf Arrays übertragen. Ansonsten schau mal hier, wenn's nicht klappt.

Gruß Gammatester

[Hybrid666]

genau der übertrag von einem baum auf einen array ist mein problem, ich weiß nicht wie ich jeweils die richtigen "söhne" im array finden soll. aber danke erstmal für die vorlesungsfolien!

[gammatester]

Zitat:

Zitat von Hybrid666

genau der übertrag von einem baum auf einen array ist mein problem, ich weiß nicht wie ich jeweils die richtigen "söhne" im array finden soll. aber danke erstmal für die vorlesungsfolien!

Die Indexrechnung dafür ist doch angegeben. In meiner Implementation im Link habe ich das nur übertragen, ich mußte allerdings "nur" implementieren nicht unbedingt 100% verstehen :wink:

Gruß Gammatester

[Hybrid666]

ahhhh okay, hatte ich überserhen :D

ist das der ganze code? oder muss ich vorher noch eine heapsortierung machen? (also das der array ein heap ist)

[gammatester]

Zitat:

Zitat von Hybrid666

ist das der ganze code? oder muss ich vorher noch eine heapsortierung machen? (also das der array ein heap ist)

Wahrscheinlich hat's sich schon erledigt, aber: Ja, pushdown wird wie beim normalen heapsort eingesetzt. Pseudocode:

Delphi-Quellcode:

for i:=n div 2 downto 1 do pushdown(i,n);
for i:=n downto 2 do begin
  swap(1,i);
  pushdown(1,i-1);
end;

Gruß Gammatester