Datenstrukturen & Algorithmen in Omikron.BASIC und Modula 2, Teil 3: Behältersortieren - Radixsort
Radixsort ist ein sehr interessantes Sortierverfahren - basierend auf dem Behältersortieren. Wir stellen beide Algorithmen vor und implementieren sie Schritt für Schritt in Modula-2 und Omikron.BASIC.
Sie kennen doch sicher das Kartenspiel 32-heb-auf. Nicht? Kein Problem. Es gibt nur eine Regel: Werfen Sie ein komplettes Skat-Spiel auf den Boden. Alles weitere ergibt sich aus dem Namen - 32-heb-auf. Übrigens spielen die meisten dieses Spiel nur einmal selbst, aber umso öfter mit anderen.
Wir wollen zunächst Ihre Fingerfertigkeit testen. Böse Zungen behaupten, daß sich bei Computer-Freaks die Anwendung dieser Gliedmaßen auf die Betätigung von Tasten beschränkt. Beweisen Sie das Gegenteil: Die Karten dürften nach Ihrer Sammelaktion unter dem Schreibtisch gut gemischt sein. Ihre erste Aufgabe ist, die Karten zu sortieren - rein manuell versteht sich.
Doch halt! Nicht so voreilig. Wir stellen Ihnen ein schnelles Sortierverfahren vor.
Klappe: Spielkartensortieren - die erste
Schaffen Sie vor sich soviel Platz, daß Sie acht Kartenstapel nebeneinander legen können - für jeden Kartenwert einen. Der linke Stapel sei für die Siebenen, der rechts daneben für die Achten, der nächste für die Neunen und so weiter. Ganz rechts kommen die Asse zu liegen.
Legen Sie Ihren gemischten Kartenstapel mit dem Blatt nach oben vor sich hin. Nehmen Sie die oberste Karte und verteilen Sie diese bezüglich Ihres Werts auf einen der acht Stapel. Dies wiederholen Sie solange, bis der gemischte Stapel leer ist (32mal). Jeder Stapel enthält anschließend vier Karten. Legen Sie alle Stapel von rechts nach links aufeinander - zuerst die Asse auf die Könige, diese acht Karten auf die Damen und so weiter.
Im zweiten Durchgang verteilen Sie die Karten auf vier Stapel - für jede Farbe einen. Die Reihenfolge ist von links nach rechts: Kreuz, Pik, Herz, Karo. Legen Sie immer nur die oberste Karte Ihres vorsortierten Kartenstapels auf einen der Farbenhaufen. Anschließend enthalten alle vier Stapel acht Karten. Legen Sie die Stapel genau umgekehrt zum ersten Durchgang aufeinander - von links nach rechts: Der Kreuz-Stapel kommt auf den für die Pik-Karten, diese zusammen auf den Herz- und zum Schluß alles auf den Karo-Stapel.
Die Karten sind jetzt in der Reihenfolge Kreuz-7 - Kreuz-As, Pik-7 - Pik-As, Herz-7 - Herz-As, Karo-7 - Karo-As sortiert.
Suchen Sie sich nun bitte einen netten’ Zeitgenossen und spielen Sie mit ihm 32-heb-auf. Falls gerade keiner zur Hand ist, dürfen Sie die Karten auch anders mischen.
Klappe: Spielkartensortieren - die zweite
Wir modifizieren das Sortierverfahren ein wenig: Verteilen Sie die Karten zuerst in die vier Farbenstapel und legen Sie die Haufen von rechts nach links übereinander. Anschließend verteilen Sie sie auf die acht Wert-Stapel und sammeln von links nach rechts. Auch jetzt sind die Karten sortiert, aber in einer anderen Reihenfolge: Kreuz-7 - Karo-7, Kreuz-8 - Karo-8, …, Kreuz-As - Karo-As.
Unten zeigen wir, warum das Kartensortieren funktioniert. Sie werden sehen, daß es eine praktische Anwendung des Behältersortierens und der Radix-Sortierung ist.
Behältersortieren
Im ersten Kursteil haben wir beschrieben, daß ein Datentyp die Menge von Werten bezeichnet, die ein Objekt annehmen kann.
TYPE Letter=["A".."Z"]
TYPE Digit=["0".."9"]
Letter und Digit sind selbstdefinierte Modula-2-Datentypen. Letter ist ein Name für die Menge aller Großbuchstaben (ohne Umlaute). Digit umfaßt alle Dezimalziffern. Die Kardinalität eines Datentyps ist die Anzahl der zu diesem Typ gehörenden Werte. Man kennzeichnet die Kardinalität durch Voranstellen von ’#' oder durch Umklammern mit zwei senkrechten Strichen (Betragsstriche). Im folgenden sind Kardinalitäten für einige Datentypen aufgelistet.
#Letter=26
#Digit=10
#CHAR=256
#INTEGER=65536
#BOOLEAN=2
Wir beschäftigen uns im folgenden mit der Sortierung von Objekten. Als Objekt bezeichnen wir den Wert eines beliebigen Datentyps. Beispiele sind Zahlen, Strings, Records oder Felder. Die Objekte sortieren wir nach ihren Schlüsselwerten. Vereinfachend nennt man den Schlüsselwert auch Schlüssel. Das Schlüsselfeld ist die Komponente des Objekts, die den Schlüsselwert enthält.
(**********************************************
* Algorithmus zum Behältersortieren bei *
* verschiedenen Schlüsselwerten *
**********************************************)
CONST MaxN=<Anzahl maximal zu sortierender Records>
MinKey= <kleinster mögl. Schlüsselwert>
MaxKey= <größter mögl. Schlüsselwert>
TYPE KeyTyp = [MinKey..MaxKey]; (* Datentyp für die Schlüssel *)
ObjTyp=RECORD (* Datentyp für die zu sortierenden Objekte *)
Key : KeyTyp (* Schlüsselfeld *)
<weitere Komponenten>
END;
...
VAR A : ARRAY [1..MaxN] OF ObjTyp; (* zu sortierendes Feld *)
B : ARRAY KeyTyp OF ObjTyp; (* Behälter *)
N : CARDINAL; (* Anzahl zu sortierender Records *)
j : KeyTyp; (* Laufvariable *)
i : CARDINAL; (* Laufvariable *)
...
BEGIN
(* Behälter löschen *)
FOR j:=MinKey TO MaxKey DO
<B[j] als leer markieren>
END;
(* Sortieren *)
FOR i:=1 to N DO
B[A[i].Key]:=A[i]
END;
(* sortiert zurückschreiben *)
i : =0 ;
FOR j:=MinKey TO MaxKey DO
IF <B[j] ist nicht leer> THEN
A[i]:=B[j];
i : =i + 1
END;
END;
END;
Bild 10
Bei Datentypen mit kleiner Kardinalität bietet sich zum Sortieren das Behältersortieren (Fachsortieren, engl, binsort) an. Für jeden möglichen Schlüsselwert stellen wir einen Behälter (Fach, engl. bin) bereit, der die Objekte mit diesem Schlüsselwert aufnimmt.
Dieses Prinzip verwendet man abgewandelt in der Industrie. Kartoffeln sortiert man bezüglich ihrer Größe, indem man sie über Siebe mit verschieden großen Löchern leitet. Unter jedem Sieb steht ein Behälter, der die Kartoffeln dieser Größe aufnimmt.
Im ersten Schritt unserer Kartensortierung legen wir für jeden Kartenwert einen Stapel an. Diese Stapel sind die Behälter.
Auf den Schlüsselwerten muß eine (totale) Ordnung definiert >ein. Die Ordnung ergibt sich meist aus dem Kontext. Bei Zahlen ist klar, daß fünf kleiner als sieben ist. Ebenso sortieren wir Anna vor Rudolf. Datentypen für Schlüsselwerte mit beschränkter Kardinalität haben einen kleinsten und einen größten Schlüsselwert. Diese bezeichnen wir meist mit MinKey beziehungsweise MaxKey. Beide sind eindeutig.
Verschiedene Schlüsselwerte
Betrachten wir zunächst den einfachsten Fall: Alle zu sortierenden Datenobjekte haben verschiedene Schlüsselwerte. Somit speichert ein Behälter maximal ein Objekt.
Die Behälter realisieren wir in einem Feld. Dieses stellt für jeden möglichen Schlüsselwert genau einen Behälter bereit.
Betrachten wir beispielsweise die folgende Datentypdefinition und Variablendeklaration.
CONST MinKey = 1;
MaxKey = 5;
TYPE KeyTyp = [MinKey..MaxKey];
ObjTyp = RECORD
Key : KeyTyp;
Text: String;
END;
VAR A : ARRAY [0..2] OF ObjTyp;
ObjTyp ist der Datentyp der zu sortierenden Objekte. ObjTyp enthält ein Schlüsselfeld namens Key (Schlüssel) vom Datentyp KeyTyp. Der Schlüsselwert in Key ist eine ganze Zahl zwischen eins und fünf. Die Informationskomponente Text speichert eine Zeichenkette. Das Record-Feld A enthält drei Records des Datentyps ObjTyp.
Wir wollen ein entsprechendes Feld A() in Omikron.BASIC sortieren. Die Felddimensionierungen und exemplarischen Variablenvorbelegungen lauten:
DIM A_Key%(2), A_Text$(2)
A_Key%(0)=5: A_Text$(0)="Maus"
A_Key%(1)=2: A_Text$(1)="Hund"
A_Key%(2)=4: A_Text$(2)="Katze"
Wir sortieren nicht die Zeichenketten, sondern die Zahlen (Schlüsselwerte). Zugelassen haben wir die Schlüsselwerte eins bis fünf. Wir benötigen also fünf verschiedene Behälter. Allgemein gilt:
Die Kardinalität des Schlüsselwertdatentyps ist die Anzahl der benötigten Behälter.
Die Behälter speichern wir in einem Record-Feld, das wir B() nennen. Der Datentyp von B() muß den Datentyp von A() enthalten:
DIM B_Key%(5), B_Text$(5)
Der Einfachheit halber spendieren wir einen zusätzlichen Behälter mit dem Index Null. Wir sortieren in einer einzigen Schleife:
'Behältersortieren'verschiedene Schlüsselwerte
FOR I%=0 TO 2
B_Key%(A_Key%(I%))=A_Key%(I%)
B_Text$(A_Key%(I%))=A_Text$(I%)
NEXT I%
enthält anschließend folgende Werte
B_Key%(0)=0 B_Text$(0)=""
B_Key%(1)=0 B_Text$(1)=""
B_Key%(2)=2 B_Text$(2)="Hund"
B_Key%(3)=0 B_Text$(3)=""
B_Key%(4)=4 B_Text$(4)="Katze"
B_Key%(5)=5 B_Text$(5)="Maus"
Der Wert Null kennzeichnet einen leeren Behälter. Von oben nach unten betrachtet sehen Sie in B() die sortierte Reihenfolge der Schlüssel: 2, 4, 5. Die sortierten Records schreiben wir nun in das Feld A() zurück:
' Behälter auflösen
I% = 0
FOR J%=1 TO 5
IF B_Key%(J%)<>0 THEN
A_Key%(I%)=B_Key%(J%)
A_Text$(I%)=B_Text$(J%)
I%=I%+1
ENDIF
NEXT J%
Anschließend enthält das Feld A() folgende Werte:
A_Key%(0)=2: A_Text$(0)="Hund"
A_Key%(1)=4: A_Text$(1)="Katze"
A_Key%(2)=5: A_Text$(2)="Maus"
Bild 10 zeigt den Algorithmus in Modula-2-Syntax.
KeyTyp kann theoretisch anstelle eines Unterbereichstyps auch ein Aufzählungstyp sein.
Ein Problem ist die Kennzeichnung eines leeren Behälters. Zwei Wege zur Realisierung bieten sich an: Wir ergänzen KeyTyp um einen Wert, der einen leeren Behälter markiert. Diesen Weg sind wir in der Omikron.BASIC-Version mit dem Wert Null gegangen. Als Alternative erweitern wir den Datentyp von B() um ein Flag. Dieses signalisiert, ob der Behälter belegt oder leer ist. Wir gehen auf dieses Problem nicht weiter ein, da es bei unseren späteren Algorithmen wegfällt.
Beliebige Schlüsselwerte
Vereinfachend sind wir davon ausgegangen, daß jeder Schlüssel wert maximal einmal vorkommt. Diese Voraussetzung ist nur selten gegeben. Wir umgehen dieses Problem, indem jeder Behälter Objekte mit gleichen Schlüsseln in einer Warteschlange (engl, queue) speichert. Also: pro Behälter eine Schlange.
Im Hinblick auf Radixsort sortieren wir im folgenden Schlangen anstatt Felder. Als grobe Struktur ergibt sich somit:
gegeben: unsortiertes Feld A
gesucht: sortiertes Feld A
- unsortiertes Feld A in Schlange S übertragen
- Schlange S sortieren
- sortierte Schlange S in das Feld A zurückschreiben
Ein großer Vorteil dieses Aufbaus sticht sofort ins Auge: Falls die zu sortierenden Daten bereits als Schlange organisiert sind, entfallen die Schritte 1. und 2. Diese Situation liegt in Modula-2-Programmen meist vor.
Die Übertragung von Feldern in Schlangen und umgekehrt beschreiben wir im nächsten Kursteil. Wir befassen uns vorerst mit Schritt 2 - der Sortierung einer Schlange S in Behälter B().
Den groben Aufbau des Behältersortierens haben wir in unseren Einführungsbeispielen vorgestellt. Bild 11 zeigt den Behältersortier-Algorithmus für beliebige Schlüssel. Bild 12 verdeutlicht die Arbeitsweise bei der Sortierung von Namen. Es wird nur nach den Anfangsbuchstaben geordnet. Diese sind explizit als Schlüsselwerte angegeben.
(**********************************************
* Algorithmus zum Behältersortieren *
**********************************************)
CONST
MinKey = <kleinster möglicher Schlüsselwert>
MaxKey = <größter möglicher Schlüsselwert>
TYPE
KeyTyp = <Datentyp, der die möglichen
Schlüsselwerte festlegt. Auf KeyTyp
muß eine Ordnung definiert sein.
MinKey und MaxKey sind der
kleinste bzw. größte mögliche Wert>
ObjTyp=RECORD (* Datentyp für die zu sortierenden Objekte *)
Key : KeyTyp; (* Schlüsselfeld *)
Info : InfoTyp; (* beliebig viele Infokomponenten *)
END;
STyp = <Datentyp für die Realisierung einer
Schlange, deren Elemente vom Datentyp
ObjTyp sind.>
...
VAR
S : STyp; (* zu sortierende Schlange *)
B = ARRAY KeyTyp OF STyp;
(* Behälterfelder mit einem Element pro
möglichem Schlüsselwert. Jeder
Behälter speichert eine Schlange. *)
i : KeyTyp; (* Laufvariable *)
...
BEGIN
(* Alle Behälter löschen *)
FOR i:=MinKey TO MaxKey DO
Lösche B(i)
END;
(* Schlange S in die Behälter B() sortieren *)
WHILE Schlange S nicht leer DO
Entferne Kopf von S und hänge ihn an die
Schlange des Behälters B(Kopf(S).Key)
END;
(* Behälter B() aufsammeln und sortierte Schlange S erzeugen. *)
Erzeuge leere Schlange S
FOR i:=MinKey TO MaxKey DO
Falls Schlange in B(i) nicht leer, hänge
sie an die Schlange S
END;
(* Die Schlange S ist nun sortiert *)
END;
Bild 11
Behältersortieren in Modula-2
Bild 13 zeigt geeignete Datentyp-Definitionen für die Implementierung des Behältersortierens in Modula-2.
#(* Allgemeine Datentypdefinitionen für das Behältersortieren *)
CONST MaxN=<Anzahl max. zu sortierender Records>
MinKey= <kleinster mögl.Schlüsselwert>
MaxKey= <größter mögl. Schlüsselwert>
TYPE KeyTyp = [MinKey..MaxKey]; (* Wertebereich der Schlüsselwerte *)
ObjTyp =RECORD (* Datentyp für die zu sortierenden Objekte *)
Key KeyTyp;
<Infokomponenten>
END;
ObjLPtr= POINTER TO ObjLTyp;
ObjLTyp= RECORD (* Listenelement *)
Obj : ObjTyp;
Next : ObjLPtr
END;
STyp= RECORD (* Schlangen- = Listentyp *)
Anfang : ObjLPtr;
Ende : ObjLPtr;
END;
Bild 13
Die Definitionen sehen komplizierter aus, als sie sind. Bild 14 stellt die Struktur grafisch dar. Die zu sortierenden Objekte sind vom Datentyp ObjTyp. Dieser ist gegliedert in das Schlüsselfeld Key und Informationskomponenten.
Ein Behälter ist eine Schlange. Schlangen realisieren wir als lineare Listen. Der Datentyp hierzu heißt STyp. Er speichert Zeiger auf den Anfang und das Ende der Schlange.
Die Listenelemente sind vom Typ Obj-LTyp. Ein Listenelement setzt sich aus dem zu sortierenden Objekt und einem Zeiger auf das nächste Listenelement zusammen. Die zugehörigen Variablendeklarationen lauten:
VAR S : STyp; (* zu sortierende Schlange *)
B : ARRAY KeyTyp OF STyp;
(* Feld mit Behältern *)
p : ObjLPtr; (* Hilfszeiger *)
i : KeyTyp; (* Laufvariable *)
Die Behälter löschen wir, indem wir jeweils den beiden Zeiger NIL zuweisen:
(* Behälter löschen *)
FOR i:=MinKey TO MaxKey DO
B[i].Anfang:=NIL;
B[i].Ende:=NIL
END;
Das Verteilen der Schlange auf die Behälter ist tückisch. Wir entfernen jeweils den Schlangenkopf und hängen ihn an die Schlange des Behälters für den zugehörigen Schlüsselwert:
(* Schlange in Behälter sortieren *)
(* fehlerhaft *)
WHILE S.Anfang<>NIL DO
LLAnhaengen(B[S.Anfang^.Obj.Key],S.Anfang);
S.Anfang:=S.Anfang^.Next;
END;
Die Prozedur LLAnhaengen(VARL:STyp;P:ObjLPtr) aus Listing 4 hängt das Objekt, auf das P zeigt, an das Ende der Liste L. Diese Operation entspricht dem Einfügen in eine Schlange (siehe zweiter Kursteil).
Finden Sie den Fehler in obigem Algorithmus? LLAnhaengen() hängt den Schlangenkopf an die Schlange eines Behälters. Dabei wird dem Next-Zeiger des Schlangenkopfs NIL zugewiesen, denn er markiert das Behälterschlangenende. Die nachfolgende Operation S.Anfang: = SAnfang^.Next weist S.Anfang somit den Wert NIL zu. Damit können wir auf den Rest der Schlange nicht mehr zugreifen. Die Schleife terminiert, nachdem das erste Element verteilt ist.
Dieser Fehler ist typisch für Programme mit dynamischer Speicherverwaltung. Durch Unachtsamkeit verbiegt man wichtige Zeiger, so daß Daten zu Speicherleichen werden.
Abhilfe schafft ein Hilfszeiger p. p speichert das zweite Element von S, denn dieses ist im nächsten Schleifendurchlauf der Schlangenkopf:
(* Schlange in Behälter sortieren *)
WHILE S.Anfang<>NIL DO
p:=S.Anfang^.Next; (* Zeiger auf nächstes Element retten *)
LLAnhaengen(B[S.Anfang^.Obj.Key],S.Anfang);
S.Anfang:=p;
END;
Das Aufsammeln der Behälter ist einfach:
(* Behälter auflösen und sortierte Liste generieren *)
S.Anfang:=NIL;
S.Ende:=NIL;
FOR i:=MinKey TO MaxKey DO
IF B[i].Anfang<>NIL THEN
LLVerbinden(S,B[i])
END
END;
Die Prozedur LLVerbinden(VAR L1,L2:STyp) hängt die Liste L2 an die Liste L1. Sie berücksichtigt die Sonderfälle, daß die Listen leer sind.
Listing 4 enthält die komplette Modula-2-Implementierung des Behältersortierens mit einer Testumgebung. Das Programm sortiert Strings nach einem Schlüssel vom Typ CHAR. Bild 15 ist eine Hardcopy der Ausgabe. Oben steht die unsortierte, unten die sortierte Liste.
Behältersortieren in Omikron.BASIC
Wenden wir uns der Implementierung des Behältersortierens in Omikron.BASIC zu. In den folgenden Beispielen sortieren wir Worte (Strings) bezüglich des Anfangsbuchstabens. Das Schlüsselfeld ist das erste Element (Zeichen) des Strings. Der Schlüsselwert ist der ASCII-Wert des Anfangsbuchstabens und nicht das Zeichen selbst.
Zur Realisation bietet sich die Datenstruktur Wortliste W1 an, die wir im zweiten Kursteil beschrieben haben:
DIM Wl_Wort$(Max_N%),
Wl_Next%(Max_N%)
Wir gehen davon aus, daß die Strings als Schlange organisiert sind. Diese Schlange S ist charakterisiert durch die beiden Cursor S_Anfang% und S_Ende%.
Min_Ascii% sei eine Konstante, die das Zeichen mit dem kleinsten ASCII-Wert festlegt, der sortiert wird. Entsprechend definiert Max_Ascii% den größtmöglichen Schlüsselwert. Die Behälter dimensionieren wir wie folgt:
DIM B_Anfang%(Max_Ascii%), B_Ende%(Max_Ascii%)
In Omikron.BASIC beginnen Felder mit dem Index Null. Die Behälter mit den Indizes von Null bis Min_Ascii%-1 sind somit überflüssig. Wir nehmen dies in Kauf, damit die Adressierung der Behälter einfach ist. Als erstes löschen wir die Behälter:
'Behälter löschen
FOR I%=Min_Ascii% TO Max_Ascii%
B_Anfang%(I%)=0
B_Ende%(I%)=0
NEXT I%
Die Sortierung ist aufwendiger als in Modula-2. Wir benutzen zwei Hilfsvariablen, um die Adressierung der Behälter übersichtlich zu gestalten: Wort$ speichert den String, der in einen Behälter verteilt wird. Ch% ist der ASCII-Wert des Anfangsbuchstabens von Wort$. Im Hinblick auf die allgemeine String-Sortierung mit Radixsort bestimmen wir Ch% mit der Funktion MID$() und nicht mit LEFT$().
'S in Behälter sortieren
WHILE S_Anfang%<>0
P%=Wl_Next%(S_Anfang%) ' Cursor
'auf das zweite Listenelement
'retten
Wort$=Wl_Wort$(S_Anfang%)
Ch%=ASC(MID$(Wort$,1,1))
Ll_Anhaengen(B_Anfang%(Ch%),B_Ende%(Ch%),S_Anfang%)
S_Anfang%=P%
WEND
Die Prozedur Ll_Anhaengen() kennen wir bereits aus Listing 2 des zweiten Kursteils.
Zum Schluß lösen wir die Behälter auf und generieren die nach Anfangsbuchstaben sortierte Schlange:
'Behälter aufsammeln
FOR I%=Min_Ascii% TO Max_Ascii%
IF B_Anfang%(I%)<>0 THEN
Ll_Verbinden(S_Anfang%,S_Ende%,B_Anfang%(I%),B_Ende%(I%))
ENDIF
NEXT I%
Die Prozedur L1_Verhinden(R L1_Anfang%,R L1_Ende%, L2_Anfang%, L2_Ende%) hängt die Liste L2 an die Liste L1. Den Prozedurtext zeigt Listing 5.
Radixsort
Beim Behältersortieren ist die Kardinalität des Schlüsselwert-Datentyps die Anzahl der benötigten Behälter. Um Buchstaben mit unserem obigen Datentyp Letter zu sortieren, benötigen wir #Letter=26 Behälter. Entsprechend sortieren wir die Dezimalziffern von "0" bis "9" in #Digit=10 Behälter.
Das Behältersortieren eignet sich nur für Datentypen mit kleiner Kardinalität. Angenommen, Sie wollen Integer-Zahlen (16 Bit) in Behälter sortieren. Dazu brauchen Sie #INTEGER=65536 Behälter. Jeder Behälter speichert mindestens den Schlüssel wert. Wir dimensionieren das Behälterfeld mit DIM B_Key%(65535) für 65536 Integerzahlen (2 Byte). Das sind 128 KByte.
Bei 32-Bit-Zahlen ist diese Sortiermethode aus Speicherplatzgründen nicht realisierbar. Ebenso bei Zeichenketten. Angenommen Sie sortieren Strings mit maximal 3 Zeichen Länge. Es seien 128 verschiedene Zeichen zugelassen (7-Bit-Code). Dann brauchen Sie 128^3=2097152 Behälter.
Eine Erweiterung des Behältersortierens ist das Radixsort. Wir haben den Grundgedanken des Radixsort im Einführungsbeispiel mit den Spielkarten kennengelernt.
(**********************************************
* Radixsort-Algorithmus *
**********************************************)
CONST
K = <Anzahl der Schlüsselfelder>
MinKey1 = <kleinste mögliche Schlüsselwerte
... für die K Schlüssel-Datentypen>
MinKeyK
MaxKey1 = <größte mögliche Schlüsselwerte
... für die K Schlüssel-Datentypen>
MaxKeyK
TYPE
KeyTyp1
...
KeyTypK = <Datentypen, die die möglichen Schlüsselwerte festlegen>
ObjTyp=RECORD (* Datentyp für die zu sortierenden Objekte *)
Key1 : KeyTyp1;
...
KeyK : KeyTypK;
Info : InfoTyp;
END
STyp = <Datentyp für die Realisierung einer
Schlange deren Elemente vom Datentyp ObjTyp sind.>
VAR
S : STyp (* zu sortierende Schlange *)
B1 = ARRAY KeyTyp1 OF STyp
...
BK = ARRAY KeyTypK OF STyp
(* Behälterfelder mit einem Element pro möglichem Schlüsselwert.
Jeder Behälter speichert eine Schlange. *)
i : <Laufvariable zur Selektion der Schlüsselfelder>
j : <Laufvariable zum Zugriff auf die Behälter>
FOR i:=K DOWNTO 1 DO
(* Behältersortieren bzgl. des Schlüsselfelds Keyi *)
(* alle Behälter löschen *)
FOR j:=MinKeyi TO MaxKeyi DO
Lösche Bi(j)
END
(* Schlange S in die Behälter Bi() verteilen *)
WHILE Schlange S nicht leer DO
Entferne Kopf von S und hänge ihn an die
Schlange des zugehörigen Behälters
Bi(Kopf(S).Keyi)
END
(* Behälter Bi() aufsammeln und sortierte Schlange S erzeugen. *)
Erzeuge leere Schlange S
FOR j:=MinKeyi TO MaxKeyi DO
Hänge Schlange Bi(j) an die Schlange S
END
(* Die Schlange S ist nun sortiert bezüglich
der Schlüsselfelder Keyi bis KeyK *)
END (* FOR i *)
(* Die Schlange S ist nun sortiert *)
Bild 16
Warum funktioniert das Spielkartensortierverfahren ?
Jede Spielkarte ist eindeutig durch Farbe (Kreuz, Pik, Herz oder Karo) und Wert (7-10, Bauer, Dame, König, As) charakterisiert. Im ersten Verfahren sortieren wir zuerst nach dem Wert in acht Stapel (Behälter). Die Karten in einem Stapel sind nur bezüglich ihrer Farbe gemischt. Nachdem die Stapel aufeinandergelegt sind, liegen die vier Asse oben, die vier Siebenen unten.
Im zweiten Durchgang können zwei Fälle eintreten: Haben zwei Karten die gleiche Farbe, so kommen sie auf den selben Stapel. Der erste Durchlauf sorgt dafür, daß Karten mit hohem Wert unter Karten mit niedrigem Wert liegen. Also sortieren Sie richtig. Im zweiten Fall haben zwei Karten verschiedene Farben.
Sie kommen somit auf verschiedene Stapel. Das Auflesen der Stapel besorgt die Sortierung.
Wir müssen noch zeigen, daß das Auflesen der Stapel korrekt ist. Es ist zunächst uneinsichtig, warum wir die Stapel einmal von links und einmal von rechts aufeinander legen. Dies ist ein Tribut an die Nutzbarkeit der Methode.
Das Behältersortieren basiert auf FIFO- (Schlange) und nicht auf LIFO-Stapeln (Keller). Es gibt drei Alternativen, um dies bei Karten zu realisieren:
Wir schieben eine neue Karte unter den schon vorhandenen Stapel. Dies ist technisch sehr aufwendig. Anschließend sammeln wir die FIFO-Stapel immer von links nach rechts.
Bei der zweiten Alternative können wir die Karten schneller verteilen: Wir legen die Karten mit dem Blatt nach unten auf die Stapel und sammeln immer von rechts nach links. Dieses Vorgehen entspricht dem ersten, wenn Sie es von unten betrachten. Der Nachteil: Sie sehen den Wert der einzelnen Stapel nicht mehr -Spielkarten sind auf dem Rücken einheitlich.
Die dritte Alternative haben wir oben vorgestellt: Die Karten werden mit dem Blatt nach oben auf die LIFO-Stapel (Keller) gelegt. Die Sammelrichtung wechselt. Wenn Sie einen Keller von oben abbauen und nebenan wiederaufbauen, vertauschen Sie die Reihenfolge der Elemente. Sie überführen den LIFO- in einen FIFO-Stapel (Schlange). Dies macht sich unser Verfahren zunutze.
Diese drei Alternativen führen zum gleichen Ergebnis. Wir haben somit gezeigt, daß das Sortierverfahren korrekt ist.
Das Spielkartensortieren demonstriert den Grundgedanken des Radixsort: Man teilt ein Schlüsselfeld mit großer Kardinalität in mehrere Schlüsselfelder mit kleiner Kardinalität. Auf jedes dieser Teilschlüsselfelder wendet man das Behältersortieren an.
Die Teilschlüsselfelder interpretiert man bezüglich verschiedener Basen (Basis = engl. radix). Daher kommt der Name Radixsort.
Betrachten wir die Datenstruktur, die eine Spielkarte beschreibt.
TYPE
FarbTyp=(Kreuz, Pik, Herz, Karo);
WertTyp=(Sieben, Acht, Neun, Zehn, Bauer, Dame, König, Ass)
Karte=RECORD
Farbe : FarbTyp;
Wert : WertTyp;
END;
Die Datentypen FarbTyp und WertTyp nennt man in Modula-2 Aufzählungstypen, da alle möglichen Werte inklusive Ordnung bei der Definition aufgezählt sind.
Die Kardinalität von Karte ist 32, denn es gibt acht Werte mit jeweils vier Farben. Wir benötigen für das Behältersortieren bezüglich Karte somit 32 Behälter. Es liegt nahe, zwei getrennte Sortierläufe zu starten. Einen bezüglich des Teilschlüsselfelds Farbe und einen bezüglich des Teilschlüsselfelds Wert. Es genügen einmal #Farbe=4 und einmal #Wert=8 Behälter.
Im folgenden bezeichnen wir die Teilschlüsselfelder als Schlüsselfelder. Wir benötigen eine Prioritätsregelung der Schlüsselfelder, um die Reihenfolge der Sortierläufe festzulegen. Je größer die Priorität eines Schlüsselfelds ist, um so größeren Einfluß hat es auf die Sortierung. Primär ordnen wir bezüglich des Schlüsselfelds mit der höchsten Priorität.
Nach Anwendung des ersten Verfahrens sind die Karten primär nach Farben sortiert: Kreuz-7 - Kreuz-As, Pik-7 - Pik-As, Herz-7 - Herz-As, Karo-7 - Karo-As. Das zweite Verfahren ordnet primär nach Werten: Kreuz-7 - Karo-7, Kreuz-8 - Karo-8,..., Kreuz-As - Karo-As.
In welcher Reihenfolge führen wir die einzelnen Durchläufe aus? Allgemein gilt: Je niedriger die Priorität eines Schlüsselfelds, desto früher sortieren wir nach diesem. Wir beginnen mit dem am wenigsten signifikanten Schlüsselfeld. Zum Schluß sortieren wir bezüglich des Schlüsselfeldes mit der höchsten Priorität.
Mit dem gleichen Verfahren sortieren Sie auch mehrere Kartenspiele: Betrachten Sie die Kartenspielart als dritten Schlüssel. Verteilen Sie zuerst nach Wert und Farbe. Im dritten Durchlauf ordnen Sie die verschiedenen Kartenspiele.
Allgemein sortiert Radixsort eine Datenstruktur mit dem Aufbau
TYPE ObjTyp=RECORD
Key1 : KeyTyp1;
...
KeyK : KeyTypK;
Info : InfoTyp;
END
Key1 bis KeyK sind K Schlüsselfelder. Key1 habe die höchste und KeyK die niedrigste Priorität. Info steht stellvertretend für weitere Komponenten.
Für jedes Schlüsselfeld benötigen wir eigene Behälter Bi(). Der Index i besagt, daß die Behälter zur Sortierung bezüglich des Schlüsselfeldes KeyTypi dienen. Als grobe Strukur des Radixsort-Algorithmus' ergibt sich somit
FOR i:=K DOWNTO 1 DO
Behältersortieren bzgl.
Schlüsselfelds Keyi
in die Behälter Bi()
END
Die FOR-Schleife beginnt mit dem Schlüsselfeld, das die niedrigste Priorität hat. Zum Schluß sortiert sie bezüglich Keyi - dem Schlüsselfeld mit der höchsten Priorität. Bild 16 zeigt den kompletten Algorithmus zur Radixsortierung.
Versuchen Sie einmal, Radixsort auf die Sortierung von Strings anzuwenden. Wir stellen im nächsten Kursteil die Lösung und einige Optimierungen in Omikron.BASIC und Modula-2 vor.
Literatur:
Aho, Hopcorft, Ullman, Data Structures and Algorithms, Addison Wesley Donald E. Knuth, The Art of Computer Programming, Vol. 3 Sorting and Searching, Addison Wesley, S. 170ff
Kurt Mehlhorn, Datenstrukturen und effiziente Algorithmen, Band 1 Sortieren und Suchen, B.G. Teuhner Stuttgart
(**********************************************
* Listing 4 *
* Behältersortieren mit linearen Listen *
* *
* Sven Krüppel 1.1.1991, (c) MAXON Computer *
* geschrieben mit dem ETH-Modula 2-System *
**********************************************)
MODULE Listing4;
FROM InOut IMPORT Write,WriteString,WriteLn;
FROM Heap IMPORT Allocate, Deallocate;
CONST MaxN=20; (* Anzahl max. zu sortierender Records *)
MinKey="A"; (* kleinster Schlüsselwert *)
MaxKey="Z"; (* größter Schlüsselwert *)
MaxLaenge=15; (* max. Stringlänge *)
TYPE String = ARRAY [1..MaxLaenge] OF CHAR;
KeyTyp = [MinKey..MaxKey]; (* Wertebereich der Schlüsselwerte *)
ObjTyp = RECORD (* Record für Daten *)
Key : KeyTyp; (* Schlüssel *)
Text: String;
(* <weitere Infokomponenten> *)
END;
ObjFTyp= ARRAY [1..MaxN] OF ObjTyp;
ObjLPtr= POINTER TO ObjLTyp;
ObjLTyp= RECORD (* Schlangenelement *)
Obj : ObjTyp;
Next : ObjLPtr;
END;
STyp = RECORD (* Schlangen-, Listentyp*)
Anfang : ObjLPtr;
Ende : ObjLPtr;
END;
VAR N : CARDINAL; (* Anzahl zu sortierender Records *)
TF : ObjFTyp; (* Feld mit Testdaten *)
TL : STyp; (* Liste mit Testdaten *)
p : ObjLPtr; (* Hilfszeiger *)
i : CARDINAL;
(**********************************************
* Element an eine lineare Liste anhängen *
* Dies entspricht dem Einfügen in eine *
* Schlange *
**********************************************)
PROCEDURE LLAnhaengen(VAR L:STyp; P:ObjLPtr);
(* Element, auf das 'P' zeigt, an die lineare
Liste 'L' hängen. Diese Operation ent-
spricht dem Einfügen in eine Schlange.
*)
BEGIN
IF P <> NIL THEN
P^.Next:=NIL; (* neues Listenende markieren *)
IF L.Anfang=NIL THEN (* Liste ist leer *)
L.Anfang:=P;
ELSE (* Liste war nicht leer *)
L.Ende^.Next:=P;(* Element anhängen, auf das P zeigt *)
END;
L.Ende:=P; (* Zeiger auf das Listenende umbiegen *)
END (* IF *)
END LLAnhaengen;
(**********************************************
* Zwei Listen verbinden *
**********************************************)
PROCEDURE LLVerbinden(VAR L1, L2: STyp);
(* Liste 'L2' wird an Liste 'L1' gehängt. Die
Ergebnisliste ist 'L1'.
*)
BEGIN
IF L1.Anfang=NIL THEN (* 1. Liste ist leer *)
L1:=L2;
ELSIF L2.Anfang<>NIL THEN (* 2. Liste nicht leer *)
L1.Ende^.Next:=L2.Anfang; (* verbinden *)
L1.Ende:=L2.Ende
END;
END LLVerbinden;
(**********************************************
* Liste ausgeben *
**********************************************)
PROCEDURE LLAusgeben(L : STyp);
VAR p : ObjLPtr;
BEGIN
p:=L.Anfang;
WHILE p<>NIL DO
Write(p^.Obj.Key);
WriteString(" ");
WriteString(p^.Obj.Text);
WriteLn;
p:=p^.Next;
END(*WHILE*);
WriteLn;
END LLAusgeben;
(**********************************************
* *
* Behältersortieren *
* *
**********************************************)
PROCEDURE BinSort(VAR S : STyp);
VAR B : ARRAY KeyTyp OF STyp; (* Feld mit Behältern *)
p : ObjLPtr; (* Hilfszeiger *)
i : KeyTyp; (* Laufvariable *)
BEGIN
(* Behälter löschen *)
FOR i:=MinKey TO MaxKey DO
B[i].Anfang:=NIL;
B[i].Ende:=NIL;
END;
(* Schlange S in Behälter sortieren *)
(* Es wird jeweils der Listenanfang von S
in einen Behälter einsortiert.
LLAnhaengen zerstört den Next-Zeiger
des Listenanfangs. Deshalb muss ein Zeiger
auf das jeweils zweite Listenelement
zwischengespeichert werden.
*)
WHILE S.Anfang<>NIL DO
p:=S.Anfang^.Next; (* Zeiger auf nächstes Element retten *)
LLAnhaengen(B[S.Anfang^.Obj.Key],S.Anfang);
S.Anfang:=p;
END;
(* Behälter auflösen und sortierte Liste generieren *)
S.Anfang:=NIL;
S.Ende:=NIL;
FOR i:=MinKey TO MaxKey DO
IF B[i].Anfang<>NIL THEN (* Schlange in Behälter B[i] nicht leer => verbinden *)
LLVerbinden(S,B[i]);
END;
END;
END BinSort;
(**********************************************
* Eine lineare Liste aus einem Feld mit *
* Daten generieren. *
**********************************************)
PROCEDURE ErzeugeListeAusFeld(F : ObjFTyp; VAR L : STyp);
(* Die Liste L wird zurückgegeben *)
VAR p : ObjLPtr; (* Hilfszeiger *)
i : CARDINAL;
BEGIN
L.Anfang:=NIL;
L.Ende:=NIL;
FOR i:=1 TO N DO
Allocate(p,SIZE(ObjLTyp));
p^.Obj.Key:=F[i].Key;
p^.Obj.Text:=F[i].Text;
LLAnhaengen(L,p);
END(*FOR*);
END ErzeugeListeAusFeld;
BEGIN (* Hauptprogramm *)
(* Feld mit Testdaten initialisieren *)
TF[1].Key:="B"; TF[1].Text:="Bruno";
TF[2].Key:="A"; TF[2].Text:="Anna";
TF[3].Key:="K"; TF[3].Text:="Klaus";
TF[4).Key:="F"; TF[4].Text:="Fritz";
TF[5].Key:="K"; TF[5].Text:="Kuni";
TF[6].Key:="H"; TF[6].Text:="Heike";
TF[7].Key:="F"; TF[7].Text:="Franz";
TF[8].Key:="Z"; TF[8].Text:="Zenzi";
TF[9].Key:="B"; TF[9].Text:="Bernd";
TF[10].Key:="E"; TF[10].Text:="Emil";
N:=10;
(* Liste mit Testdaten generieren *)
ErzeugeListeAusFeld(TF,TL);
LLAusgeben(TL);
BinSort(TL); (* Liste sortieren *)
LLAusgeben(TL);
END Listing4.
'********************************************
'* Listing 5 *
'* Sven Krüppel, 2.1.91, (c) MAXON Computer *
'********************************************
DEF PROC Ll_Verbinden(R Anfang1%,R Ende1%,Anfang2%,Ende2%)
'Hängt die durch Anfang2% und Ende2%
'definierte Liste an die durch Anfang1% und
'Ende1% definierte Liste.
IF Anfang1%=0 THEN ' 1. Liste ist leer.
Anfang1%=Anfang2% ' funktioniert auch,
Ende1%=Ende2% ' wenn beide leer
ELSE ' 1. Liste ist nicht leer
IF Anfang2%<>0 THEN '2. Liste nicht leer
Wl_Next%(Ende1%)=Anfang2%' verbinden
Ende1%=Ende2%
ENDIF
ENDIF
RETURN 'Ll_Verbinden
Sven Krüppel