Hilfe bei Sortierungsverfahren

[MC (Gast)]

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

[hellboy (Gast)]

heapSort
QuickSort
mergeSort
shellSort

[Klaus (Gast)]

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

[Johnny Maxwell (Gast)]

Mein Rat: Programmiere es nicht selber sondern nimm einfach die 
stdlib.h qsort() Funktion.

[Andreas S. (andreas) (Admin)]

Umterm Strich ist auf Mikrocontrollern Heapsort meist am besten 
geeignet: keine Rekursion, konstanter Speicherverbrauch, gutes 
Wort-Case-Verhalten.

[Johann L. (gjlayde)]

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.

[yalu (Gast)]

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

[MC (Gast)]

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.

[MC (Gast)]

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

[Εrnst B. (ernst)]

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

[MC (Gast)]

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.