Sortieren mit Bubble-Sort

Letztmalig dran rumgefummelt: 28.06.07 07:48:27

Algotithmus Bubblesort: Eine gegebene Menge von Elementen soll via Bubble-Sort sortiert werden.
Eingangsparameter: Divident in DE Divisor in HL und BC
Ausgangsparameter: Quotient in BC und HL

Verfahren:

Die Division ist die Umkehrung der Multiplikation. Es soll eine Division mit einem Dividenden (DV) von 32 Bit und einem Divisor (DR) von 16 Bit betrachtet werden. Der Quotient (Q) möge 16 Bit sein.
Dann gilt:

DV : DR = Q Rest R oder:

Bringt man die Gleichung auf die Form

R = DV - Q - DR

und schreibt den Quotienten Q als Dualzahl

Q = Q₁₅ · 2¹⁵ + Q₁₄ · 2¹⁴ + ... Q₁ · 2¹ + Q₀

so kann man unser Verfahren aus der Gleichung

R = DV - 2¹⁵ Q₁₅ DR - 2¹⁴ Q₁₄ DR -... 2¹ Q₁ DR - Q₀ DR

ableiten.

Man probiert, ob 2¹⁵ - DR vom Dividenden DV abzuziehen geht. Wenn »ja«, ist Q₁₅ = 1, und es werden 2¹⁵ - DR abgezogen; wenn »nein«, ist Q₁₅ = 0, und 2¹⁵ - DR werden nicht abgezogen. Danach verfährt man ebenso mit 2¹⁴ - DR bis 2⁰ - DR. Für die Division ergibt sich damit folgendes Blockschema (Bild unten).
 

Bildung von Dividend - Divisor
Ist das Ergebnis negativ, so wird der Divisor wieder zum Ergebnis dazugezählt (Rückstellung des Restes) und in die letzte Stelle des Quotienten eine 0 eingetragen.
Ist das Ergebnis positiv, so wird keine Rückstellung des Restes vorgenommen. In die letzte Quotientenstelle trägt man eine 1 ein.
2. Quotient und Dividend werden gemeinsam 1 Stelle nach links verschoben. 3. 1. und 2. werden so oft wiederholt, wie der Quotient Stellen haben soll.
Am Ende steht der Quotient im Quotientenregister und im Dividendenregister der Rest. Da im Divisorregister der Divisor - 2'6 steht und wir mit einem 16-Bit-Divisor arbeiten, müssen Punkt 1 und 2 einmal zusätzlich durchlaufen und die nach der ersten Linksverschiebung aus dem Restregister austretende vorderste Stelle in einem weiteren Register aufgefangen werden.
 

Beispiel für eine kleine Anweisungstabelle in vollständiger Assembler-Codierung

zur Hauptseite

© Samuel-von-Pufendorf-Gymnasium Flöha

© Frank Rost im Juni 2007