Heapsort

sveno · Beiträge: 40

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:

markieren

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 · Verfasst: So 30.01.05 20:31

Zu den Laufzeiten:

Sortieren einer Folge mit N Elementen:

markieren

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:

markieren

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.

_________________
We are, we were and will not be.

sveno · Beiträge: 40

Was ist denn eine Methode?

BenBE · Verfasst: So 30.01.05 23:38

Bitte gucke Dir dazu die DOH, die FAQ-Sparte oder einschlägige Einsteiger-Tutorials an.

_________________

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Gausi · Verfasst: Mo 31.01.05 16:57

Mit Methode meine ich Prozedur oder Funktion.

_________________
We are, we were and will not be.

sveno · Beiträge: 40

Gausi hat folgendes geschrieben:

Mit Methode meine ich Prozedur oder Funktion.

Ja, hab ich nachdem ich gegoogelt habe auch gemerkt, wusste doch das ich das Wort irgendwann in der 11 mal gehört hatte^^
Danke.

sveno · Beiträge: 40

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?

markieren

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 · Verfasst: 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.

_________________
We are, we were and will not be.

sveno · Beiträge: 40

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 · Verfasst: 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.

_________________
We are, we were and will not be.

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme