Der schlimmste Sortieralgorithmus

Nicht nur das Entwickeln möglichst leistungsfähiger, vor allem schneller Sortieralgorithmen ist anspruchsvoll. Es hat nämlich durchaus auch einen herausfordernden intellektuellen Anspruch, einen Sortieralgorithmus möglichst zu verlangsamen, ihn so ineffizient wie möglich zu gestalten, ohne das Sortierziel aus den Augen zu verlieren. Sinnlos wäre hingegen, den Sortieralgorithmus ständig irgendetwas für den Sortierfortschritt und das Sortierergebnis unnötiges zwischenzeitlich rechnen zu lassen, die schon aufgebaute Teilordnung bewußt wieder zu zerstören, künstliche Pausen einzulegen oder einfach nur zu warten, ob etwas von allein passiert (was natürlich nimmer der Fall ist). Nein, es muß tatsächlich eine Änderung des Ordnungsniveaus erfolgen, und der Algorithmus muß zumindest das Potential, die Chance haben, irgendwann mit einer sortierten Menge zu enden.

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 scheinbar maximal entgegenwirken. In Wirklichkeit wird der bisherige Sortierfortschritt nur nicht fixiert, nicht darauf aufgebaut. 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). Beide Methoden lassen sich noch dahingehend steigern, daß nicht jeweils zwei Elemente vertauscht werden, sondern daß die jeweils neue Permutation durch jeweils mehr Elementebewegungen erzeugt wird. Diese Sortieralgorithmen, die auch schon erreichte Teilordnungen immer wieder sehr wahrscheinlich zerstören, sind vermutlich die ineffizientesten überhaupt (bis jemand noch langsamere findet), 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.