Gnome Sort
Der Gnome Sort basiert auf dem Verfahren, mit dem Gartenzwerge ihre Blumentöpfe sortieren. Die Zwerge wenden beim Sortieren drei Regeln an.
1. Wenn der Zwerg am Anfang der Topfreihe steht, es also keinen Topf vor ihm gibt, macht er einen Schritt vorwärts.
2. Wenn der Zwerg am Ende der Topfreihe steht - es gibt keinen Topf nach ihm - ist er fertig mit dem Sortieren.
3. Wenn der Zwerg zwischen zwei Töpfen steht, vergleicht er die Töpfe: Sind die Töpfe in der richtigen Reihenfolge, macht er einen Schritt vorwärts. Sonst vertauscht er die Töpfe und macht einen Schritt rückwärts.
Der Funktion gnome-sort übergibt man die zu sortierenden Elemente als Liste und die Vergleichsfunktion. Sie stellt den Zwerg an den Anfang der Reihe und lässt ihn dann Schritte machen.
(defproc gnome-sort (elements predicate)
(step nil elements predicate))
Die Funktion step bekommt die Liste mit den Elementen vor dem Zwerg, die Liste mit den Elementen hinter dem Zwerg und die Vergleichsfunktion. Der cond-Ausdruck unterscheidet die drei oben genannten Regeln und handelt dann entsprechend.
(defproc step (previous next predicate)
(cond
((null? previous)
(step-forward nil next predicate))
((null? next)
previous)
(t
(let
((p (first (last previous)))
(n (first next)))
(if
(or
(predicate p n)
(= p n))
(step-forward previous next predicate)
(swap-and-step-backward previous next predicate))))))
Die Funktion step-forward macht einen Schritt vorwärts. Das bedeutet, das erste Element hinter dem Zwerg wird zum letzten Element vor dem Zwerg.
(defproc step-forward (previous next predicate)
(step
(append previous (list (first next)))
(rest next)
predicate))
Die Funktion swap-and-step-backward vertauscht die Töpfe und macht dann einen Schritt rückwärts. Vertauschen bedeutet, dass der letzte Topf vor dem Zwerg und der erste Topf hinter dem Zwerg ihre Plätze tauschen.
(defproc swap-and-step-backward (previous next predicate)
(step-backward
(append (butlast previous) (list (first next)))
(append (last previous) (rest next))
predicate))
Schließlich macht die Funktion step-backward einen Schritt rückwärts. Der letzte Topf vor dem Zwerg wird zum ersten Topf hinter dem Zwerg.
(defproc step-backward (previous next predicate)
(step
(butlast previous)
(append (last previous) next)
predicate))
Links
http://www.geeksforgeeks.org/gnome-sort-a-stupid-one/
https://de.wikipedia.org/wiki/Gnomesort
1. Wenn der Zwerg am Anfang der Topfreihe steht, es also keinen Topf vor ihm gibt, macht er einen Schritt vorwärts.
2. Wenn der Zwerg am Ende der Topfreihe steht - es gibt keinen Topf nach ihm - ist er fertig mit dem Sortieren.
3. Wenn der Zwerg zwischen zwei Töpfen steht, vergleicht er die Töpfe: Sind die Töpfe in der richtigen Reihenfolge, macht er einen Schritt vorwärts. Sonst vertauscht er die Töpfe und macht einen Schritt rückwärts.
Der Funktion gnome-sort übergibt man die zu sortierenden Elemente als Liste und die Vergleichsfunktion. Sie stellt den Zwerg an den Anfang der Reihe und lässt ihn dann Schritte machen.
(defproc gnome-sort (elements predicate)
(step nil elements predicate))
Die Funktion step bekommt die Liste mit den Elementen vor dem Zwerg, die Liste mit den Elementen hinter dem Zwerg und die Vergleichsfunktion. Der cond-Ausdruck unterscheidet die drei oben genannten Regeln und handelt dann entsprechend.
(defproc step (previous next predicate)
(cond
((null? previous)
(step-forward nil next predicate))
((null? next)
previous)
(t
(let
((p (first (last previous)))
(n (first next)))
(if
(or
(predicate p n)
(= p n))
(step-forward previous next predicate)
(swap-and-step-backward previous next predicate))))))
Die Funktion step-forward macht einen Schritt vorwärts. Das bedeutet, das erste Element hinter dem Zwerg wird zum letzten Element vor dem Zwerg.
(defproc step-forward (previous next predicate)
(step
(append previous (list (first next)))
(rest next)
predicate))
Die Funktion swap-and-step-backward vertauscht die Töpfe und macht dann einen Schritt rückwärts. Vertauschen bedeutet, dass der letzte Topf vor dem Zwerg und der erste Topf hinter dem Zwerg ihre Plätze tauschen.
(defproc swap-and-step-backward (previous next predicate)
(step-backward
(append (butlast previous) (list (first next)))
(append (last previous) (rest next))
predicate))
Schließlich macht die Funktion step-backward einen Schritt rückwärts. Der letzte Topf vor dem Zwerg wird zum ersten Topf hinter dem Zwerg.
(defproc step-backward (previous next predicate)
(step
(butlast previous)
(append (last previous) next)
predicate))
Links
http://www.geeksforgeeks.org/gnome-sort-a-stupid-one/
https://de.wikipedia.org/wiki/Gnomesort