Bogosort
unsinniges Sortierverfahren Aus Wikipedia, der freien Enzyklopädie
unsinniges Sortierverfahren Aus Wikipedia, der freien Enzyklopädie
Bogosort, Dumbsort oder Stupidsort bezeichnet ein nicht-stabiles Sortierverfahren, bei dem die Elemente so lange zufällig gemischt werden, bis sie sortiert sind. Wegen der langen Laufzeit ist Bogosort der Prototyp eines schlechten Algorithmus. Bogosort wird insbesondere in der Informatik-Ausbildung in den Bereichen Datenstrukturen und Algorithmen verwendet, um an einem Extrembeispiel die Eigenschaften von Sortierverfahren im Allgemeinen zu verdeutlichen.[1][2]
Bogosort ist ein (randomisierter) Las-Vegas-Algorithmus, daher ist dessen Laufzeit eine Zufallsvariable. Die erwartete Laufzeit ist im besten Fall (angegeben in der Landau-Notation) sofern die angegebene Liste bereits sortiert ist und im schlechtesten Fall .[3] Die Fakultät ist die Anzahl der möglichen Anordnungen (Permutationen) verschiedener Elemente. Die Operation, die am häufigsten ausgeführt wird und das Laufzeitverhalten bestimmt, ist die Anzahl der Vertauschungen. Erstaunlicherweise ist die erwartete Anzahl der Vergleiche, die für große Listen gegen strebt, wesentlich geringer.[3] Hierbei bezeichnet die Eulersche Zahl.
In der Realität kann die Laufzeit beliebig lang sein, allerdings sind übermäßig lange Laufzeiten gemäß der Markow-Ungleichung auch entsprechend unwahrscheinlich. Der Algorithmus kommt unter der Annahme echter Zufallszahlengeneratoren und einer endlichen Anzahl zu sortierender Elemente fast sicher, d. h. mit Wahrscheinlichkeit 1, nach endlich vielen Schritten zu einem Ergebnis. Das bedeutet, dass es dennoch möglich ist, dass der Algorithmus niemals terminiert. Kommt ein Pseudozufallszahlengenerator zum Einsatz, muss dessen Periode hinreichend lang sein, sodass jede mögliche Permutation mindestens einmal generiert wird, bevor sich die Folge wiederholt.
while not sorted(deck):
shuffle(deck)
from random import shuffle
def bogosort(data: list) -> list:
while not all(a <= b for a, b in zip(data, data[1:])):
shuffle(data)
return data
class Main{
public static int[] sort(int[] toSort) {
Random r = new Random();
while (!isSorted(toSort)) { // Prüfen, ob sortiert
int a = r.nextInt(toSort.length);
int b = r.nextInt(toSort.length);
int temp = toSort[a];
toSort[a] = toSort[b];
toSort[b] = temp;
}
return toSort;
}
static boolean isSorted(int[] arr) {
for(int i = 0; i < arr.length - 1; i++) {
if (arr[i] > arr[i + 1]) return false;
}
return true;
}
}
function sort(arr) {
while(!isSorted()) {
var a = Math.floor(Math.random() * arr.length);
var b = Math.floor(Math.random() * arr.length);
var tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
function isSorted() {
for(var i = 0; i < arr.length - 1; i++) {
if (arr[i] > arr[i + 1]) return false;
}
return true;
}
}
inline void swap(register int *a, register int *b) {
register int temp = *a;
*a = *b;
*b = temp;
}
int isSorted(int arr[], size_t n) {
for (size_t i = 0; i < n - 1; ++i)
if (arr[i] > arr[i + 1])
return 0;
return 1;
}
void shuffle(int arr[], size_t n) {
for (size_t i = n - 1; i > 0; --i) {
int j = rand() % (i + 1);
swap(&arr[i], &arr[j]);
}
}
void bogoSort(int arr[], size_t n) {
while (!isSorted(arr, n))
shuffle(arr, n);
}
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.