Heapsort

[sveno2k5]

Hallo, hab gerade mal probiert den Heapsort zu programmieren, aber denke ich habe die Funktionsweise nicht ganz verstanden. Der soll doch noch schneller sein als qick und mergesort oder? Bei meinem Heapsort sortiert er die Zahlenreihe zwar korrekt, aber in einer viel langsameren Zeit als quick und mergesort. Hier der Code:

Delphi-Quellcode:

procedure heap_sort;
var i,y: integer;
begin
 IF anzahl > 1 THEN
 begin
  FOR i := (Anzahl - 1) DOWNTO 1 DO
  begin
   FOR y := (i+1) DIV 2 DOWNTO 1 DO
   begin
    IF sortfeld[y] < sortfeld[2*y] THEN
     tausche(sortfeld[y],sortfeld[2*y]);
    IF (sortfeld[y] < sortfeld[2*y+1]) AND ((2*y+1) <= (i+1)) THEN
     tausche(sortfeld[y],sortfeld[2*y+1]);
   end;
   tausche(sortfeld[1],sortfeld[i+1]);
  end;
 end;
end;

Kann mir jemand sagen wo ich die Funktionsweise falsch verstanden habe?

Gruss Sven

[Binärbaum]

Was glaubst du wohl, warum Quicksort so heißt? :wink:
Im Mittel hat Quicksort die beste Zeitkompleität aller (mir bekannten) Sortieralgorithmen, also ist Quicksort auch besser als Heapsort (zumindest bei großen Datenmengen).
Bei Heapsort muss man ja nach jedem Durchlauf den "Heap" neu sortieren, was ziemlich aufwendig sein kann. Darum würde ich dir Quicksort empfehlen, wenn's schnell gehen soll. Falls Zeit nicht so die große Rolle spielt, kannst du aber auch Heapsort verwenden.

MfG
Binärbaum

[Eichhoernchen]

Quicksort ist nicht immer schneller als Heapsort,
sortiere mal ein sortiertes Array mit Heapsort und mit Quicksort, du wirst sehen das Quicksort zum "slowsort" wird.
Quicksort hat den vorteil das es große Datenmengen sehr schnell sortieren kann, wenn jedoch im array schon eine strucktur herrscht, z.B. es ist schon sortiert, ist es sehr lahm, da ist heapsort besser da es das Array auf heapeigenschaft bringt, d.h.
a[i] <= a[2*i]
a[i] <= a[2*i+1]

Und heapsort ist nur minimal langsamer als quicksort, d.h. ich würde lieber heapsort nehmen da es nie langsam werden kann!