Sortieren im Stack

Fünf Akkus, fünf Ladestände. Welcher ist der zweitschwächste? Minimum sagt dir nur den schwächsten. Wer eine Rangfolge braucht, muss sortieren – und IC10 hat dafür keinen Befehl. Du baust ihn selbst.

Werte ordnen: Bubblesort#

Das einfachste Verfahren vergleicht immer zwei Nachbarn und tauscht sie, wenn sie falsch herum stehen. Nach einem Durchlauf steht der größte Wert ganz hinten. Der nächste Durchlauf braucht ihn nicht mehr anzufassen und ist einen Schritt kürzer.

Tauschen mit Registern#

IC10 hat kein swap. Zwei Stack-Plätze tauschst du über zwei Register: beide lesen, über Kreuz zurückschreiben.

get a db j
add k j 1
get b db k
ble a b weiter        # schon richtig
poke j b
poke k a
weiter:

Der Sprung über den Tausch heißt: Stehen die beiden schon richtig, bleibt alles, wie es ist. Bei gleichen Werten wird ebenfalls nicht getauscht, deshalb ble und nicht blt.

Zwei Schleifen#

Die innere Schleife läuft mit j über die Paare, die äußere verkürzt nach jedem Durchlauf die grenze:

sub grenze ANZAHL 1
aussen:
move j 0
innen:
add j j 1
blt j grenze innen
sub grenze grenze 1
bgtz grenze aussen

Aufwand pro Takt#

Bubblesort vergleicht bei n Werten n · (n − 1) / 2 Paare. Jeder Vergleich kostet hier etwa acht Befehle:

Der Chip unterbricht nach 128 Befehlen von selbst und macht im nächsten Takt weiter. Bei 50 Werten dauert das Sortieren also fast 40 Sekunden – in der Zeit tut der Chip nichts anderes.