本記事ではボゴソートソートの可視化についてのプログラムを紹介しています。
JavaScriptを使っています。
ボゴソートとはソートアルゴリズムの一つで、ひたすらランダムにシャッフルをし続け、運よく順番に並ぶまでそれを繰り返すアルゴリズムです。
数打ちゃ当たるソート、ランダムソートとも呼ばれています。
YouTubeに動画もアップしてあるのでそちらもご覧ください↓
ボゴソートの可視化についてのプログラム
DEMO
まずこちらが完成品。
まず、３～10の間の数を入力し「Enter」ボタンを押してソートをする棒の数を決めます。
「shffle」ボタンを押すことでシャッフルが始まります。
下の Speed バーでソートをする速さを設定することができます。
Start ボタンを押すとソートが始まり、シャッフルしたものが運よく昇順に並んでいたら、経過時間が表示されます。
９個の棒をソートする場合でも、８万回ぐらいシャッフルしないと綺麗に昇順にはなりません。
なので今回の例ではエレメント数は３～１０に限定しています。
HTMLファイルの作成
まず始めに、下記のような html ファイルを用意します。
CSSファイルは適当にこんな感じ。
JavaScript ファイルの作成
JavaScript ファイルは下記のように書いています。
まず、棒の数とシャッフルするSpeedを決める処理について書いています。
次にEnter ボタンの処理。
Enter ボタンが押されると、numBar という変数の値を更新し、reset(), shuffle(), draw() という関数が呼び出されます。
reset() 関数では、パラメータの値を０にしたりなどリセットをしています。
shuffle() 関数で棒の高さをランダムな値にし、draw() で描画をしています。
isSorted() 関数では配列を受け取り、その配列が昇順になっていたら true を返却しています。
btn_shuffle.addEventListener を使い、シャッフルボタンが押されたときに 発生するイベントを決めています。
スタートボタンが押されたら、まず、シャッフル・スタートボタンを disabled を true にすることで、もう一度押せないように設定をしています。
そして、ソートが始まった時間を記録し、ゲームループを実行します。
配列がたまたま昇順になるまでそのゲームループが繰り返し実行されます。
もし、配列がたまたま昇順になっていたら、 return をし終了をしています。
以上、ボゴソートを可視化するソースコードについての記事でした。
- GitHubのコード
コメント