Bogosort: Unterschied zwischen den Versionen

Aus SibiWiki
Zur Navigation springen Zur Suche springen
Zeile 1: Zeile 1:
[[Kategorie:Informatik]]
[[Kategorie:Sortierverfahren]]
[[Kategorie:Sortierverfahren]]



Version vom 16. Februar 2012, 21:58 Uhr


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]);
}