WikiDer > Bogosort

Bogosort (ebenfalls dumme Sorte oder langsam sortieren erwähnt) ist ein scherzhafter Vorschlag Sortieralgorithmus was extrem ineffizient ist, aber dennoch einen gewissen Wert als Benchmark für den theoretisch schlechtesten Sortieralgorithmus haben kann.

Der Algorithmus geht so:

1. ein zufälliges erzeugen Permutation der zu sortierenden Elemente Array (Mische sie nach dem Zufallsprinzip);
2. überprüfen Sie, ob sie in der richtigen Reihenfolge sind;
3. Wenn nicht, gehen Sie zurück zu Schritt 1.

Wie ein Pseudo-Zufallsgenerator verwendet wird, kann dieser Algorithmus nicht terminieren. Wenn sich alle Elemente voneinander unterscheiden, ist die erwartete KomplexitätsgradO(n × n!). Bogosort ist nicht stabil.