Forum: PC-Programmierung Sortieralgorythmus mit C++


von Bastian (Gast)


Lesenswert?

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.

von Christoph _. (chris)


Lesenswert?

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?

von Peter D. (peda)


Lesenswert?

"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

von Peter Sager (Gast)


Lesenswert?

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

von Μαtthias W. (matthias) Benutzerseite


Lesenswert?

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

von Rolf Magnus (Gast)


Lesenswert?

> Rekursionen haben auf MCs den Nachteil, daß ...

Und was genau hat das mit PC-Programmierung zu tun?

von Μαtthias W. (matthias) Benutzerseite


Lesenswert?

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

von Christoph _. (chris)


Lesenswert?

> 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.).

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.