Sortieralgorhythmus

[Julien (Gast)]

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

[Sascha Weitkunat (Gast)]

http://www.sortieralgorithmen.de/

[Julien (Gast)]

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

[thkais (Gast)]

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

[Ingo (Gast)]

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

[Julien (Gast)]

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

[Sebastian Wille (Gast)]

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

[Ingo (Gast)]

@ 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

[thkais (Gast)]

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

[ERDI - Soft (Gast)]

Hi,

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

[Julien (Gast)]

Vielen Dank ERDI-SOFT

Das ist genau das was ich suchte.

Julien