【整列アルゴリズム】シミュレーション「選択ソート」公開
2018/06/22
こんばんは。えいたです。
整列アルゴリズム第２弾、選択ソートを解説します。
バブルソートの弱点は、要素の交換回数が多い！
「隣り合う要素の比較 → 交換」は単純作業、コンピューターの得意分野です。
しかし、要素数が多ければ・・・処理が不安定になります。
よって、記憶領域の実装は見送りました。
選択ソートとは
IT技術者ならば、プログラムは書けるはず。
ソートのアルゴリズムの一つ。配列された要素から、最大値やまたは最小値を探索し配列最後の要素と入れ替えをおこなうこと。最悪計算時間が遅い。
データ列中で一番小さい値を探し、1番目の要素と交換する。次に、2番目以降のデータ列から一番小さい値を探し、2番目の要素と交換する(データ列の最後まで繰り返す)。
for( i = 0 ; i < 要素数 - 1 ; i++ ){
for( j = i+1 ; j < 要素数 ; j++ ){
if( sort_array[i] > sort_array[j] ){
//配列の要素を入れ替える
}
}
}
・上記のアルゴリズムを使用(要素数：４)
「３ ２ ４ １」 ← 開始
「２ ３ ４ １」
「２ ３ ４ １」 ← 交換無し
「１ ３ ４ ２」
「１ ３ ４ ２」 ← 交換無し
「１ ２ ４ ３」
「１ ２ ３ ４」
「１ ２ ３ ４」 ← 終了
比較回数６回、交換回数４回になります。
「選択ソート」で学ぶ
「選択ソート」について
ルール
１０個の要素について、整列します。
- 小の指先：要素の比較場所
- 大の指先：要素の比較場所
- 済の指先：整列の確定場所(赤背景は整列済み)
上記の場合は順序が逆により、入れ替えます。
全要素が整列するまで、繰り返します。
画面構成
初期化ボタンは、３種類あります。
- 昇順：要素を昇順にします。
- 降順：要素を降順にします。
- ランダム：要素をランダムにします。
実行ボタンは、２種類あります。
手動：ユーザが次ステップの実行権を持つ
自動：自動で次ステップに進む(スピードは、右側のつまみで調節可能)
操作方法
要素を初期化してから、実行ボタンを押して下さい。
全要素を整列：要素が昇順になりました。
交換回数について
要素数：１０の場合、比較回数は４５回です。
計算式：要素数 × （要素数 － １） ÷ ２
交換回数は要素の順序により、異なります。
昇順
交換回数は０回、最も良いケースです。
降順
交換回数は４５回、最も悪いケースです。
ランダム
当たり前ですが、交換回数は０～４５回です。
さいごに
記憶領域は未使用、交換回数は「バブルソート」と同様です。
選択ソートを可視化、教材制作完了！
他のゲームも遊んで下さいね。