mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik Hilfe bei Sortierungsverfahren


Autor: MC (Gast)
Datum:

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

Autor: hellboy (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
heapSort
QuickSort
mergeSort
shellSort

Autor: Klaus (Gast)
Datum:

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

Autor: Johnny Maxwell (Gast)
Datum:

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

Autor: Andreas Schwarz (andreas) (Admin) Benutzerseite Flattr this
Datum:

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

Autor: Johann L. (gjlayde) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Schau mal hier, da gibt's zig Algorithmen mit Komplexitätsanalyse und 
Animationen.

http://www.inf.fh-flensburg.de/lang/algorithmen/so...

Und für heapsort gibt's sogar ne C-Quelle.

Möglicherweise ist bei so ner kleinen Menge ein naiver Algorithmus aber 
besser.

Autor: yalu (Gast)
Datum:

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

Autor: MC (Gast)
Datum:

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

Autor: MC (Gast)
Datum:

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

Autor: Εrnst B✶ (ernst)
Datum:

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

Autor: MC (Gast)
Datum:
Angehängte Dateien:

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

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.