Bogosort vs bogobogosort [geschlossen]

Nicht bogobogosort

Die Art und Weise, wie Sie Ihr bogobogosort implementiert haben, ist tatsächlich schneller als bogosort becau Dies hat einige Gründe:

1. Nachdem Sie k Elemente erfolgreich bogosortiert haben, überprüfen Sie sofort, ob k+1 Elemente werden sortiert. Dies bedeutet, dass Sie, wenn Sie bei einem vorherigen Shuffle m -Elemente alle der Reihe nach gemischt haben, nach dem Sortieren der ersten beiden Elemente sofort m.

   Angenommen, Sie erreichen 5 Karten und schlagen dann fehl. Sie mischen 5 Karten und beginnen dann bei 2. Wenn diese 5 Karten in sortierter Reihenfolge vorliegen, erreichen Sie sofort 6, sobald Sie die ersten 2 Karten in die richtige Reihenfolge bringen.

2. Aufgrund von Punkt 1 ist Ihr Bogobogosort tatsächlich schneller als der Bogosort, da nur n-1 Karten anstelle von n sortiert werden müssen . Nachdem n-1 -Karten sortiert wurden, überprüft es die Reihenfolge der n -Karten und schlägt möglicherweise fehl. Wenn dies fehlschlägt, werden n -Karten neu gemischt, sodass jedes Mal, wenn n-1 -Karten sortiert wird, eine 1/n Chance auf Erfolg. Die Gesamtzahl der gemischten Karten liegt also in der Größenordnung von (n-1) * (n-1)! * n, was sich zu (n-1) * n! vereinfacht, verglichen mit dem Bogosort, der n * n! -Karten.

   Ich glaube, dass bei jedem Schritt das gleiche Prinzip gilt, daher ist die Zeit sogar kürzer als (n-1) * n!. Ich bin mir der genauen Mathematik nicht sicher, aber nach dem Ausführen Ihres Programms scheint der Bogobogosort ungefähr zur gleichen Zeit wie der Bogosog mit einer Karte weniger zu laufen. Dh Your_bogobogosort (n) = Bogosort (n-1).

Ein richtiger Bogobogosort

Ich habe Ihre Bogobogosort-Funktion so umgeschrieben:

unsigned long bogobogosort(int *data, size_t n) { unsigned long c = 0; size_t b = 2; while (1) { if (sorted(data, b)) { if (b == n) break; b++; } else { b = 2; } c += b; shuffle(data, b); } return c; } 

Der Hauptunterschied besteht darin, dass nach jedem Erfolg, bei dem b erhöht wird, das Deck neu gemischt wird, um zu verhindern, dass Punkt 1 oben auftritt. Mit dieser Änderung erhalte ich die folgende Ausgabe:

% ./a.out 6 bogosort shuffled 1044 cards in 0.000013 seconds. bogobogosort shuffled 54464568 cards in 0.500339 seconds. 

Kommentare

• Laut der Beschreibung bei Wikipedia prüft der erste Teil von bogosort auf Bestellung Daten. Wenn die ersten N Elemente in Ordnung sind, führt ein Bogosort dieser N Elemente kein einziges Shuffle durch. Wenn ich also 0 1 2 3 4 6 5 und Bogobogosort habe, gehe ich von Bogosort von 2 auf 5 Elemente ohne Mischen, dann 6 Elemente mischen (und zurück zu bo gobogosorting 2).
• @pmg Wenn dies die richtige Definition von bogobogosort ist, stellt sich heraus, dass es schneller als bogosort ist (wie das Programm OP ' beweist). . Ich ' bin nicht mit den Ursprüngen von bogobogosort vertraut, aber damit es " bis zum Hitzetod des Universums " Wie behauptet, sollte es eher so aussehen, wie ich es geschrieben habe.