|
Anzeige
|
Sortieralgorythmus mit C++
Gast
#296162
Hallo, ich bin gerade dabei ein Programm zu schreiben welches mir vorher eingegebene Zahlen von der kleinsten bis zur größten sortiert und die sortierte Reihe dann ausgiebt. Also das Einlesen ins Array und das Ausgeben bekomme ich hin. Aber wie genau kann ich die Reihe intern sortieren? PS: Dies sollte auf jeden fall rekursiv und nicht über die Funktion Bubble gelößt werden. Ich hoffe mir kann vielleicht einer weiterhelfen. Da du von Array im Zusammenhang mit C++ sprichst gehe ich davon aus, dass du std::vector meinst. In dem Fall würde ich mir mal http://www.sgi.com/tech/stl/sort.html ansehen. Schneller bekommt man es kaum hin, falls der Sortieralgorithmus einigermaßen allgemein bleiben soll. Es gibt auch noch stable_sort, das die Reihenfolge "gleicher" Elemente gleich lässt, aber für Zahlen brauchst du das nicht (nur merken, dass es das gibt, falls du es mal brauchst). Falls du dich für Sortier-Algorithmen interessierst, könntest du z.B. bei Wikipedia vorbeischauen: Mergesort, Insertion Sort, Quicksort sind keine schlechten Stichworte. p.s.: std::sort funktioniert übrigens auch mit einem gewöhnlichen (C-)Array, aber wieso solltest du das unter C++ benutzen? "PS: Dies sollte auf jeden fall rekursiv und nicht über die Funktion Bubble gelößt werden." Wunderbares Statement ! Rekursionen haben auf MCs den Nachteil, daß sie viel SRAM benötigen und daß sie viel Rechenzeit mit CALL, RET, PUSH, POP verbrauchen. Wenn Dein Code also möglichst langsam sein soll und viel SRAM belegen soll, dann sind Rekursionen genau das richtige Mittel. Hast Du allerdings andere Prämissen, kann ich Dein Beharren auf Rekursion nicht nachvollziehen. Ich wähle Algorithmen jedenfalls immer nach Effizienz aus (Code-Größe, SRAM-Bedarf, Geschwindigkeit). Peter
Gast
#296165
Irgendwie sehr verdächtig: Klingt für mich nach einer mega typischen SW-Hausaufgabe für angehende Ingenieure... Sich selber den Kopf zerbrechen, bringt den grössten Lerneffekt. Oder gehörst Du zu den Schmarotzern, die sich ein Leben lang auf Kosten anderer durchs Leben mogeln? Gruss Peter Hi klingt für mich auch nach Hausaufgabe. Hier http://de.wikipedia.org/wiki/Sortieralgorithmus gibts eine schöne Übersicht über verschiedene Sortieralgorithmen. Da ist auch ersichtlich das Quicksort u.U. garnicht so quick ist wie der Name verspricht. Matthias
Gast
#296167
> Rekursionen haben auf MCs den Nachteil, daß ...
Und was genau hat das mit PC-Programmierung zu tun?
Hi die Lösung von Problemen mit rekursieven Funktionen sind nur sehr selten schnell im Vergleich z.B. zu einer Schleife. Sie sind nur sehr elegant und einfach zu programmieren. Matthias > Sie sind nur sehr elegant und einfach zu programmieren. Nicht nur das. Zum Beispiel wird tail recursion ( http://de.wikipedia.org/wiki/Endrekursion , als einfachstes Beispiel) beim Kompilieren ziemlich sicher in eine iterative Version umgewandelt. Andere Sprachen wie Scheme schreiben das sogar vor, damit sich ein Compiler "standardkonform" nennen darf. Möglicherweise erkennen aktuelle C-Compiler auch komplexere Situationen, bei denen sich Rekursion im Maschinencode einfach in Iteration umwandeln lässt. Getestet habe ich das noch nicht, habe aber newsgroup-Postings in der Richtung gelesen (in news://comp.lang.c z.B.). Antwort schreiben |
Anzeige
|
