Sortieralgorithmen mit Prolog
Sortierverfahren gehören zum klassischen Bestand der Informatik und sind daher auch Bestandteil des Informatikunterrichts, u. a. im Bereich Objektorientierte Modellierung. Die Grundideen einiger Sortierverfahren lassen sich allerdings auch in Prolog sehr elegant ausdrücken. Wir werden uns hier allerdings auf das Sortieren von Zahlenlisten beschränken.
Inhaltsverzeichnis
Liste von Zufallszahlen
Beim Testen der zu entwickelnden Sortierverfahren wird es auf Dauer mühselig und ineffektiv sein, die zu ordnenden Listen immer explizit einzugeben. Daher soll hier ein Prädikat randomliste geschaffen werden, welches Zufallslisten erzeugt.
Zufallszahlen
SWI-Prolog bietet von Haus aus die Möglichkeit, Zufallszahlen (und auch Listen mit Zufallszahlen) zu erzeugen:
| Prädikat | Beschreibung |
| random(-Z) | Es wird eine rationale Zufallszahl Z generiert mit 0 <= Z < 1. |
| random(+L,+H,-Z) | Es wird eine ganzzahlige Zufallszahl Z generiert mit L < Z < H. |
| randset(+S,+M,-L) | Es wird eine sortierte Liste L mit ganzzahligen Zufallszahlen erzeugt. S gibt die Anzahl der Elemente an und M das wertige Maximum jeder Zufallszahl. |
Weshalb müssen wir uns nun noch eine neues Prädikat randomliste erarbeiten? Nach einem kurzen Test des Prädikats randset sollte die Antwort nicht schwer fallen ...
Das Prädikat random/3 soll aber im Weiteren Verlauf Verwendung finden.
Liste von Zufallszahlen
Nun benötigen wir nur noch ein Prädikat, welches für eine bestimmten Maximalwert H und eine gewünschte Anzahl S eine Liste zufälliger Zahlen erstellt:
% randomliste(+S,+H,-L) -- Liste von Zufallszahlen der Mächtigkeit S und H als Maximalwert randomliste(0,_,[]). randomliste(N,H,[Z|Zs]) :- N > 0, N1 is N - 1, random(0,H,Z), randomliste(N1,H,Zs).
Prädikat sort
SWI-Prolog besitzt ein Standard-Prädikat sort, welches Listen sortiert. Uns geht es an dieser Stelle allerdings darum, die klassischen (schon bekannten) Sortierverfahren in Prolog umzusetzen.
Sortierverfahren
Folgende Sortierverfahren werden diskutiert:
