Startseite < Informatik < Algorithmen < Sortieren < BucketSort RadixSort / QuickSort MergeSort HeapSort / BubbleSort SelectionSort InsertionSort / [ DRUCK , 2004 , 2005 , 2006 , 2007 , 2008 , 2009 ] SlowSort BogoSort > Komprimieren Suchen / Primzahltest > Datenstrukturen / Software-Engineering / Programmiersprachen / Künstliche Intelligenz > Schach Privates / Inhalt >
SlowSort
Ineffizienter kann man nicht mehr sortieren!
Einführung Theorie: SlowSort
Definition
SlowSort ist ein sehr uneffizienter Sortieralgorithmus.
Es muss zunächst eine Permutation der zu sortierenden Liste gebildet werden. Diese Permutation muss daraufhin überprüft werden, ob sie sortiert ist. Falls diese Permutation nicht sortiert ist, wird der Sortiervorgang so lange angewandt, bis sie sortiert ist. [PROGINLOG]
Komplexität
Es gibt maximal n! Möglichkeiten n Elemente anzuordnen. Im schlimmsten Fall muss n! -mal permutiert werden, um zur sortierten Liste zu kommen.
Eine (Folge-) Permutation kann in einem Schritt meist mit einer simplen Vertauschung zweier Elemente (swap) realisiert werden, also O(1). Der Test, ob eine Permutation eine sortierte Liste darstellt, benötigt n-1 Schritte, also O(n).

average case / worst case
Der SlowSort sortiert also im Schneckentempo mit der Laufzeitkomplexität O(n * n!) und ist deshalb für das Sortieren nicht brauchbar. Schon bei kleinen Listen (z. B.: n = 10) legt der SlowSort den Rechner lahm! :-(

Dieses Sortierverfahren kann so lange dauern, dass vielleicht das zufällige Anordnen der Elemente mit anschließender Prüfung auf Sortierung schneller sein könnte — ein RandomSort mit unbestimmter Laufzeitabschätzung, welcher im Hackerjargon als BogoSort bezeichnet wird.

best case
Unglaublicherweise gibt es einen Fall, der bzgl. der Laufzeitkomplexität sogar den QuickSort übertreffen kann. Denn bei einer bereits vorsortierten Liste benötigt SlowSort nur n-1 Schritte, also O(n).
Konkretes Zahlenbeispiel
Prüfe jede Permutation bzgl. der Kleiner-Ordnung! Dabei sei nun [3, 1, 4, 2] die zu sortierende Liste:
  • is_sorted([3, 1, 4, 2])? no!
  • is_sorted([1, 3, 4, 2])? no!
  • is_sorted([1, 4, 3, 2])? no!
  • is_sorted([1, 4, 2, 3])? no!
  • is_sorted([3, 4, 1, 2])? no!
  • is_sorted([4, 3, 1, 2])? no!
  • is_sorted([4, 1, 3, 2])? no!
  • is_sorted([4, 1, 2, 3])? no!
  • is_sorted([3, 4, 2, 1])? no!
  • is_sorted([4, 3, 2, 1])? no!
  • is_sorted([4, 2, 3, 1])? no!
  • is_sorted([4, 2, 1, 3])? no!
  • is_sorted([3, 1, 2, 4])? no!
  • is_sorted([1, 3, 2, 4])? no!
  • is_sorted([1, 2, 3, 4])? yes!!!
Das Sortieren ist zwar korrekt, kann jedoch langwierig werden, was man an diesem Beispiel leicht erkennen kann.
Implementierung Implementierung des SlowSort
Mit Prolog permutieren
Da es sehr viele Permutationen geben kann, — so viel Speicherplatz gibt es auf der ganzen Welt nicht — realisiert man in Prolog 1 den SlowSort mit der Tiefensuche. Eine Permutation wird auf Sortierung getestet. Bei Erfolg terminiert die Suche (cut bzw. !). Schlägt der Test is_sorted fehl, so wird Dank des internen Beweisverfahrens mittels Backtracking die nächst mögliche Permutation aufs Neue getestet.

Im Prinzip kann permute als zweistellige Relation betrachtet werden, die zu einer gegebenen Liste alle dazugehörigen Permutationen liefert und permute_ als dreistellige Hilfsrelation, die alle Listen mit gegebenen Wert X zurückgibt, wobei dieser Wert stets an einer anderen Stelle steht.
1) Es liegt nicht an der Programmiersprache "Prolog", dass der SlowSort so langsam ist, sondern an der zugrundeliegenden Idee von SlowSort!
Implementierung mit Prolog
% ?-slowsort([1, 2, 1, 2, 4, 3, 5, 3, 4, 5], SL).

slowsort(L, SL) :- permute(L, SL), is_sorted(SL), !.

is_sorted([]).
is_sorted([_]).
is_sorted([X, X|Rest]) :- is_sorted([X|Rest]).
is_sorted([X, Y|Rest]) :- X < Y, is_sorted([Y|Rest]).

permute([], []).
permute([X|Rest], PL) :- permute(Rest, L), permute_(X, L, PL).

permute_(X, L, [X|L]).
permute_(X, [Y|L], [Y|PL]) :- permute_(X, L, PL).
⇑ Implementierung mit Prolog ⇑
Startseite   Sitemap   Downloads   Hilfe   Impressum   POV-Ray-Zauberwürfel  
Fußnote
  1. Es liegt nicht an der Programmiersprache "Prolog", dass der SlowSort so langsam ist, sondern an der zugrundeliegenden Idee von SlowSort!
Quellenangabe
  • [PROGINLOG] Logik und Programmieren in Logik: Ramin Yasdi, 1995 Prentice Hall Verlag GmbH ISBN 3-93043-624-8 Ein Lehrbuch
Startseite < Informatik < Algorithmen < Sortieren < BucketSort RadixSort / QuickSort MergeSort HeapSort / BubbleSort SelectionSort InsertionSort / [ DRUCK , 2004 , 2005 , 2006 , 2007 , 2008 , 2009 ] SlowSort BogoSort > Komprimieren Suchen / Primzahltest > Datenstrukturen / Software-Engineering / Programmiersprachen / Künstliche Intelligenz > Schach Privates / Inhalt >