von Harald Schönfeld

Anmerkung: Runde Klammern, die in den
Listings(-auszügen) mit einem PLUS (+)
gekennzeichnet sind, sind als ent-
sprechend eckige (!) Klammern ohne +
einzugeben.

Nachdem wir uns bisher vor allem mit
der QUICK-Theorie beschäftigt haben,
werden wir nun anhand eines ersten,
größeren Programmierbeispiels sehen,
wie man lokale Variablen in QUICK
sinnvoll einsetzen kann.

Sortieren in QUICK

Eine einfache, und doch anspruchsvolle
Aufgabe ist es, ein Zahlenfeld zu sor-
tieren. Da es in QUICK verschiedene
Arten von numerischen Variablen gibt,
sollte man sich auf eine bestimmte
Variablenart festlegen.

Da WORD-Variablen für die allermeisten
Berechnungen ausreichen, stellen wir es
uns also zur Aufgabe ein "WORD-Array"
zu sortieren. Wie ein solches ARRAY
aufgebaut sein muß, haben wir ja im
letzten Teil gesehen.

Das Programm wird sich in etwa in die
folgenden Teile gliedern:

- Einlesen des Feldes
  Dieser Teil wird sicher in jedem     
  Programm anders aussehen müssen.
- Sortieren des Feldes
  Das ist eine Aufgabe, die ein für    
  alle mal zu lösen sein dürfte.
- Ausgeben des Feldes
  Das wird auch von Anwendung zu       
  Anwendung verschieden sein.

Das WORDSORT Programm

Da wir keine besondere Anwendung für
unser Sortierprogramm haben werden,
fallen die Teile "Einlesen" und "Ausge-
ben" natürlich ganz einfach aus. In
einer Schleife lesen wir jeweils einen
WORD-Wert ein, und schreiben ihn dann
in das ARRAY. Dabei ist natürlich zu
beachten, daß der Index immer um 2
erhöht werden muß (siehe letzter Teil).
Das Ausgeben des Arrays nach dem Sor-
tieren gestaltet sich genauso einfach.

Der schwierige Teil ist das Sortierpro-
gramm, das so geschrieben werden soll,
daß man es auch in jedem anderen Pro-
gramm, ohne jede Änderung verwenden
könnte. Das bedeutet also, daß wir in
dieser Sortierroutine keine einzige
globale Variable, sondern nur lokale
Variablen verwenden dürfen. Die Über-
gabe der Felder muß demnach auch mit
lokalen Variabeln geschehen.

Zunächst müssen wir beim Aufruf des
Programms das unsortierte Feld an das
Unterprogramm übergeben. Außerdem soll-
ten wir auch einen Wert übergeben, der
angibt, wieviele Werte im Feld zu sor-
tieren sind. Schließlich müssen wir
nach dem Sortieren das sortierte Feld
von der Routine entgegennehmen.

Wenn FELD das zu sortierende Feld ist,
und ANZ angibt, wieviele BYTEs(!) zu
sortieren sind, dann sieht der
entsprechende Aufruf z.B. so aus:

.SORT(FELD,ANZ,FELD)

Wie man sieht, wird zunächst FELD, und
ANZ an das Unterprogramm SORT
übergeben. "." bedeutet, daß das
Programm dann aufgerufen wird. Und
schließlich wird das Ergebnis dann in
FELD zurückgeliefert. Wir könnte hier
auch eine andere Feldvariable angeben.
Natürlich wäre es auch möglich anstatt
der Variablen ANZ direkt eine Zahl zu
übergeben.

Der dazugehörige Variablen-Deklara-
tionsteil der Routine SORT muß dann so
aussehen:

PROC SORT
IN
ARRAY
+(
UNSORT(255)
+)
BYTE
+(
ANZ
+)
OUT
ARRAY
+(
SORTED(255)
+)
LOCAL
...
Die Reihenfolge von IN und OUT spielt
dabei keine Rolle. Wichtig ist nur, daß
die richtige Variablen in IN und OUT
angegeben werden.

Zu beachten ist, daß wir die ARRAYs auf
die größtmögliche Länge setzen sollten.

Unser Ziel, die Abkopplung von SORT vom
Hauptprogramm ist nun also erreicht.
Wir haben unsere "eigenen" Variablen in
SORT, und brauchen uns nicht um irgend-
welche Variablennamen die schon da sind
(oder eben auch nicht) zu kümmern. Die
Routine ist also universell in jedem
anderen Programm einsetzbar. In BASIC
wäre das ein unlösbares Problem.

Nun zur Sortierroutine selbst:

Wie verwenden den einfachen Bubble
(Blasen)-Sortieralgorithmus, der nach
dem folgenden Prinzip arbeitet:
Stellen wir uns vor, die Daten seien
aufeinander gestapelt. Dann sorgt
Bubble-Sort sozusagen dafür, daß die
"leichteren" (also die kleineren), wie
Luftblasen nach oben steigen (daher
auch der Name), während die schwereren
entsprechend nach unten fallen.

Wie läuft das also ab ?

Wir durchlaufen das Feld von oben nach
unten. Dabei betrachten wir immer 2
übereinander liegende Elemente. Ist das
untere leichter als das obere, vertau-
schen wir die beiden. Dann rücken wir
eine Stelle tiefer und arbeiten wieder
nach diesem Prinzip. Sind wir schließ-
lich am tiefsten Punkt angekommen, so
können wir bereits jetzt sicher sein,
daß das schwerste Element ganz unten
liegt. Ob die anderen richtig liegen,
läßt sich aber jetzt noch nicht beur-
teilen. Wir gehen ds Feld also ein
weiteres mal durch. Dabei müssen wir
aber das untere Feld nicht mehr prüfen
(s.o.). Nach 2 Durchgängen dürfen wir
dann also die 2 unteren Elemente außer
acht lassen, usw. Nach ANZ-1 Durch-
läufen befinden sich dann alle Elemente
in der Richtige Reihenfolge: Das Feld
ist sortiert.

Dieser Algortihmus ist im folgenden
QUICK-Programm recht schön zu erkennen.
Man muß allerdings einige Dinge
beachten:

Vergleiche wie ...
IF UNSORT(I)>UNSORT(I+2)
sind in QUICK nicht möglich. Man muß
den Umweg über

H1=UNSORT(I)
ADD(I,2,K)
H2=UNSORT(K)
IF H1>H2

gehen, da man keine indizierte Verglei-
che machen darf.

Da wir ein WORD-Feld vor uns haben, muß
jeder Index immer um 2 erhöht oder
erniedrigt werden. Nicht um 1 wie das
bei einem BYTE-Feld der Fall wäre.

Da das Programm sowohl im SIGN als auch
im UNSIGN Modus laufen soll, muß man
bei kritischen Vergleichen vorsichtig
sein.

Wenn man überprüfen will, ob J kleiner
als Null ist, sollte man deshalbnicht
schreiben :

IF J<0

sondern den Wert, der dabei zu erwarten
ist direkt abfragen:

IF J=254

Keine Panik: Wie man weiß ist 0-2 = 256
-2 = 254 (2er-Komplement). Da solche
Ergbenisse unabhängig vom Modus sind,
ist das also bombensicher. An solche
Dinge sollte man sich in QUICK gewöhnen
(auch in Assembler oder ACTION muß man
da immer genau aufpassen).

Will man vorsichtig sein, könnte man
natürlich J auch als WORD-Variable
deklarieren. Dann wären solche Ver-
gleiche auch kein Problem, weil man
noch lange nicht an die Überlaufgrenze
käme.

Da wir in SORT einige weitere Hilfs-
variablen brauchen, deklarieren wir
diese mit LOCAL.

Da wir in SORT das Feld im ARRAY UNSORT
bekommen und in diesem ARRAY bearbei-
ten, müssen wir es am Ende in das
OUT-Array SORTED kopieren.

Man darf unter keinen Umständen ver-
suchen das IN und OUT-Feld durch ein
einziges Feld zu ersetzen...:

IN
ARRAY
+(
SFELD(255)
+)
OUT
ARRAY
+(
SFELD(255)
+)

...In der Hoffnung, daß man dann die
Kopierroutine am Ende von SORT nicht
barucht. Leider legt der Compiler aber
2 verschiedene Felder mit dem gleichen
Namen an...

Nun noch zu Erklärung einiger
verwendeter Befehle:

ADD(A,B,C)
Addiert den Wert von A zu B und
schreibt das Ergebnis in die Variable
C. Z.B.:
ADD(A,B,C)
ADD(A,2,C)
ADD(-2,4,C)

SUB funktioniert analog.


ASLB(B)
Schiebt den Inhalt der BYTE-Variable B
um eine Stelle nach links. Das bedeutet
der Inhalt wird mit 2 multipliziert
(siehe 2er Komplement). Das ist schnel-
ler als MULT(B,2,B).

REPEAT

  ...

UNTIL Vergleich

Diese Konstruktion wiederholt die
Befehlsfolge, die vom Block
eingeschlossen ist solange, bis der
Vergleich wahr ist. Bsp:

I=0
REPEAT
  PRINT(I)
  I+
UNTIL I=10

Ergibt: 0 1 2 3 4 5 6 7 8 9

IF Vergleich
  ...1
ELSE
  ...2
ENDIF

Führt Befehlsfolge ...1 aus, falls der
Vergleich wahr ist. Sonst wird ...2
ausgeführt. Der ELSE-Teil darf auch
fehlen:

IF Vergleich
  ...1
ENDIF


Soweit dazu. Nun also das Programm, das
sich auch als QUICK-File auf der Disk
befindet:


Quick-Sourcetext
D1:WORDSORT.QIK 
----------------
Length: $085B

Free  : $6F10
----------------

* Sortierdemo in QUICK V2.0
* (c) H.Schoenfeld '90

ARRAY
+(
FELD(255)  * Globales Zahlenfeld
+)
WORD
+(
W          * Hilfsvariable
+)
BYTE
+(
I        * Feldindex fuer WORD-Zugriff
J        * Feldindex fuer Feldnummer
ANZ      * Globale Anzahl der Feld-
+)       * elemente

MAIN

* SIGN   auch moeglich
  UNSIGN

* Grafik 0 BS oeffnen

  CLOSE(6)
  OPEN(6,12,0,"E:")

* Endlosschleife

  REPEAT

    ?
    ?("WORD-SORTIER-DEMO")
    ?
    ?("Anzahl der Elemente")(SEMIKOLON)
    INPUT(ANZ)

* ANZ*2 ergibt ANZ in BYTEs
* Nicht mehr als 2*126=254 Bytes

    IF ANZ>126
      ANZ=126
    ENDIF
    ASLB(ANZ)

* Auffuellen des Feldes mit WORDs

    ?("Einlesen...")
    J=0
    I=0
    REPEAT
      ?("Element ",J)(SEMIKOLON)
      INPUT(W)
      FELD(I)=W
      J+
      I+
      I+
    UNTIL I>ANZ

* Unterprogrammaufruf

    ?("Sortiere...")
    .SORT(FELD,ANZ,FELD)

* Ausdrucken des nun sortierten Feldes
    ?("Ergebnis...")
    I=0
    J=0
    REPEAT
      W=FELD(I)
      ?("Element ",J,"= ",W)
      J+
      I+
      I+
    UNTIL I>ANZ
  UNTIL 1=0
ENDMAIN

* SORT sortiert ein als WORD-Feld
* aufgebautes ARRAY der BYTE-Laenge
* ANZ und gibt das ARRAY sortiert
* zurueck.
* Funktioniert auch im SIGN-Modus
* mit Vorzeichen.

PROC SORT
IN
ARRAY
+(
UNSORT(255)  * Unsortieres Feld rein...
+)
BYTE
+(
ANZ  * Anzahl in BYTE
+)
OUT
ARRAY
+(
SORTED(255)  * sortiertes Feld raus...
+)
LOCAL
WORD
+(
H1,H2        * Hilfswords
+)
BYTE
+(
I,J,K,L      * Schleifenzaehler
+)
BEGIN

  IF ANZ=0
    W=UNSORT(0)
    SORTED(0)=W
  ELSE

* Bubble-Sort Algorithmus siehe Text.
* Zu Beachten ist die Verdopplung
* aller Indexvariablen (da WORD-Feld)
  SUB(ANZ,2,J)

  REPEAT

  I=2
  ADD(J,4,L)
* Feld von oben (klein) nach unten
* (gross) durchgehen.
    REPEAT
* 2 Elemente holen
      H1=UNSORT(I)
      SUB(I,2,K)
      H2=UNSORT(K)

* 2 Elemente vergleichen
* und vertauschen, falls das untere
* kleiner ist. (Die Leichten steigen
* auf)

      IF H2<=H1
        UNSORT(K)=H1
        UNSORT(I)=H2
      ENDIF
      ADD(I,2,I)
    UNTIL I=L
    SUB(J,2,J)

  UNTIL J=254

* Sortiertes Feld in OUT-Array kopieren
  I=0
  REPEAT
    H1=UNSORT(I)
    SORTED(I)=H1
      I+
      I+
  UNTIL I>ANZ

  ENDIF
ENDPROC

So, und wenn Sie jetzt noch das gleiche
Programm in BASIC schreiben, werden Sie
überrascht sein, wie langsam das BASIC
doch ist...