Bogosort

Aus SibiWiki
Version vom 11. April 2013, 23:00 Uhr von FTchalabi (Diskussion | Beiträge)
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)
Zur Navigation springen Zur Suche springen


Bogosort(auch Monkeysort oder Stupidsort genannt) ist kein stabiler Sortieralgorithmus.
Es mischt die Elemente solange zufällig bis sie alle richtig sortiert sind, somit hat er eine sehr lange Laufzeit.

Laufzeit

Das will man nicht wirklich wissen... Bogosort funktioniert ja so, als würde man ein Kartenspiel mischen und dann schauen, ob es sortiert ist. Wenn nicht, mischt man einfach nochmal - und das so lange, bis es sortiert ist! Das kann natürlich ziemlich lange dauern...

Einsatz von Bogosort in Java

Sortieren von Zahlen

public int[] BogoSort(int[] Zahl) {
   Random random = new Random();
   while (true) {
      boolean sortiert = true;
      for (int i = 0; i < Zahl.length - 1; i++)
      if (Zahl[i] > Zahl[i + 1]) {
          sortiert = false;
          break;
      }
      if (sortiert){
      return Zahl;
      }
      for (int i = Zahl.length - 1; i > 0; i--) {
         int randomZahl = random.nextInt(i);
         int hilfsZahl = Zahl[i];
         Zahl[i] = Zahl[randomZahl];
         Zahl[randomZahl] = hilfsZahl;
      }
   }
}

Sortieren von Strings

public String[] BogoSort(String[] String) {
   Random random = new Random();
   while (true) {
      boolean sortiert = true;
      for (int i = 0; i < String.length - 1; i++)
      if (String[i].compareTo(String[i + 1])>0) {
         sortiert = false;
         break;
      }
      if (sortiert){
      return String;
      }
      for (int i = String.length - 1; i > 0; i--) {
         int randomZahl = random.nextInt(i);
         String hilfsString = String[i];
         String[i] = String[randomZahl];
         String[randomZahl] = hilfsString;
      }
   }
}

Sortieren von Listen

Für Listen kann man den gleichen Code verwenden wie bei "Sortieren von Strings" man soll aber den Aufruf in der Main-Methode modifizieren

String[] String = new String[lt.anzahl(fussballerListe)];
fussballerListe.toFirst();
for (int i = 0; i < String.length; i++) {
   String[i]=fussballerListe.getObject().toString();
   fussballerListe.next();
}
String[] Sortieren = lt.BogoSort(String);
for (int i = 0; i < Sortieren.length; i++) {
   System.out.println(Sortieren[i]);
}