内部整列(ソート)の逐次決定法(基本選択法)


 昇順の場合、1番目の要素と2番目の要素を比較して小さい要素を1番目にします。次に1番目と3番目を比較して比較して小さい要素を1番目にします。次に1番目と4番目を比較して比較して小さい要素を1番目にします。これを最後の要素まで繰り返し1番小さい要素を1番目に設定します。

 2番目の要素と3番目の要素を比較して小さい要素を2番目にします。次に2番目と4番目を比較して比較して小さい要素を2番目にします。次に2番目と5番目を比較して比較して小さい要素を2番目にします。これを最後の要素まで繰り返し1番小さい要素を2番目に設定します。

 以上の手順を繰り返し、並び変えるのが、逐次決定法のソート方法になります。

逐次決定法のフローチャート

 IT企業に入ってから気づいたのですが、昔ベーシックマガジンに載っていたBASICのプログラムを改造して、ゲームのハイスコアの機能を追加する機能を実装するするために思いついた方法が、実は逐次決定法と呼ばれるアルゴリズムであるでことが分かり、感動したことがあります。

下記の逐次決定法の定義は電子開発学園出版局「改訂アルゴリズムとデータ構造」より引用しました。

昇順の場合、全要素を比較して最小のキーを持つ要素を選び、それを1番目の要素に移し、次に2番目以降の要素の中から最小のキーを持つ要素を選び、それを2番目の要素に移す。これを繰り返して最終要素の1つ手前の要素まで行う方法である。


テクニカルエンジニアデータベースの過去問のホームページへ inserted by FC2 system