Tag an alle, ich muss für mein Projekt 8 8Bit-Zahlen der Größe nach sortieren. Dafür suche ich ein möglichst effizientes Verfahren. Bisher habe ich - Bubbelsort (sehr langsgam) - Quicksort gefunden. Kennt noch jemand ein besseres Verfahren? Vielen Dank schon mal im Voraus, MC
> ein besseres Verfahren?
Die Frage is hier, was genau du unter besser verstehst. Es gibt
unzählige verschiedene Sortieralgorithmen. Was muss bei dir besonders
effizient sein? Laufzeit, Codegröße, Ram verbrauch?
Und gibt es evtl. irgendwelche Besonderheiten/zusätzlichen Informationen
über die zu sortierenden Zahlen? Das hilft auch oft bei der Auswahl des
Verfahrens.
Mein Rat: Programmiere es nicht selber sondern nimm einfach die stdlib.h qsort() Funktion.
Umterm Strich ist auf Mikrocontrollern Heapsort meist am besten geeignet: keine Rekursion, konstanter Speicherverbrauch, gutes Wort-Case-Verhalten.
Schau mal hier, da gibt's zig Algorithmen mit Komplexitätsanalyse und Animationen. http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/algoen.htm Und für heapsort gibt's sogar ne C-Quelle. Möglicherweise ist bei so ner kleinen Menge ein naiver Algorithmus aber besser.
Bei nur 8 Werten braucht man keine Komplexitätsbetrachtungen anzustellen. Ich schätze, dass so etwas mit am besten abschneiden wird, aber sicher bin ich mir nicht (Probieren macht schlau :)): http://de.wikipedia.org/wiki/Selectionsort Aber bitte nicht das angegebene Beispiel in C abtippen (unnötig kompliziert), sondern das C#-Beispiel umschreiben (viel ist da nicht zu tun).
Vielen Dank für eure Antworten! ich werde mir die Links heute abend mal zu Gemüte führen. >> ein besseres Verfahren? >Die Frage is hier, was genau du unter besser verstehst. >Was muss bei dir besonders effizient sein? Laufzeit, Codegröße, Ram >verbrauch? >Und gibt es evtl. irgendwelche Besonderheiten/zusätzlichen Informationen >über die zu sortierenden Zahlen? Das hilft auch oft bei der Auswahl des >Verfahrens. Ich muss lediglich 8 8Bit Zahlen (genauer gesagt können nur Werte von 0 bis 64 auftreteten) der Größe nach sortieren. Ob auf- oder Absteigend ist dabei relativ uninteressant, da ich ja oben bzw. unten in meiner sortierten Liste anfangen kann zu lesen.
>Was muss bei dir besonders effizient sein? Laufzeit, Codegröße, Ram >verbrauch?
hab ich ganz vergessen: je schneller die Sortierung abläuft, desto
besser. Ist zwar noch nicht zeitkritisch, aber ich habe noch andere
Routinen, die ich nicht unnötig ausbremsen möchte.
RAM und Flash für den Code ist genügend vorhanden.
Beim Wertebereich 0..64 würd mir Bucketsort mit einer Laufzeit von O(n) einfallen, bei nur 8 Zahlen holt der den Overhead aber nie wieder ein...
Danke noch mal für eure Links! Ich nehme jetzt doch Bubble-Sort, da es i µC am einfachsten umzusetzen ist. Außerdem sind es ja eh nur 8 Werte. mein Test-Code für den 8051 ist im Anhang.
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
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.