Der schlimmste Sortieralgorithmus

Die meisten Sortieralgorithmen beruhen ausschließlich oder vorwiegend auf dem Befehlspaar „Vergleichen und und optionales Tauschen (wenn die Reihenfolge der verglichenen Elemente der gewünschten Ordnung zuwiderläuft) jeweils zweier Elemente“. Doch es gibt auch Sortieralgorithmen, die diese Befehlsreihenfolge umkehren und mithin der Erreichung des Sortierzieles maximal entgegenwirken. Dabei werden erst zwei beliebige Elemente vertauscht und erst dann die gesamte Menge auf Ordnung bzw. Sortiertheit geprüft (oder, wenn man zuerst prüft, dann kann man so wenigstens schon sortierte Mengen von überflüssiger „Sortierung“ befreien). Die Wahl der zu tauschenden Elemente erfolgt entweder zufällig (Bozosort) oder durch systematische Permutationsenumeration (Bogosort). Diese Sortieralgorithmen, die auch schon erreichte Teilordnungen immer wieder sehr wahrscheinlich zerstören, sind die ineffizientesten überhaupt, aber auch sie können die Sortierung nach Zeitaltern, die jegliche astronomische / kosmologische Zeiträume schnell und weit überschreiten, nicht für alle Ewigkeit verhindern. Während beim Bogosort nach spätestens n! Vertauschungen und Prüfen der Menge auf Sortiertheit Schluß sein muß (n: Anzahl der Sortierelemente), weil alle Permutationen der Sortierelemente geprüft wurden, kann es beim Bozosort noch wesentlich länger dauern.

Kontaktformular