終了この質問は
トピック外です。現在、回答を受け付けていません。
コメント
回答
bogobogosortではありません
bogobogosortの実装方法は、実際にはbogosortbecauよりも高速です。いくつかの理由があります：
-
k要素のボゴソートに成功したら、すぐにk+1要素がソートされます。つまり、前のシャッフルでm要素をすべて順番にシャッフルした場合、最初の2つの要素を並べ替えると、すぐにm。
たとえば、5枚のカードに到達してから失敗したとします。 5枚のカードをシャッフルしてから2からやり直します。これらの5枚のカードが並べ替えられている場合、最初の2枚のカードを並べるとすぐに6枚になります。
-
ポイント＃1のため、bogobogosortは、nではなくn-1カードを並べ替えるだけでよいため、実際にはbogosortよりも高速です。 。 n-1カードを並べ替えた後、nカードの順序を確認し、失敗する可能性があります。ただし、失敗すると、nカードが再シャッフルされ、n-1カードを並べ替えるたびに1/n最終的に成功する可能性。したがって、シャッフルされるカードの総数は(n-1) * (n-1)! * nのオーダーであり、iv id =をシャッフルするボゴソートと比較して、(n-1) * n!に簡略化されます。 “8998a03aef”>
カード。
各ステップで同じ原則が適用されると思うので、時間は(n-1) * n!よりもさらに短くなります。正確な計算はわかりませんが、プログラムを実行すると、bogobogosortは1枚少ないカードでbogosortとほぼ同じ時間に実行されるようです。つまりYour_bogobogosort（n）= bogosort（n-1）。
適切なボゴソート
ボゴソート関数を次のように書き直しました：
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; }
ここでの主な違いは、bをインクリメントする成功のたびに、上記のポイント＃1が発生しないようにデッキを再シャッフルすることです。この変更により、次のような出力が得られます。
% ./a.out 6 bogosort shuffled 1044 cards in 0.000013 seconds. bogobogosort shuffled 54464568 cards in 0.500339 seconds.
コメント