Bogosort: Unterschied zwischen den Versionen

Aus SibiWiki
Zur Navigation springen Zur Suche springen
(Die Seite wurde neu angelegt: „Kategorie:Informatik Kategorie:Sortierverfahren <math> \Theta(n \cdot n!) </math>“)
 
 
(5 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt)
Zeile 1: Zeile 1:
[[Kategorie:Sortierverfahren]]
[[Kategorie:Informatik]]
[[Kategorie:Informatik]]
[[Kategorie:Sortierverfahren]]


<math> \Theta(n \cdot n!) </math>
Bogosort(auch Monkeysort oder Stupidsort genannt) ist kein stabiler [[Sortierverfahren|Sortieralgorithmus]].<br /> 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 ===
<code>
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;
      }
    }
}
</code>
=== Sortieren von Strings ===
<code>
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;
      }
    }
}
</code>
=== 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
<code>
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]);
}
</code>

Aktuelle Version vom 11. April 2013, 23:00 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]);
}