【整列アルゴリズム】シミュレーション「挿入ソート」公開
2018/04/26
こんにちは。えいたです。
整列アルゴリズム第３弾、挿入ソートを解説します。
比較回数：要素数 × （要素数 － １） ÷ ２
比較回数を減らす方法は、整列済みの要素と比較します。
カードゲームを想像して下さい。
手札を１枚取る → 整列済みのカードを辿る → 指定の場所に配置
全てのカードを確認せず、配置しています。
挿入ソートとは
IT技術者ならば、プログラムは書けるはず。
ソートのアルゴリズムの一つ。整列してある配列に追加要素を適切な場所に挿入すること。最悪計算時間が遅い。
まず0番目と1番目の要素を比較し、順番が逆であれば入れ換える。次に、2番目の要素が1番目までの要素より小さい場合、正しい順に並ぶように「挿入」する。3番目以降の要素について、整列済みデータとの比較と適切な位置への挿入を繰り返す。
for( i = 1 ; i < 要素数 ; i++ ){
j = i;
while( j > 0 && sort_array[j-1] > sort_array[j]){
//配列の要素を入れ替える
j--;
}
}
・上記のアルゴリズムを使用(要素数：４)
「３ ２ ４ １」 ← 開始
「２ ３ ４ １」
「２ ３ ４ １」 ← 交換無し
「２ ３ １ ４」
「２ １ ３ ４」
「１ ２ ３ ４」
「１ ２ ３ ４」 ← 終了
比較回数５回、交換回数４回になります。
「挿入ソート」で学ぶ
「挿入ソート」について
ルール
１０個の要素について、整列します。
- 小の指先：要素の比較場所
- 大の指先：要素の比較場所
- 済の指先：整列の確定場所(赤背景は整列済み)
上記の場合は順序が逆により、入れ替えます。
全要素が整列するまで、繰り返します。
画面構成
初期化ボタンは、３種類あります。
- 昇順：要素を昇順にします。
- 降順：要素を降順にします。
- ランダム：要素をランダムにします。
実行ボタンは、２種類あります。
手動：ユーザが次ステップの実行権を持つ
自動：自動で次ステップに進む(スピードは、右側のつまみで調節可能)
操作方法
要素を初期化してから、実行ボタンを押して下さい。
全要素を整列：要素が昇順になりました。
交換回数について
比較回数の計算式は下記です。
最高の計算式：要素数 － １
交換回数は比較回数以下になります。
昇順
比較回数９回・交換回数は０回、最も良いケースです。
降順
交換回数は４５回(比較回数と同じ)、最も悪いケースです。
ランダム
比較回数は９～４５回・交換回数は０～４５回です。
交換回数：比較回数 － (０ ～ 要素数 － １)
比較回数と交換回数の関係は、規則性があります。
さいごに
全要素を比較する必要はありません。
整列済みの要素を生かすソートは、挿入ソートの特徴です。
挿入ソートを可視化、教材制作完了！
他のゲームも遊んで下さいね。