|
Anzeige
|
Hilfe bei Sortierungsverfahren
Gast
#897073
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
Gast
#897075
heapSort QuickSort mergeSort shellSort
Gast
#897080
> 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.
Gast
#897081
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.
Gast
#897103
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).
Gast
#897246
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.
Gast
#897249
>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...
Gast
#898199
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. Antwort schreiben |
Anzeige
|
