Lampsort
Quicksort ist ein Algorithmus zum Sortieren von Arrays. Er wurde von C. Antony R. Hoare 1960 entwickelt. Am Pseudocode von Quicksort erkennt man, dass sich die Prozedur quicksort selbst aufruft, also rekursiv ist.
prozedur quicksort(links, rechts)
falls links < rechts dann
teiler := teile(links, rechts)
quicksort(links, teiler - 1)
quicksort(teiler + 1, rechts)
ende
ende
Die Hauptarbeit des Sortierens erledigt die Funktion teile.
funktion teile(links, rechts)
i := links
j := rechts - 1
pivot := daten[rechts]
wiederhole
wiederhole solange daten[i] ≤ pivot und i < rechts
i := i + 1
ende
wiederhole solange daten[j] ≥ pivot und j > links
j := j - 1
ende
falls i < j dann
tausche daten[i] mit daten[j]
ende
solange i < j
falls daten[i] > pivot dann
tausche daten[i] mit daten[rechts]
ende
antworte i
ende
Sie bearbeitet den Ausschnitt des Arrays zwischen den Elementen mit den Indexen links und rechts.
Dazu wählt sie zuerst ein Element pivot aus (hier das Element mit dem Index rechts). Dann sortiert sie Elemente, die kleiner sind, vor das ausgewählte Element und Elemente, die größer sind, dahinter.
Z.B. wird so für den Array-Ausschnitt 2 4 1 5 3 die 3 als pivot verwendet. Die beiden inneren Schleifen bringen die Elemente in die Reihenfolge 2 1 4 5 3 - Elemente kleiner als 3 stehen links und größere Elemente stehen rechts. Die abschließende Fallunterscheidung läuft in den Dann-Zweig und vertauscht 3 und 4, so dass das Resultat 2 1 3 5 4 ist.
Die Funktion liefert schließlich den Index des Pivot-Elements als Rückgabewert.
Lampsort (nach Leslie Lamport) ist eine nicht-rekursive Variante von Quicksort. Anstelle der rekursiven Aufrufe wird eine Liste verwendet, um nachzuhalten, welche Teile des Arrays noch bearbeitet werden müssen.
Die oben erwähnte Liste enthält Instanzen der Struktur interval. Diese Instanzen repräsentieren Abschnitte des Arrays.
(defstruct interval (low high)
(and
(integer? low)
(integer? high)))
Die Methode size berechnet die Zahl der Elemente in einem Abschnitt.
(defmethod size ((this interval)) t
(+ 1 (. this high) (- (. this low))))
Die Prozedur lampsort realisiert den Algorithmus.
(defproc lampsort (elements predicate)
(let
((array (to-array elements))
(intervals (list (new interval 0 (- (length elements) 1))))
(pivot nil))
(loop
(when (null? intervals)
(return (to-list array)))
(let
((picked (pop intervals)))
(when (> (size picked) 1)
(setq pivot (partition array (. picked low) (. picked high) predicate))
(push (new interval (. picked low) (- pivot 1)) intervals)
(push (new interval (+ pivot 1) (. picked high)) intervals))))))
Die Prozedur partition ist die Umsetzung der oben beschriebenen Funktion teile.
(defproc partition (array low high predicate)
(let
((i low)
(j (- high 1))
(value ([] array high)))
(loop
(loop
(unless (and (not (predicate value ([] array i)))
(< i high))
(return nil))
(setq i (+ i 1)))
(loop
(unless (and (not (predicate ([] array j) value))
(> j low))
(return nil))
(setq j (- j 1)))
(if
(< i j)
(swap array i j)
(progn
(when (predicate value ([] array i))
(swap array i high))
(return i))))))
Eine Reihe von Hilfsprozeduren werden von lampsort und partition verwendet. swap vertauscht zwei Array-Elemente. to-array wandelt eine Liste in ein Array um. to-list wandelt umgekehrt ein Array in eine Liste. [] liefert ein Array-Element und []= setzt ein Array-Element.
(defproc swap (array i j)
(let
((value-i ([] array i))
(value-j ([] array j)))
(progn
([]= array i value-j)
([]= array j value-i))))
(defproc to-array (elements)
(let
((array (make-array (list (length elements))))
(index 0))
(dolist (element elements array)
([]= array index element)
(setq index (+ index 1)))))
(defproc to-list (array)
(let
((elements nil))
(dotimes (index (first (array-dimensions array)) (reverse elements))
(push ([] array index) elements))))
(defproc [] (array i)
(get-array-element array (list i)))
(defproc []= (array i v)
(set-array-element array (list i) v))
Quellen
https://bertrandmeyer.com/2014/12/07/lampsort/
http://www.computerhistory.org/timeline/?year=1960
https://de.wikipedia.org/wiki/Quicksort
https://en.wikipedia.org/wiki/Quicksort
prozedur quicksort(links, rechts)
falls links < rechts dann
teiler := teile(links, rechts)
quicksort(links, teiler - 1)
quicksort(teiler + 1, rechts)
ende
ende
Die Hauptarbeit des Sortierens erledigt die Funktion teile.
funktion teile(links, rechts)
i := links
j := rechts - 1
pivot := daten[rechts]
wiederhole
wiederhole solange daten[i] ≤ pivot und i < rechts
i := i + 1
ende
wiederhole solange daten[j] ≥ pivot und j > links
j := j - 1
ende
falls i < j dann
tausche daten[i] mit daten[j]
ende
solange i < j
falls daten[i] > pivot dann
tausche daten[i] mit daten[rechts]
ende
antworte i
ende
Sie bearbeitet den Ausschnitt des Arrays zwischen den Elementen mit den Indexen links und rechts.
Dazu wählt sie zuerst ein Element pivot aus (hier das Element mit dem Index rechts). Dann sortiert sie Elemente, die kleiner sind, vor das ausgewählte Element und Elemente, die größer sind, dahinter.
Z.B. wird so für den Array-Ausschnitt 2 4 1 5 3 die 3 als pivot verwendet. Die beiden inneren Schleifen bringen die Elemente in die Reihenfolge 2 1 4 5 3 - Elemente kleiner als 3 stehen links und größere Elemente stehen rechts. Die abschließende Fallunterscheidung läuft in den Dann-Zweig und vertauscht 3 und 4, so dass das Resultat 2 1 3 5 4 ist.
Die Funktion liefert schließlich den Index des Pivot-Elements als Rückgabewert.
Lampsort (nach Leslie Lamport) ist eine nicht-rekursive Variante von Quicksort. Anstelle der rekursiven Aufrufe wird eine Liste verwendet, um nachzuhalten, welche Teile des Arrays noch bearbeitet werden müssen.
Die oben erwähnte Liste enthält Instanzen der Struktur interval. Diese Instanzen repräsentieren Abschnitte des Arrays.
(defstruct interval (low high)
(and
(integer? low)
(integer? high)))
Die Methode size berechnet die Zahl der Elemente in einem Abschnitt.
(defmethod size ((this interval)) t
(+ 1 (. this high) (- (. this low))))
Die Prozedur lampsort realisiert den Algorithmus.
(defproc lampsort (elements predicate)
(let
((array (to-array elements))
(intervals (list (new interval 0 (- (length elements) 1))))
(pivot nil))
(loop
(when (null? intervals)
(return (to-list array)))
(let
((picked (pop intervals)))
(when (> (size picked) 1)
(setq pivot (partition array (. picked low) (. picked high) predicate))
(push (new interval (. picked low) (- pivot 1)) intervals)
(push (new interval (+ pivot 1) (. picked high)) intervals))))))
Die Prozedur partition ist die Umsetzung der oben beschriebenen Funktion teile.
(defproc partition (array low high predicate)
(let
((i low)
(j (- high 1))
(value ([] array high)))
(loop
(loop
(unless (and (not (predicate value ([] array i)))
(< i high))
(return nil))
(setq i (+ i 1)))
(loop
(unless (and (not (predicate ([] array j) value))
(> j low))
(return nil))
(setq j (- j 1)))
(if
(< i j)
(swap array i j)
(progn
(when (predicate value ([] array i))
(swap array i high))
(return i))))))
Eine Reihe von Hilfsprozeduren werden von lampsort und partition verwendet. swap vertauscht zwei Array-Elemente. to-array wandelt eine Liste in ein Array um. to-list wandelt umgekehrt ein Array in eine Liste. [] liefert ein Array-Element und []= setzt ein Array-Element.
(defproc swap (array i j)
(let
((value-i ([] array i))
(value-j ([] array j)))
(progn
([]= array i value-j)
([]= array j value-i))))
(defproc to-array (elements)
(let
((array (make-array (list (length elements))))
(index 0))
(dolist (element elements array)
([]= array index element)
(setq index (+ index 1)))))
(defproc to-list (array)
(let
((elements nil))
(dotimes (index (first (array-dimensions array)) (reverse elements))
(push ([] array index) elements))))
(defproc [] (array i)
(get-array-element array (list i)))
(defproc []= (array i v)
(set-array-element array (list i) v))
Quellen
https://bertrandmeyer.com/2014/12/07/lampsort/
http://www.computerhistory.org/timeline/?year=1960
https://de.wikipedia.org/wiki/Quicksort
https://en.wikipedia.org/wiki/Quicksort