ソート 選択法、挿入法
n個のデータの系列(a1, a2,…, an)が入力として与えられたとき、これらをある順序にしたがって並べ替える処理をソートと呼ぶ。ソートを行うアルゴリズムは、これまでに多く研究され、いくつかの効率の良いアルゴリズムが知られている。
比較によりソートを行う最も簡単なアルゴリズムは次のようなものである。
入力のn個の数値a1, a2,…, anの中から最小のものを見つけそれを取り出し、次にその残りの数値の中からまた最小のものを見つけて取り出す。これを繰り返し、各数値を取り出した順に並べるというものである。このようなアルゴリズムは選択法と呼ばれ、入力サイズnが小さいときによく用いられる。
| 入力された数列が 27 31 15 7 11 9 の場合 27 31 15 7 11 9 7 27 31 15 11 9 7 9 27 31 15 11 7 9 11 27 31 15 7 9 11 15 27 31 7 9 11 15 27 31 |
このアルゴリズムを実現するには、入力されたn個の数列を格納する配列をまず用意し、その中（配列0からn-1まで）から最小となるものを選び、ソートされた結果を格納する配列の0番目に入れる。続いて、配列1からnまでの中から最小のものを選び、結果を格納する配列の1番目に入れる。この操作をn回ループを行えばよい。
具体的なプログラムの流れ図は以下のようになる。(画像をクリックすると拡大）
挿入法は各時点で注目しているaiを、そのときまでにソートされている系列(a1, a2,…, ai-1)の間の適切な場所に挿入するというものである。
注目点を右に順に動かしていくことで、ソートが行われる。
（*注目点） |
このアルゴリズムを実現するには、入力されたn個の数列を格納する配列をまず用意し、注目点をiに設定する。その注目点がソートされた結果を格納する配列のどこに挿入するのが適切かを調べ、その場所に挿入する。挿入は注目点よりも大きな値を持った配列要素を右にシフトすることで実現する。
この操作をiを0からnまで繰り返すことでソートが行われる。
具体的なプログラムの流れ図は以下のようになる。(画像をクリックすると拡大）
