Autor |
Beitrag |
sveno
Beiträge: 40
|
Verfasst: So 30.01.05 20:13
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
Beiträge: 8535
Erhaltene Danke: 473
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: 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.
_________________ We are, we were and will not be.
|
|
sveno
Beiträge: 40
|
Verfasst: So 30.01.05 22:53
Was ist denn eine Methode?
|
|
BenBE
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
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
Beiträge: 8535
Erhaltene Danke: 473
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
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
|
Verfasst: Mo 31.01.05 17:54
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
|
Verfasst: 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?
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:
|
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 FOR i := (anzahl DIV 2) DOWNTO 1 DO versickere(i,anzahl); FOR i := (anzahl - 1) DOWNTO 1 DO begin tausche(sortfeld[1],sortfeld[i+1]); versickere(1,i); end; end; |
Gruss Sven
|
|
Gausi
Beiträge: 8535
Erhaltene Danke: 473
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
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
|
Verfasst: 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
Beiträge: 8535
Erhaltene Danke: 473
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
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.
|
|
|