#1 10.08.2006 14:09:42

Pollux
Newbie
Registriert: 10.08.2006
Beiträge: 5

[Algo] Heapsort

Hallo zusammen,

Ich habe vor kurzem mein erstes Tutorial über den Heapsort-Sortieralgorithmus fertiggestellt. Verfügbar ist das ganze unter folgendem Link:

http://www.michael-nett.info/?p=12

Da er ursprünglich für GameDev.net gedacht war ist er in Englisch verfasst. Weiterhin sind diverse Illustrationen und C++ Sourcecode enthalten.

Für konstruktive Kritik wäre ich sehr dankbar smile


http://www.michael-nett.info/
"The badness of a movie is directly proportional to the number of helicopters in it." - Dave Berry
Tutor für "Advanced Software Engineering" WS06/06

Offline

 

#2 10.08.2006 15:12:33

JorEl
ExtremeMember
Registriert: 29.01.2005
Beiträge: 894

Re: [Algo] Heapsort

Ich hab das Tutorial mal überflogen und hier meine Anmerkungen dazu:

1) Es ist sehr gut geschrieben, schön strukturiert und sicher auch verständlich erklärt - wobei es natürlich schwierig ist das objektiv zu beurteilen, wenn man den Algorithmus ohnehin kennt.

2) Was ich als eher irritierend empfunden habe... am Anfang wird nirgends die Laufzeit in der enstprechenden Notation angegeben - ich weiss, das machst du dann am Ende in einem eigenen Kapitel, aber auch in einem tutorial schadet (wie auch in einer wissenschaftlichen Publikation) ein kurzes abstract nicht, in dem man solche Informationen unterbringen kann - denn genau dafür ist es ja gedacht, man soll auf einen Blick sehen ob das paper/das tutorial das behandelt was man braucht und dann entscheiden ob es Sinn macht es zu lesen.

3) Das ist etwas, das ich für alle anmerke die dieses Tutorial lesen und den Algorithmus verwenden wollen: in der Praxis hat sich gezeigt, dass Quicksort das schnellere Verfahren ist - aber wie schon richtig im Artikel steht gibt es Situationen, in denen dies nicht der Fall ist. Sind jedoch äusserst wenige, gegebenenfalls muss man je nach Datenset entscheiden was sinnvoll ist, aber im Normalfall ist man mit Quicksort gut beraten.

Fazit: sehr gutes Tutorial, klar strukturiert, sprachlich gut formuliert und vor allem auch überraschend ausführlich für einen so simplen Algorithmus - eine Spur mehr Objektivität beim Vergleich mit Quicksort wäre vielleicht noch möglich, denn das könnte für Leser die nicht Informatik studieren/studiert haben sehr leicht zur Schlussfolgerung führen, dass Heapsort dem Quicksort prinzipiell überlegen ist - und das ist nicht der Fall.

JorEl


Jesus hat gesagt - selig sind die, die da Leid erfahren, denn sie sollen getröstet werden... Ford Prefect hat gesagt - es ist unheimlich wichtig, dass wir miteinander reden und einen trinken.

Offline

 

#3 10.08.2006 15:24:37

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: [Algo] Heapsort

Ideal ist eigentlich der Introsort-Algorithmus. Das ist ein Quicksort der auf Heapsort umspringt, wenn er in den O(n^2) Fall hineinzulaufen droht. Also quasi ein Quicksort mit garantierter Laufzeit O(n * log n). Er wird beispielsweise in der C++ STL eingesetzt.

Edit: Kategorie auf [Algo] geändert.


My software never has bugs. It just develops random features.

Offline

 

#4 10.08.2006 18:20:21

Pollux
Newbie
Registriert: 10.08.2006
Beiträge: 5

Re: [Algo] Heapsort

Hallo.

Ich nehme mir deine Kritik zu Herzen, JorEl. Wenn die Klausuren bestanden sind, durch die Coolcat und ich uns noch prügeln müssen, werde ich ein paar Veränderungen vornehmen.

Was den Mangel an Objektivität angeht muß ich wohl gestehen, daß du vollkommen recht hast - Das einzige das "Objektiv" war als ich den Artikel geschrieben habe, war das Ding was vorne auf meiner Kamera sitzt (Schlechter Witz ich weiß *g*). Ich denke auch daß ich bei der Überarbeitung wesentlich klarer hervorheben sollte, das der eigentlich Vorteil von Heapsort damit zusammenhängt das die Laufzeit nicht in speziellen Fällen degeneriert.

Die Diskussion bleibt natürlich offen und ich mag mehr Kritik bekommen. Falls jemand noch Rechtschreibfehler findet - die eigenen findet man nämlich immer am schlechtesten - einfach schreiben smile

Gruß,
Pollux


http://www.michael-nett.info/
"The badness of a movie is directly proportional to the number of helicopters in it." - Dave Berry
Tutor für "Advanced Software Engineering" WS06/06

Offline

 

#5 10.08.2006 18:32:42

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: [Algo] Heapsort

Naja, Rechtschreibfehler nicht direkt, aber sowas:
yada-yada-yada
Was soll das sein :?

Ansonsten die Tabelle auf der letzten Seite:
Wie kann Heapsort ein Array mit 10 Elementen in 6 Schritten sortieren? Er muss doch wenigstens einmal alle Elemente angucken.

Überings wenn man von Hand sortiert macht man Mergesort....hast wohl noch nie nen Stapel mit 500 Klausuren sortiert oder? wink  (Vorallem kann man das wunderbar rekursiv auf mehrere Leute aufteilen :mrgreen: )

Coolcat


My software never has bugs. It just develops random features.

Offline

 

#6 10.08.2006 18:42:56

Pollux
Newbie
Registriert: 10.08.2006
Beiträge: 5

Re: [Algo] Heapsort

Zitat:

yada-yada-yada

Das ist Umgangssprache smile

Zitat:

Wie kann Heapsort ein Array mit 10 Elementen in 6 Schritten sortieren?

Heapsort ownt halt wink Nein, das sind keine Erfahrungswerte sondern welche, die mit den formeln für die Laufzeit berechnet sind, also maximal qualitative Aussagen (das sollte ich allerdings auch explizit dran schreiben oder bei den Graphen ein wenig rummogeln).

Zitat:

Überings wenn man von Hand sortiert macht man Mergesort....hast wohl noch nie nen Stapel mit 500 Klausuren sortiert oder? wink  (Vorallem kann man das wunderbar rekursiv auf mehrere Leute aufteilen :mrgreen: )

Sag' mal, du weisst aber das wir letztes Semester zusammen Klausuren korregiert haben oder? Außerdem macht man da Bucketsort tongue

Gruß,
Pollux.


http://www.michael-nett.info/
"The badness of a movie is directly proportional to the number of helicopters in it." - Dave Berry
Tutor für "Advanced Software Engineering" WS06/06

Offline

 

#7 10.08.2006 18:59:35

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: [Algo] Heapsort

Zitat:

Außerdem macht man da Bucketsort

Na am Ende tut man die Stapel aber mergen...naja Def-Sort ist besser und vorallem schneller! Wir definieren den Stapel als sortiert, fertig! => O(1)


My software never has bugs. It just develops random features.

Offline

 

#8 11.08.2006 09:22:43

Pollux
Newbie
Registriert: 10.08.2006
Beiträge: 5

Re: [Algo] Heapsort

Zitat:

Def-Sort ist besser und vorallem schneller! Wir definieren den Stapel als sortiert, fertig! => O(1)

Da gibt's aber schönere:


- Democratic-Sort: Entscheide jeweils durch Mehrheitsbeschluss ob ein Elementpaar vertauscht wird.

- Bundeswehr-Sort: Jemand wird schon dran gedacht haben das zu sortieren....

- uvm. smile


http://www.michael-nett.info/
"The badness of a movie is directly proportional to the number of helicopters in it." - Dave Berry
Tutor für "Advanced Software Engineering" WS06/06

Offline

 

Brett Fußzeile

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson