Lisp lernen, Teil 2: Quicksort implementieren

Quicksort ist ein schneller und bekannter Algorithmus zum Sortieren von Daten. Da er rekursiv arbeitet, eignet er sich gut als Übungsaufgabe. An der Implementierung lassen sich zudem einige interessante Konstrukte von Lisp zeigen.

In Pocket speichern vorlesen Druckansicht 1 Kommentar lesen
Lesezeit: 5 Min.
Von
  • Golo Roden
Inhaltsverzeichnis

Quicksort ist ein schneller und bekannter Algorithmus zum Sortieren von Daten. Da er rekursiv arbeitet, eignet er sich gut als Übungsaufgabe. An der Implementierung lassen sich zudem einige interessante Konstrukte von Lisp zeigen.

Das Prinzip von Quicksort lässt sich leicht erklären. Aus einer gegebenen Liste wählt man ein beliebiges Element, das sogenannte Pivot-Element. Anschließend zerlegt man die Liste in zwei Listen: Die eine enthält alle Werte, die kleiner als das Pivot-Element sind, die andere alle, die größer sind. Anschließend werden beide Teillisten erneut durch Quicksort sortiert und das Ergebnis schließlich wieder zusammengefügt.

Eine Funktion, die den Algorithmus implementiert, lässt sich entsprechend einfach definieren. Gesucht ist eine Funktion quick-sort, die eine Liste list als Parameter entgegennimmt und sie in sortierter Form zurückgibt. Ist die Liste leer, ist die leere Liste zurückzugeben.

Der erste Schritt fällt leicht. Da die leere Liste in Lisp äquivalent zu dem Wert NIL ist, der dem in anderen Sprachen logischen Wert false entspricht, lässt sich auf einfachem Weg prüfen, ob eine Liste leer ist oder nicht. Es genügt, sie IF als Bedingung zu übergeben. Wird die Bedingung als NIL evaluiert, ist die Liste leer. Da sie in dem Fall bereits dem gewünschten Ergebnis entspricht, kann man sie direkt zurückgeben:

(defun quick-sort (list)
(if list
<...>
list))

Das gleiche gilt, wenn die Liste nur ein Element enthält. In dem Fall ist sie nämlich bereits sortiert. Enthält eine Liste nur ein Element, ist der Rest der Liste leer: Die Funktion CDR gibt daher NIL zurück. Praktischerweise gibt CDR jedoch auch dann NIL zurück, wenn man der Funktion die leere Liste übergibt. Die Funktion quick-sort lässt sich daher wie folgt erweitern und deckt bereits die leere Liste und alle ein-elementigen Listen ab:

(defun quick-sort (list)
(if (cdr list)
<...>
list))

Nun gilt es, die eigentliche Arbeit zu leisten. Dazu benötigt man zunächst ein Pivot-Element. Da die Liste nun mindestens zwei Elemente enthält, kann man als Pivot-Element das erste Element verwenden. Um zu verdeutlichen, dass es sich bei dem gewählten Element um das Pivot-Element handelt, bietet sich die Definition einer lokalen Variable mit LET an:

(defun quick-sort (list)
(if (cdr list)
(let ((pivot (car list)))
<...>)
list))

Der Rest ist einfach. Prinzipiell muss die Liste nun lediglich in drei Teillisten zerlegt werden: Die erste Liste enthält alle Werte, die kleiner als pivot sind, die zweite alle, die größer sind, und die dritte alle, die gleich sind. Fügt man die Listen nachher in der richtigen Reihenfolge zusammen, erhält man das gewünschte sortierte Ergebnis.

Um aus list die passende Teilliste zu extrahieren lässt sich die Funktion REMOVE-IF-NOT verwenden, die eine neue Liste zurückgibt, die nur noch jene Elemente enthält, für die ein bestimmtes Kriterium gilt. Um beispielsweise die Teilliste zu erhalten, die nur die kleineren Elemente enthält, dient der folgende Ausdruck:

(remove-if-not (lambda (n) (< n pivot)) list)

Auf dem gleichen Weg kann man auch den Code formulieren, der die beiden anderen Teillisten ermittelt. Zum Zusammenfügen der Listen dient die APPEND-Funktion, wobei quick-sort für die beiden äußeren Listen nochmals rekursiv aufzurufen ist:

(defun quick-sort (list)
(if (cdr list)
(let ((pivot (car list)))
(append (quick-sort (remove-if-not (lambda (n) (< n pivot)) list))
(remove-if-not (lambda (n) (= n pivot)) list)
(quick-sort (remove-if-not (lambda (n) (> n pivot)) list))))
list))

Die Funktion funktioniert bereits, wie verschiedene Aufrufe beweisen:

(quick-sort '())
; => NIL

(quick-sort '(23))
; => (23)

(quick-sort '(23 5 42 17 2))
; => (2 5 17 23 42)

Allerdings enthält der Code noch einige Redundanz. Um sie zu verringern, lässt sich eine Hilfsfunktion filter definieren, der man den gewünschten Operator übergibt. Das funktioniert, da die Sprache Funktionen höherer Ordnung unterstützt.

Damit man weder die Liste noch das Pivot-Element übergeben muss, bietet es sich an, die Funktion ebenfalls lokal zu definieren, also innerhalb der Funktion quick-sort. Dazu dient FLET. Da der Operator in dem Fall als Parameter übergeben wird, muss der Lambda-Ausdruck nun allerdings FUNCALL verwenden, um den Vergleich durchzuführen:

(defun quick-sort (list)
(if (cdr list)
(let ((pivot (car list)))
(flet ((filter (operator)
(remove-if-not
(lambda (n) (funcall operator n pivot))
list)))
(append (quick-sort (filter #'<))
(filter #'=)
(quick-sort (filter #'>)))))
list))

Die Aufgabe ist damit gelöst. Ein Blick auf den Code zeigt, wie einfach sich Rekursion und Funktionen höherer Ordnung in Lisp verwenden lassen, und wie praktisch das in der Sprache verwendete Scoping zur Definition lokaler Variablen und Funktionen ist.

tl;dr: Das Beispiel des Quicksort-Algorithmus lässt sich in Lisp gut implementieren, wobei vor allem Rekursion und Funktionen höherer Ordnung zum Einsatz kommen. Auch das in Lisp verwendete Scoping hilft, den eigentlichen Kern der Funktion ausgesprochen lesbar zu gestalten. ()