Aufgabe 1 - Prolog Sortieren

Aufgabenstellung

Ein einfacher Sortieralgorithmus ist wie folgt definiert: Eine unsortierte Liste wird durch die Wahl eines Trennelements in zwei Hälften unterteilt. Alle Elemente, die kleiner als das Trennelement sind, werden in der linken Liste gespeichert; alle, die größer sind, in der rechten. Mit den beiden Teillisten „links“ und „rechts“ wird das Verfahren dann erneut durchgeführt. Dies geschieht solange, bis die Liste sortiert ist.

Wann bricht der Algorithmus ab?
Implementieren Sie den Sortieralgorithmus in PROLOG.

1. Wann bricht der Algorithmus ab?

Der Algorithmus bricht ab (d.h. die Rekursion endet), wenn der Algorithmus versucht eine leere Liste ([]) zu sortieren. In diesem Fall gibt es nichts mehr zu unterteilen, und die leere Liste wird als sortiert zurückgegeben.

In der Praxis bedeutet das: Die Listen werden immer weiter in Teillisten zerlegt, bis diese Teillisten leer sind. Da eine Liste mit nur einem Element beim nächsten Schritt in eine leere Liste zerlegt wird, führen auch einelementige Listen im darauffolgenden Rekursionsschritt zum Abbruch.

2. Implementierung in PROLOG

Der verwendete Algorithmus ist bekannt als Quicksort-Verfahren.

Funktionsweise des Codes

1. Das Aufteilen (Partitionieren)

Wir brauchen ein Hilfsprädikat, nennen wir es aufteilen. Es soll eine Liste anhand eines Trennelements (Pivot) durchgehen und zwei neue Listen erzeugen: eine für kleinere/gleiche Elemente und eine für größere.

Das Prädikat sieht so aus: aufteilen(Liste, Pivot, Kleinere, Groessere).

Dafür gibt es drei Fälle:

Fall A: Die Liste ist leer (Abbruchbedingung)

Wenn die Liste leer ist, sind auch die beiden Teillisten leer.

aufteilen([], _, [], []).

Fall B: Das Element ist kleiner oder gleich dem Pivot

Wenn der Kopf der Liste (K) kleiner oder gleich dem Pivot (P) ist, gehört er in die Liste der Kleineren. Danach machen wir mit dem Rest (Rest) weiter.

aufteilen([K|Rest], P, [K|KleinereRest], Groessere) :-
    K =< P,
    aufteilen(Rest, P, KleinereRest, Groessere).

Fall C: Das Element ist größer als der Pivot

Wenn der Kopf (K) größer als der Pivot (P) ist, gehört er in die Liste der Groesseren.

aufteilen([K|Rest], P, Kleinere, [K|GroessereRest]) :-
    K > P,
    aufteilen(Rest, P, Kleinere, GroessereRest).

2. Der Sortier-Algorithmus (Quicksort)

Nun bauen wir das Hauptprädikat quicksort(Unsortiert, Sortiert).

Auch hier gibt es zwei Fälle:

Fall A: Die Basisfall (Leere Liste)

Eine leere Liste ist bereits sortiert.

quicksort([], []).

Fall B: Der rekursive Schritt

Hier passiert folgendes:

Wir wählen den Kopf der Liste als Trennelement (Pivot).
Wir unterteilen den Rest der Liste in Links (kleiner) und Rechts (größer).
Wir sortieren die linke Liste (rekursiv).
Wir sortieren die rechte Liste (rekursiv).
Wir fügen zusammen: Sortierte Linke + [Pivot] + Sortierte Rechte.

quicksort([Pivot|Rest], Sortiert) :-
    aufteilen(Rest, Pivot, Links, Rechts), % 1. Aufteilen
    quicksort(Links, SortiertLinks),       % 2. Linke Seite sortieren
    quicksort(Rechts, SortiertRechts),     % 3. Rechte Seite sortieren
    append(SortiertLinks, [Pivot|SortiertRechts], Sortiert). % 4. Zusammenfügen

Hinweis: append/3 ist ein eingebautes Prolog-Prädikat, das Listen aneinanderhängt.

Code (`sort.pl`)

Hier ist der komplette Code

% --- 1. Hilfsprädikat: Aufteilen ---

% Basisfall A: Leere Liste ergibt leere Teillisten
aufteilen([], _, [], []).

% Fall B: Element ist kleiner/gleich Pivot -> in die linke Liste (Kleinere)
aufteilen([K|Rest], Pivot, [K|Kleinere], Groessere) :-
    K =< Pivot,
    aufteilen(Rest, Pivot, Kleinere, Groessere).

% Fall C: Element ist größer Pivot -> in die rechte Liste (Groessere)
aufteilen([K|Rest], Pivot, Kleinere, [K|Groessere]) :-
    K > Pivot,
    aufteilen(Rest, Pivot, Kleinere, Groessere).

% --- 2. Hauptprädikat: Quicksort ---

% Basisfall A: Eine leere Liste ist sortiert
quicksort([], []).

% Fall B: Rekursiver Schritt
quicksort([Pivot|Rest], Sortiert) :-
    % 1. Liste aufteilen anhand des Pivots
    aufteilen(Rest, Pivot, Links, Rechts),

    % 2. Die beiden Hälften rekursiv sortieren
    quicksort(Links, SortiertLinks),
    quicksort(Rechts, SortiertRechts),

    % 3. Alles zusammenfügen: Links + Pivot + Rechts
    append(SortiertLinks, [Pivot|SortiertRechts], Sortiert).

Nutzung

?- quicksort([ ], Ergebnis).

Ergebnis = ...