www.mikrocontroller.net

Forum: PC-Programmierung Sortieralgorythmus mit C++


Autor: Bastian (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: Christoph __ (chris)
Datum:

Bewertung
0 lesenswert
nicht 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?

Autor: Peter Dannegger (peda)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Peter Sager (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Μαtthias W. (matthias) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Rolf Magnus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Rekursionen haben auf MCs den Nachteil, daß ...

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

Autor: Μαtthias W. (matthias) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Christoph __ (chris)
Datum:

Bewertung
0 lesenswert
nicht 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.).

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.