Hardware Reference
In-Depth Information
4
5
8
17
22
12
3
1
29 43
4
5
8
12
17
22
3
1
29
43
AbbildungA.2.
Sortieren durch Einfugen. Der Bereich ist bis einschließlich der 22
(Position 5) bereits sortiert (oben). Die Zahl 12 ist als nachste einzusortieren. Dazu mussen
17 und 22 um eine Position weiter rucken (unten)
Sodann werden alle Elemente um eine Position nach rechts verschoben und
x
entsprechend eingefugt. Diesen Vorgang veranschaulicht Abbidung A.2.
Hier ein
MMIX
-Programm, das den Algorithmus implementiert:
insertionsort.mms
1
PREFIX :ISort:
2
∗
Parameter
3
A
IS
$0
4
size
IS
$1
5
∗
Lokale Register
6
i
IS
$2
Offset fur einzufugende Elemente
7
j
Laufindex fur das Einfugen
IS
$3
8
k
IS
$4
9
x
IS
$5
10
y
IS
$6
11
tmp
IS
$7
12
13
∗
Zuerst Positionierung auf zweites Element. Alle Elemente sind 8 Bytes groß.
14
Daher werden die Indizes stets um Vielfache von 8 bewegt
15
:ISort
∗
SET
i,8
16
JMP
1F
17
18
2H
x,A,i
nachstes einzufugendes Element
LDO
19
SET
j,i
20
JMP
3F
21
5H
y,A,j
yruckt eine Position weiter vor
STO
22
SET
j,k
23
3H
BNP
j,4F
24
SUBU
k,j,8
25
LDO
y,A,k
26
CMP
tmp,y,x
