 | BogoSortDer BogoSort gehört zu den langsamsten Sortieralgorithmen.
Definition
Der BogoSort, auch RandomSort, StupidSort oder MonkeySort genannt, gehört neben dem SlowSort zu den langsamsten Sortieralgorithmen. BogoSort ordnet die zu sortierenden Elemente solange zufällig an, bis sie sortiert vorliegen.
Der BogoSort wird in der Praxis nie eingesetzt; er dient lediglich als akademisches Beispiel für schlechtes Laufzeitverhalten.
|
Komplexität
Das äußerst schlechte Laufzeitverhalten des BogoSort können Sie sich mit folgender Frage schnell plausibel machen: Wie oft muss ich meine Spielkarten mischen, bis sie sortiert sind? - best case
Im besten Fall reicht bei einer Liste mit n Elementen ein einziger Mischvorgang aus, lediglich das Überprüfen auf Sortiertheit benötigt bei einer sortierten Liste n−1 Schritte, O(n). - average case
Im Durchschnittsfall muss man die Hälfte aller möglichen Permutation (n!) durchprobieren, sodass man mit der Sortierprüfung die Laufzeitkomplexität O(n! * n) hat. Bei 32 Spielkarten müsste man mit etwa 2 * 1036 Aktionen rechnen. - worst case
Für den schlechtesten Fall kann man hingegen keine Laufzeitabschätzung machen. Schlimmstenfalls muss man ewig warten. :−(
|
Eigenschaft
Dieses Sortierverfahren ist nicht−stabil.
Durch das zufällige Anordnen (Mischen) der Elemente, geht die Stabilität verloren.
|
Pseudocode für BogoSort
Sortiere Liste A mit BogoSort
{
Solange die Liste A nicht sortiert ist,
{
mische Liste A.
}
} | |
Konkretes Zahlenbeispiel
Die Integerliste [3, 1, 2, 4] soll nun mit BogoSort aufsteigend sortiert werden. is_sorted([3, 1, 2, 4])? no.
shuffle([3, 1, 2, 4]) −> [1, 2, 4, 3] is_sorted([1, 2, 4, 3])? no.
shuffle([1, 2, 4, 3]) −> [3, 2, 4, 1] is_sorted([3, 2, 4, 1])? no.
shuffle([3, 2, 4, 1]) −> [3, 2, 4, 1] is_sorted([3, 2, 4, 1])? no.
shuffle([3, 2, 4, 1]) −> [4, 1, 2, 3] is_sorted([4, 1, 2, 3])? no.
shuffle([4, 1, 2, 3]) −> [3, 1, 2, 4] is_sorted([3, 1, 2, 4])? no.
shuffle([3, 1, 2, 4]) −> [1, 2, 4, 3] is_sorted([1, 2, 4, 3])? no.
shuffle([1, 2, 4, 3]) −> [3, 2, 4, 1] is_sorted([3, 2, 4, 1])? no.
shuffle([3, 2, 4, 1]) −> [3, 2, 4, 1] is_sorted([3, 2, 4, 1])? no.
shuffle([3, 2, 4, 1]) −> [1, 2, 3, 4] is_sorted([1, 2, 3, 4])? yes!
Mit ein bisschen Glück erhält man schon nach einigen Iterationen ein korrektes Ergebnis. :−)
|
Folgendes Implementierungsbeispiel in Java 1.6 zeigt, eine einfache Implacement−Sortierung mit der Strategie des BogoSort.
|
Implementierung mit Java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class BogoSort {
// Sortiert eine Integerliste mit der Strategie des BogoSort.
public static void sort(List<Integer> values) {
while (!isSorted(values)) {
shuffle(values);
}
}
// Prüft, ob die Integerliste sortiert ist.
private static boolean isSorted(List<Integer> values) {
for (int i = 1; i < values.size(); i++) {
if (values.get(i - 1) > values.get(i)) {
return false;
}
}
return true;
}
// Mischt die Integerliste.
private static void shuffle(List<Integer> values) {
Collections.shuffle(values);
}
// Hauptprogramm zum Test.
public static void main(String[] arguments) {
List<Integer> values = new ArrayList<Integer>();
Collections.addAll(values, 3, 1, 2, 4, 2);
System.out.println("Unsortierte Liste: " + values);
BogoSort.sort(values); // Die Werte werden hier sortiert!
System.out.println("Sortierte Liste: " + values);
}
} | |
Beachten Sie, dass auch gleichwertige Integerwerte vorkommen können. Im Folgenden sehen Sie den Konsolenoutput des Implementierungsbeispiels.
|
Ausgabe nach Ausführung
Unsortierte Liste: [3, 1, 2, 4, 2]
Sortierte Liste: [1, 2, 2, 3, 4] | |
| |
