挿入法とは

たとえば、以下の名前の並びを考えてみよう。

佐藤、高橋、加藤、田中、石田

この5名の名前を「あいうえお順」に並べることを考えてみよう。あいうえお順は、辞書式順序(dictionary order)という。

まず、佐藤（さとう）、高橋（たかはし）、加藤（かとう）、田中（たなか）、石田（いしだ）とひらがなで考えるだろう。すると、以下のようになる。

さとう、たかはし、かとう、たなか、いしだ

まず、このなかで一番最初（になるべき）の名前を検索する。すると、「いしだ」であることがわかり、最初の名前「さとう」と交換する。

いしだ、たかはし、かとう、たなか、さとう

となる。次に、残りの、「たかはし、かとう、たなか、さとう」について、同様に、一番最初（になるべき）の名前を検索する。すると、「かとう」であることがわかり、二番目の名前「たかはし」と交換する。

いしだ、かとう、たかはし、たなか、さとう

となる。さらに、残りの「たかはし、たなか、さとう」について、同様の処理を行う。

いしだ、かとう、さとう、たなか、たかはし

となる。さらに、「たなか、たかはし」について、同様の処理を行う。

いしだ、かとう、さとう、たかはし、たなか

となる。以上の処理より、解は以下となる。

石田、加藤、佐藤、高橋、田中

ここで、以下の2つの処理が必要となることがわかる。以下では、簡単のために数字の並び替えを考えよう。

87、90、56、98、23

で考えてみよう。

23、90、56、98、87

23、56、90、98、87

23、56、87、98、90

23、56、87、90、98

となり、いわゆる「昇順」となった。この処理では、以下の2つの処理が重要であることがわかった。

1. 最小値の検索
2. 2つの値の交換

この2つの処理を使うとソートのアルゴリズムは以下のようになる。

まず、データを以下のように置く。

以下で、i は変数、N は定数とする。

1. N 個の値を入力する。
2. i を 1 とする。
3. i が N+1　なら 8 へ飛び越し
4. i から N 番目の中で最小値を見つける(最小値の検索)。
5. i 番目の値と最小値を交換する(2つの値の交換)。ただし、i番目が最小値の場合は交換しない。
6. i に 1 を加える。
7. 3に戻る。
8. 終了

では、次にこのアルゴリズムをプログラミングしよう。このアルゴリズムは最小法という。値は、ランダムに生成することにしよう。