Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

Heapsort Algorithmus in C++

  • 1
  • 2

Werbeanzeige

p0llux

Treue Seele

  • »p0llux« ist der Autor dieses Themas

Beiträge: 101

Wohnort: Aachen

Beruf: HiWi (theo. Inf.)

  • Private Nachricht senden

1

05.01.2008, 23:39

Heapsort Algorithmus in C++

Hallo zusammen,

bin ja gerade neu hier und habe mir gedacht, ich könnte direkt mal ein Tutorial das ich vor fast zwei Jahren mal geschrieben habe hier posten. Das ganze dreht sich um den sogenannten Heapsort Algorithmus. Wer also irgendwelche Objekte sortieren muss und das auch noch von der CPU erledigen lassen möchte, der kann diesen sehr schnellen Algorithmus verwenden.

Generell wird zwar von vielen Personen Quicksort bevorzugt, aber in dem .PDF-Dokument werden auch die wichtigen Unterschiede hervorgehoben und man kann sich ein Bild machen, welcher Algorithmus zu einer bestimmten Situation besser passt.

Das ganze findet sich hier - (Direktlink zum Dokument).

Gruß,
p0llux
http://www.scienceandcode.org http://www.mathestudium.org

Deviloper

Community-Fossil

Beiträge: 2 872

  • Private Nachricht senden

2

05.01.2008, 23:57

hmm deine seite war letztens mal bei "Most Inspired" gelostet ... da war ich da schon mal drauf ;)

Naja egal ... ehm in deinem Code könntest du evtl. noch ein wenig STL nutzen ... man muss nicht das Rad immer neu erfinden (std::swap usw. ;) )... sonst ganz gut :)
Devil Entertainment :: Your education is our inspiration
Der Spieleprogrammierer :: Community Magazin
Merlin - A Legend awakes :: You are a dedicated C++ (DirectX) programmer and you have ability to work in a team? Contact us!
Siedler II.5 RttR :: The old settlers-style is comming back!

Also known as (D)Evil

p0llux

Treue Seele

  • »p0llux« ist der Autor dieses Themas

Beiträge: 101

Wohnort: Aachen

Beruf: HiWi (theo. Inf.)

  • Private Nachricht senden

3

06.01.2008, 01:44

Danke für den Zucker.

Ich überleg' momentan eh, was ich dieses Semester machen soll. Prüfungen hab' ich keine, dafür gibt's aber auch nur wenige Vorlesungen weil meine Dozente fast alle Forschungssemester haben.

Ich werd' mir das mal "Whiteboarden" ;)

/p0llux

PS: Was ist "Most Inspired" eigentlich? Bin ja mal neugierig geworden ^^
http://www.scienceandcode.org http://www.mathestudium.org

Deviloper

Community-Fossil

Beiträge: 2 872

  • Private Nachricht senden

4

06.01.2008, 01:49

Ist ne Zusammenstellung von so den bekanntesten CSS-Gallary Seiten ... Eine davon hatte deine Seite an einem Tag drauf ;)
http://www.mostinspired.com/?type=gallery
Devil Entertainment :: Your education is our inspiration
Der Spieleprogrammierer :: Community Magazin
Merlin - A Legend awakes :: You are a dedicated C++ (DirectX) programmer and you have ability to work in a team? Contact us!
Siedler II.5 RttR :: The old settlers-style is comming back!

Also known as (D)Evil

TrommlBomml

Community-Fossil

Beiträge: 2 117

Wohnort: Berlin

Beruf: Software-Entwickler

  • Private Nachricht senden

5

06.01.2008, 11:15

Zitat von »"Deviloper"«

Naja egal ... ehm in deinem Code könntest du evtl. noch ein wenig STL nutzen ... man muss nicht das Rad immer neu erfinden (std::swap usw. )


also soweit würde ich immer stl vermeiden, weis nich was du die imma so anpreist an allen stellen. vor allen beim sortieren, was ziemlich zeitaufwändig ist und durch die stl nochmal ordentlich langsamer wird...

dot

Supermoderator

Beiträge: 9 757

Wohnort: Graz

  • Private Nachricht senden

6

06.01.2008, 11:46

Zitat von »"TrommlBomml"«

also soweit würde ich immer stl vermeiden, weis nich was du die imma so anpreist an allen stellen. vor allen beim sortieren, was ziemlich zeitaufwändig ist und durch die stl nochmal ordentlich langsamer wird...


worauf stützt sich diese these?
m4studios

TrommlBomml

Community-Fossil

Beiträge: 2 117

Wohnort: Berlin

Beruf: Software-Entwickler

  • Private Nachricht senden

7

06.01.2008, 11:53

unter anderem hat mir das der contest gezeigt, hatte es erst komplett mit stl implementiert(mein algorithmus). war schon ein wenig schneller. als ich dann mit einem array ersetzt habe wars nochma bedeutend schneller. ausserdem stütze ich mich noch auf die regel "statisch ist schneller als dynamisch".

Deviloper

Community-Fossil

Beiträge: 2 872

  • Private Nachricht senden

8

06.01.2008, 12:53

Hmm dann setzt die Algos intelligent ein und fertig. Und ja wenn es auf Geschwindigkeit ankommt, können, in ganz bestimmten Fällen, in dem bsw. bei dem Algorithmus, derim Standard ist, eine Kopieroperation ausgeführt wird, die du dir sparen könntest, schneller.
Devil Entertainment :: Your education is our inspiration
Der Spieleprogrammierer :: Community Magazin
Merlin - A Legend awakes :: You are a dedicated C++ (DirectX) programmer and you have ability to work in a team? Contact us!
Siedler II.5 RttR :: The old settlers-style is comming back!

Also known as (D)Evil

TrommlBomml

Community-Fossil

Beiträge: 2 117

Wohnort: Berlin

Beruf: Software-Entwickler

  • Private Nachricht senden

9

06.01.2008, 16:00

vllt um das ganze auch mal zu entschärfen ich will nicht sagen, dass ich die stl nich nutze, ganz im gegenteil! Bei solchen sachen, wo man oft datensätze löschen muss etc. (bezug auf vector, List) oda stringmainuplation (std::string) ist sie echt von vorteil.

rklaffehn

Treue Seele

Beiträge: 267

Wohnort: Braunschweig

  • Private Nachricht senden

10

06.01.2008, 16:47

Um nochmal eine Referenz einzuwerfen, die STL kennt auch Heaps, man muss das also nicht alles selbst programmieren:

make_heap auf www.cplusplus.com

Aber als Hilfe zum Verständnis, was da eigentlich passiert, ist das Dokument sehr schön.
God is real... unless declared integer.
http://www.boincstats.com/signature/user_967277_banner.gif

Werbeanzeige

  • 1
  • 2