連想配列を活用、交換回数が減少「挿入ソート改」公開
こんばんは。えいたです。
挿入ソートの特徴：整列済みの要素と比較 → 適切な要素と交換
適切な要素が前の方であれば、交換回数は増加します。
２を挿入：「１ ３ ４」 → 「１ ３ ２ ４」 → 「１ ２ ３ ４」
改善案：連想配列を用いた場合、交換回数は常に１回
２を挿入：「１→３→４」 → 「１→２→３→４」
連想配列は「要素は数字、キーは矢印」の１セットです。
要素の交換ではなく、キーを変更して挿入します。
ロジックの改善
連想配列を用いて、交換部分をfor文の外側にしました。
for( i = 1 ; i < 要素数 ; i++ ){
j = i;
while( j > 0 && sort_array[j-1] > sort_array[j]){
j--;
}
//連想配列のキーを入れ替える
}
・上記のアルゴリズムを使用(要素数：４)
「３→２→４→１」 ← 開始
「３→２→４→１」 ← 比較
「２→３→４→１」 ← 交換
「２→３→４→１」 ← 比較・交換無し
「２→３→４→１」 ← 比較
「２→３→４→１」 ← 比較
「２→３→４→１」 ← 比較
「１→２→３→４」 ← 交換
「１→２→３→４」 ← 終了
比較回数５回、交換回数２回になります。
「挿入ソート改」で学ぶ
「挿入ソート改」について
ルール
１０個の要素について、整列します。
- 小の指先：要素の比較場所
- 大の指先：要素の比較場所
- 済の指先：整列の確定場所(赤背景は整列済み)
上記の場合は交換箇所が決定、小の右側に大を移動します。
全要素が整列するまで、繰り返します。
画面構成
初期化ボタンは、３種類あります。
- 昇順：要素を昇順にします。
- 降順：要素を降順にします。
- ランダム：要素をランダムにします。
実行ボタンは、２種類あります。
手動：ユーザが次ステップの実行権を持つ
自動：自動で次ステップに進む(スピードは、右側のつまみで調節可能)
操作方法
要素を初期化してから、実行ボタンを押して下さい。
全要素を整列：要素が昇順になりました。
交換回数について
比較回数の計算式は下記です。
最高の計算式：要素数 － １
交換回数は要素数未満になります。
昇順
比較回数９回・交換回数は０回、最も良いケースです。
降順
比較回数９回・交換回数は４５回、最も悪いケースです。
ランダム
比較回数は９～４５回・交換回数は０～９回です。
交換回数：０ ～ 要素数 － １
比較回数は関係がありません。
さいごに
全要素を比較する必要はありません。
そして、交換回数も要素数以下です。
つまり「単純な整列アルゴリズム」では最も性能が良いソート！
他のゲームも遊んで下さいね。