低速アルゴリズム
単純挿入ソート ( Insertionsort )
単純挿入ソートは、対象とするデータがリストのようなときにはとても有効である。しかし、単なる配列データの時には、基本的な考え方はバブルソートと同じである。また、例をあげて解説しよう。
49 66 11 37 84 6 22 73
単純挿入法では、あらかじめ並べ換えが済んでいるデータ列に新たにデータを挿入する事を基本としている。そこで、まず左から１番目までが並べ換えが済んでいるとして、２番目のデータをそこに挿入することを考える。この例では、４９が１つしかないデータ列に６６を挿入することを考える。この場合は、なんの変化もない。
49 66 11 37 84 6 22 73
次に、４９，６６のデータ列に１１を挿入することを考える。大きい方から小さい方（右から左へ）に向かって比較していき、ソート済みのデータ列のどこに挿入できるかを見ていく。この場合は、１１が一番小さいため一番左に挿入されたことになる。
11 49 66 37 84 6 22 73
次に、１１，４９，６６のデータ列に３７を挿入する。６６から左へ順に見ていく。
11 37 49 66 84 6 22 73
以下、同様な操作を行なう。
11 37 49 66 84 6 22 73
6 11 37 49 66 84 22 73
6 11 22 37 49 66 84 73
6 11 22 37 49 66 73 84
以下のような、プログラムが作成できる。
1: void Insertionsort(int data[], int n) {
2: int tmp, i, j;
3:
4: for( j=1; j < n; j++ ) {
5: i = j - 1;
6: tmp = data[j];
7: while( (i>=0) && (tmp < data[i]) ) {
8: data[i+1] = data[i];
9: i = i - 1;
10: }
11: data[i+1] = tmp;
12: }
13: }
単純挿入ソートもＯ（ｎ＾２）の計算量を持つことは、４のｆｏｒループ内に７のｗｈｉｌｅループが存在することから予想できる。単純選択ソートと同様な方法で容易に示せる。
以上、３種類の低速アルゴリズムを示した。これらのアルゴリズムは単純であるが、Ｏ（ｎ＾２）の計算量を持つことが理解できたであろう。
このｎ＾２のオーダーがどの程度のものなのかは、ｙ＝ｘ＾２のグラフを方眼紙に書いてみるとよい。ｘがある数値を越えると、ｙが急に大きくなり方眼紙をはみ出してしまう。このように、データの個数がある点を越えると、ソートにとてつもなく時間を要するようになるということである。
戻る
アプレットに戻る
a93sj030@j.dendai.ac.jp