【整列アルゴリズム】シミュレーション「バブルソート」公開
2018/03/10
こんばんは。えいたです。
情報系の大学出身者なら、整列アルゴリズムは学習済みと思います。
整列アルゴリズム：要素の集合について、規則通りに並べる処理
人間はコンピュータと異なり、まとめて比較することは得意です。しかし、結果はコンピュータの方が圧倒的に速い！
コンピュータは「２つの要素を比較 → 規則通りに整列」を繰り返す。
圧倒的な速さで繰り返すから、人間は太刀打ちできません。
最も簡単な整列アルゴリズム、バブルソートで解説します。
バブルソートとは
IT技術者ならば、プログラムは書けるはず。
ソートのアルゴリズムの一つ。隣り合う要素の大小を比較しながら整列させること。最悪計算時間が遅い。
全ての要素に関して、隣接する要素と比較し順序が逆であれば入れ替える。これを要素数-1回繰り返すことでソートを行なう。
for( i = 要素数 - 1 ; i > 0 ; i-- ){
for( j = 0 ; j < i ; j++ ){
if( sort_array[j] > sort_array[j + 1] ){
//配列の要素を入れ替える
}
}
}
・上記のアルゴリズムを使用(要素数：４)
「３ ２ ４ １」 ← 開始
「２ ３ ４ １」
「２ ３ ４ １」 ← 交換無し
「２ ３ １ ４」
「２ ３ １ ４」 ← 交換無し
「２ １ ３ ４」
「１ ２ ３ ４」
「１ ２ ３ ４」 ← 終了
比較回数６回、交換回数４回になります。
「バブルソート」で学ぶ
「バブルソート」について
ルール
１０個の要素について、整列します。
- 小の指先：要素の比較場所
- 大の指先：要素の比較場所
- 済の指先：整列の確定場所(赤背景は整列済み)
上記の場合は順序が逆により、入れ替えます。
全要素が整列するまで、繰り返します。
画面構成
初期化ボタンは、３種類あります。
- 昇順：要素を昇順にします。
- 降順：要素を降順にします。
- ランダム：要素をランダムにします。
実行ボタンは、２種類あります。
手動：ユーザが次ステップの実行権を持つ
自動：自動で次ステップに進む(スピードは、右側のつまみで調節可能)
操作方法
要素を初期化してから、実行ボタンを押して下さい。
全要素を整列：要素が昇順になりました。
交換回数について
要素数：１０の場合、比較回数は４５回です。
計算式：要素数 × （要素数 － １） ÷ ２
交換回数は要素の順序により、異なります。
昇順
交換回数は０回、最も良いケースです。
降順
交換回数は４５回(比較回数と同じ)、最も悪いケースです。
ランダム
当たり前ですが、交換回数は０～４５回です。
さいごに
シミュレーションの使用目的は、机上の学習成果を試すため。
交換回数０回、昇順のケースは必要ですか？
０回の理由を確認して欲しいから、実装しました。
バブルソートを可視化、教材制作完了！
他のゲームも遊んで下さいね。