Entwickler-Ecke :: Thema anzeigen

sveno - So 30.01.05 20:13
Titel: Heapsort

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-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:

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

Gausi - So 30.01.05 20:31

Zu den Laufzeiten:

Sortieren einer Folge mit N Elementen:

Quelltext

1:
2:
3:
4:

           Bester Fall      | Mittlerer Fall | Schlimmster Fall
Quicksort:   N*log(N)             N*log(N)           N^2
Mergesort:  N oder N*log(N)       N*log(N)         N*log(N)
Heapsort:    N*log(N)             N*log(N)         N*log(N)

Bei Mergesort kommt es auf die Variante an, ob du eine Vorsortierung ausnutzt oder nicht.

Dein Code produziert etwas, was in etwa N^2 Zeit benötigt.

Zum Heapsort:
Das geht so nicht. Zuerstmal musst du deine Zahlenfolge in einen Heap umwandeln. In einem Heap gilt immer a[i]>=a[2*i+1] und a[2*i+2] (erster Index: 0)

Anschaulich kann man sich einen Heap als Baum vorstellen:

Quelltext

1:
2:
3:
4:
5:
6:

  
          10       Index: 0
        /    \ 
       8      7    Index: 1   2
      / \    / \
     3  4   6   0  Index: 3 4 5 6

Dazu benötigst du am besten eine Methode "versickern", die in der Mitte des Zahlenfeldes anfängt, und die zu kleinen Elemente nach unten vertauscht, bis man zuletzt das erste Element nach unten versickert hat.

Dann fängt der Sortiervorgang an. Dazu vertauschst du das erste Element mit dem letzten, und lässt anschließend das neue erste Element versickern. Bedenke dann, dass der eigentliche Heap dann um eins kleiner geworden ist, d.h. die Methode versickern muss wissen, wo sie mit dem Versickern aufhören muss.

sveno - Di 01.02.05 15:18

So, habe jetzt den heapsort neu geschrieben.

Er sortiert korrekt, ist schneller als mein vorheriger aber imme rnoch nicht schneller als quick oder mergesort. Woran liegt das?

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:

                      {Heapsort}

procedure versickere(zahl,ende: integer);
begin
 IF (2*zahl+1) <= ende THEN
 begin
  IF sortfeld[2*zahl] > sortfeld[2*zahl+1] THEN
  begin
   IF sortfeld[2*zahl] > sortfeld[zahl] THEN
   begin
    tausche(sortfeld[2*zahl],sortfeld[zahl]);
    versickere(2*zahl,ende);
   end;
  end ELSE
   IF sortfeld[2*zahl+1] > sortfeld[zahl] THEN
   begin
    tausche(sortfeld[2*zahl+1],sortfeld[zahl]);
    versickere(2*zahl+1,ende);
   end;
 end ELSE
  IF (2*zahl) <= ende THEN
   IF sortfeld[2*zahl] > sortfeld[zahl] THEN
    tausche(sortfeld[2*zahl],sortfeld[zahl]);
end;

procedure heap_sort;
var i: integer;
begin
 //Heap Bedingung wir hergestellt
 FOR i := (anzahl DIV 2) DOWNTO 1 DO
  versickere(i,anzahl);
 //Zahlenreihe wird sortiert
 FOR i := (anzahl - 1) DOWNTO 1 DO
 begin
  tausche(sortfeld[1],sortfeld[i+1]);
  versickere(1,i);
 end;
end;

Gruss Sven

Gausi - Di 01.02.05 16:31

Ein bissel Geschwindigkeit könntest du rausholen, wenn du nicht rekursiv, sondern iterativ versickerst, also anstelle der rekursiven Aufrufe eine Schleife drin hast.

Prinzipiell schneller ist Heapsort aber nicht als Quick- oder Mergesort. Diese 3 Sortierverfahren haben im Mittel alle eine Laufzeit von N*log(N), d.h. wenn man z.B. 1024 Zahlen sortieren möchte, dann werden ungefähr 1024*10=10.240 Vergleiche durchgeführt. 'Ungefähr' bedeutet dabei, dass es auch mal gut das Doppelte sein kann, oder auch das 5-fache. Aber dieser maximale Faktor (von z.B. 5) bleibt, auch wenn man 300.000MillionenMilliarden Zahlen sortieren möchte.

sveno - Di 01.02.05 16:50

Ok, aber wenn dass die Geschwindigkeit nicht bedeutend verbessert lass ichs so, mir gings hauptsächlich darum das Prinzip des heapsorts zu verstehen und ihn programmieren zu können.

Aber da stell ich mir eine neue Frage, nachdem ich nun die Sortieralgorhimten für mich abgeschlossen habe. Warum ist bei manchen Algorhitmen eine rekursive und bei anderen eine iterative Programmierung besser? Das verstehe ich nicht. Gibts da irgendwo im Forum einen Thread zu?

Gruss sven

Gausi - Di 01.02.05 17:08

Das liegt an der Art des Verfahrens. Was will man z.B. bei Bubblesort großartig rekursiv machen? Das geht alles mindestens genauso gut iterativ. Und bei AuswahlSort nimmt man immer das Minimum und packt das nach vorne. Geht auch wunderbar mit zwei verschachtelten Schleifen.
Bei Quicksort lautet eine Beschreibung ja so: Teile die Folge in zwei Folgen auf, und sortiere beide Folgen mit Quicksort. Das geht am einfachsten rekursiv, weil die Beschreibung rekursiv ist.

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!