記憶領域を活用、交換回数が減少「選択ソート改」公開
こんばんは。えいたです。
選択ソートの特徴：整列されていない部分から最小の要素を選択 → 先頭と交換
比較対象より小さい要素が見つかった場合、ロジックの組み方はどうしますか？
- 記憶領域無し：比較対象と交換
- 記憶領域あり：最小の要素を記録領域に保存 → 最後に比較対象と交換
似たり寄ったりですが、コードの行数は異なります。
temp = sort_array[i];
sort_array[i] = sort_array[j];
sort_array[j] = temp;
//記憶領域あり
min = j;
つまり、要素数が多ければ・・・記憶領域は必須です。
ロジックの改善
記憶領域を用いて、交換回数を減らします。
for( i = 0 ; i < 要素数 - 1 ; i++ ){
//最小値の要素(i)を記憶
for( j = i+1 ; j < 要素数 ; j++ ){
if( 最小値 > sort_array[j] ){
//最小値の要素(j)を記憶
}
}
//配列の要素を入れ替える
}
・上記のアルゴリズムを使用(要素数：４)
「３ ２ ４ １」[３] ← 開始
「３ ２ ４ １」[１] ← 最小値発見
「１ ２ ４ ３」[１] ← 交換
「１ ２ ４ ３」[２]
「１ ２ ４ ３」[２] ← 最小値発見(初期値と同様)・交換無し
「１ ２ ４ ３」[４]
「１ ２ ４ ３」[３] ← 最小値発見
「１ ２ ３ ４」[３] ← 交換
「１ ２ ３ ４」[ー] ← 終了
比較回数６回、交換回数２回になります。
「選択ソート改」で学ぶ
「選択ソート改」について
ルール
１０個の要素について、整列します。
- 小の指先：要素の比較場所
- 大の指先：要素の比較場所
- 比の指先：未整列の先頭場所
- 済の指先：整列の確定場所(赤背景は整列済み)
灰色背景：記憶領域
上記の場合は順序が逆により、記憶領域に保存します。
最小の要素について、先頭の要素を交換します。
全要素が整列するまで、繰り返します。
画面構成
初期化ボタンは、３種類あります。
- 昇順：要素を昇順にします。
- 降順：要素を降順にします。
- ランダム：要素をランダムにします。
実行ボタンは、２種類あります。
手動：ユーザが次ステップの実行権を持つ
自動：自動で次ステップに進む(スピードは、右側のつまみで調節可能)
操作方法
要素を初期化してから、実行ボタンを押して下さい。
全要素を整列：要素が昇順になりました。
交換回数について
要素数：１０の場合、比較回数は４５回です。
計算式：要素数 × （要素数 － １） ÷ ２
交換回数は要素の順序により、異なります。
※処理が速い「記録領域に保存」は省略
昇順
交換回数は０回、最も良いケースです。
降順
交換回数は５回、最も悪いケースになりません。
ランダム
交換回数は０～９回です。
最大：要素数 ー １
さいごに
塵も積もれば山となる、処理の流れは重要です。
交換：処理時間が長い → 回数を減らす
選択ソートは「記憶領域に保存」で解決しました。
※仕事において、ボトルネックからのコード修正は頻繁にあります。
他のゲームも遊んで下さいね。