Forum: Mikrocontroller und Digitale Elektronik Sortieralgorhythmus


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von Julien (Gast)


Lesenswert?

Hallo zusammen,

Ich habe eine Frage zum sortieren von Daten.

Im SRAM des AT90S8515 habe ich 12 8Bit werte stehen.
Diese 12 Werte möchte ich jetzt der größe nach ordnen und an irgendeiner 
stelle im SRAM oder Registern wieder abspeichern.
Angefangen mit dem Größten.

Wer hat schon Erfahrung mit solchen Sortieralgorhythmen bzw. wer könnte 
mir Tipps zur Umsetzung geben.

Julien

von Sascha Weitkunat (Gast)


Lesenswert?


von Julien (Gast)


Lesenswert?

Danke Sasha,

Allerdings möchte ich Assembler verwenden und auf dieser seite wird 
meiner ansicht nach nicht so gut beschrieben wie vorzugehen ist.

Gibt es weitere Möglichkeiten

von thkais (Gast)


Lesenswert?

Für diese Aufgabe scheint mir der "Bubblesort" geeignet.
Funktionsprinzip:


Vergleiche aktuelle Speicherstelle mit der nachfolgenden.
ist die nachfolgende größer, vertausche beide. Sonst tue nichts.

Dies für alle 12 Werte machen (also 11 mal).
Die komplette Sortierung so oft durchführen, bis kein Tausch mehr 
stattgefunden hat (max. 12 mal).

von Ingo (Gast)


Lesenswert?

Hallo Julien,

das Sortieren Deiner Daten ist eine ganz einfache Sache! Du brauchst 
einen Zähler und ein Flag-Bit. Der Zähler läuft von 1 bis n Elemente 
(bei Dir sind das zwölf), Du holst Dir das Element, auf das der Zähler 
zeigt in ein Register z.B X und das folgende Element (also Zählerstand 
plus 1) in ein anderes Register z.B Y. Nun subtrahierst Du Y von X, ist 
das Ergebnis negativ so werden die beiden Elemente in der Tabelle 
vertauscht, da ja das Zweite grösser als das Erste ist. Wenn eine 
Vertauschung erfolgt ist, wird das Flag gesetzt. Ist der Zähler 
abgelaufen, so wird geprüft ob das Flag gesetzt ist. Ist es gesetzt 
erfolgt das gleiche Spiel noch einmal wenn nichts getauscht wurde ist 
Deine Tabelle geordnet.

Das Ganze nennt sich Bubble-Sort, weil es (bei visueller Betrachtung) 
den Anschein hat, das die Elemente von unten nach oben "blubbern"!

GRUSS   INGO

von Julien (Gast)


Lesenswert?

Also danke erst mal an euch.

Ich werde micht dann mit diesem Verfahren anfreunden und es in Assembler 
umsetzen.

Sollte der Code gut funktionieren, kann ich ihn dann der Codesammlung 
hinzufügen.

Gruß Julien

von Sebastian Wille (Gast)


Lesenswert?

Hi Ingo,

kleine Anmwerkung: von 1 bis (n-1), hier also 12.

Denn Du vergleichst ja immer Zählerstand mit Zählerstand +1 (!). Also am 
Ende 11 mit 11+1.

Sebastian

von Ingo (Gast)


Lesenswert?

@ Sebastian

Au Backe mein Zahn!!  Na klar Du hast recht, das kommt davon wenn man 
einen Beitrag mal eben zwischen Tür und Angel schreibt!

Danke

@ thkais

Sorry, wegen meines Beitrages, ich wollte mich nicht mit fremden Federn 
schmücken. Hatte den Beitrag offline, schnell getippt und dann ins Netz 
gescheucht, ohne vorher nachzusehen ob schon ein gleicher Beitrag da 
ist.

ENTSCHULDIGUNG!



GRUSS   INGO

von thkais (Gast)


Lesenswert?

@Ingo: So etwas passiert immer wieder mal, daß während des Schreibens 
eines Postings jemand anders die gleiche Idee hat. Zwei Menschen, ein 
Gedanke - zero Problem, da braucht man sich nicht zu entschuldigen.

von ERDI - Soft (Gast)


Lesenswert?

Hi,

soweit ich weiß, gibt es ne App-Note von Atmel, die den 
Bubble-Sortieralgorithmus inklusive Code beschreibt.
Kannst ja mal bei Atmel schauen.

von Julien (Gast)


Lesenswert?

Vielen Dank ERDI-SOFT

Das ist genau das was ich suchte.

Julien

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]
  • [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.