アルゴリズムA 第15回


挿入ソート

挿入ソートのアルゴリズム p.300
n個の値  a[0], a[1], ..., a[n-1] を並べ替えるには、配列の一部分(a[0]〜a[i-1])を
整列済みの状態にしておき、a[i]をa[0]〜a[i-1]の適切な位置に挿入する。
このiを0からn-1まで上記の操作を繰り返せば終了。
InsertSort.java
授業で配布するプリントを参照して下さい。
InsertSort.javaの実行例
$ javac InsertSort.java
$ java InsertSort
データの個数を入力して下さい  8
20 6 44 74 3 45 13 87
3 6 13 20 44 45 74 87 
$ java InsertSort -d
データの個数を入力して下さい  8
20 6 44 74 3 45 13 87
sorting: 6 20 44 74 3 45 13 87 
sorting: 6 20 44 74 3 45 13 87 
sorting: 6 20 44 74 3 45 13 87 
sorting: 3 6 20 44 74 45 13 87 
sorting: 3 6 20 44 45 74 13 87 
sorting: 3 6 13 20 44 45 74 87 
sorting: 3 6 13 20 44 45 74 87 
3 6 13 20 44 45 74 87 
$ java InsertSort -d2
データの個数を入力して下さい  8
20 6 44 74 3 45 13 87
i=1,j=0: 6 20 44 74 3 45 13 87 
sorting: 6 20 44 74 3 45 13 87 
sorting: 6 20 44 74 3 45 13 87 
sorting: 6 20 44 74 3 45 13 87 
i=4,j=3: 6 20 44 3 74 45 13 87 
i=4,j=2: 6 20 3 44 74 45 13 87 
i=4,j=1: 6 3 20 44 74 45 13 87 
i=4,j=0: 3 6 20 44 74 45 13 87 
sorting: 3 6 20 44 74 45 13 87 
i=5,j=4: 3 6 20 44 45 74 13 87 
sorting: 3 6 20 44 45 74 13 87 
i=6,j=5: 3 6 20 44 45 13 74 87 
i=6,j=4: 3 6 20 44 13 45 74 87 
i=6,j=3: 3 6 20 13 44 45 74 87 
i=6,j=2: 3 6 13 20 44 45 74 87 
sorting: 3 6 13 20 44 45 74 87 
sorting: 3 6 13 20 44 45 74 87 
3 6 13 20 44 45 74 87 

外側のループは n-1回実行されます。 内側のループが実行される回数は、与えられた配列の並び方によって 変わります。

挿入ソートは、バブルソートと比べると、内側のループで 実際のデータを交換する回数は同じとなりますが、 比較の回数は少ないです(後から正しい位置まで移動すると、 それで内側のループは繰り返しを止めるので)。

ほとんどの要素が整列されている場合は、内側のループはただちに 終了します。したがって、「整列済みの配列の後ろに要素を追加して、 その配列全体を再び整列させる」ような「ほとんどの要素が整列された 状態で整列を行う」場合は、この挿入ソートが適しています。

挿入ソートは安定なソートです。


シェルソート

挿入ソートを変形したアルゴリズム(p.306, Fig 13.1 「シェルソートの原理」参照)。 実用上、性能がよい。O(n2.5)O(n1.5)

シェルソートのアイディア
挿入ソートは、ほとんど整列されているデータを速く整列できる。
前処理によってデータの整列度を高めておいてから挿入ソートを使えば
高速にソートができるはずである。

増分(h)の選び方

シェルソートの定義
減少数列 h = h1, h2, ..., hl-1, hl
(ただし hl = 1) にしたがって 「h-ソート」を行う整列法。
"h-ソート (h-sort)" とは「hだけ離れた要素同士をソートすること」。

「整数 x, y に関して x > y であれば、『x-ソート』後『y-ソート』を 行えば、データは『x-ソート済み』かつ『y-ソート済み』の性質を満たす」 が一般に成り立つ。 したがって、最終的に1になるものであれば任意の減少数列を選ぶことができる。

ただし、次の性質には注意が必要である。

減少数列の性質
数列に現れる値は、互いに倍数になっていない方がよい。→理由はp.311 fig.13.2

どのような減少数列を用いると最良の結果が得られるかは、わかっていません。 しかし、Knuth が解析&実験的に求めたところ hi = 3 × hi+1 + 1 とすれば、よい結果 O(n1.25)が得られることが わかりました。 hs = 「2s-1 の逆順」 とすると O(n1.5)となることは証明されています。

教科書のプログラム(p.313, List13.1)では、Knuthの「h←3 * h + 1 の逆順」 を使って h を 121, 40, 13, 4, 1 と変化させる方法を採用しています。 hを求める際に n/9 を越えない間、 h←3*h+1 を計算しています。 「n/9を越えない」ようにしているのは、極端に離れた要素を h-ソート してもあまり高速化されず、むしろ欠点(余分な手間が増える)の方が大きいためです。

ShellSort.java
授業で配布するプリントを参照して下さい。

hが1より大きい値となるためには、hの初期値の計算で 1 < a.length / 9 が 成り立てばいいので a.length ≥ 18 となります(整数で計算することに注意)。 データの個数を18個にして動作させてみます。

ShellSort.javaの実行例
$ javac ShellSort.java
$ java ShellSort -d
データの個数を入力して下さい  18
11 3 16 7 13 4 9 17 2 5 12 8 15 1 18 10 6 14
h=4,i=4: 11 3 16 7 13 4 9 17 2 5 12 8 15 1 18 10 6 14 
h=4,i=5: 11 3 16 7 13 4 9 17 2 5 12 8 15 1 18 10 6 14 
h=4,i=6: 11 3 9 7 13 4 16 17 2 5 12 8 15 1 18 10 6 14 
h=4,i=7: 11 3 9 7 13 4 16 17 2 5 12 8 15 1 18 10 6 14 
h=4,i=8: 2 3 9 7 11 4 16 17 13 5 12 8 15 1 18 10 6 14 
h=4,i=9: 2 3 9 7 11 4 16 17 13 5 12 8 15 1 18 10 6 14 
h=4,i=10: 2 3 9 7 11 4 12 17 13 5 16 8 15 1 18 10 6 14 
h=4,i=11: 2 3 9 7 11 4 12 8 13 5 16 17 15 1 18 10 6 14 
h=4,i=12: 2 3 9 7 11 4 12 8 13 5 16 17 15 1 18 10 6 14 
h=4,i=13: 2 1 9 7 11 3 12 8 13 4 16 17 15 5 18 10 6 14 
h=4,i=14: 2 1 9 7 11 3 12 8 13 4 16 17 15 5 18 10 6 14 
h=4,i=15: 2 1 9 7 11 3 12 8 13 4 16 10 15 5 18 17 6 14 
h=4,i=16: 2 1 9 7 6 3 12 8 11 4 16 10 13 5 18 17 15 14 
h=4,i=17: 2 1 9 7 6 3 12 8 11 4 16 10 13 5 18 17 15 14 
h=1,i=1: 1 2 9 7 6 3 12 8 11 4 16 10 13 5 18 17 15 14 
h=1,i=2: 1 2 9 7 6 3 12 8 11 4 16 10 13 5 18 17 15 14 
h=1,i=3: 1 2 7 9 6 3 12 8 11 4 16 10 13 5 18 17 15 14 
h=1,i=4: 1 2 6 7 9 3 12 8 11 4 16 10 13 5 18 17 15 14 
h=1,i=5: 1 2 3 6 7 9 12 8 11 4 16 10 13 5 18 17 15 14 
h=1,i=6: 1 2 3 6 7 9 12 8 11 4 16 10 13 5 18 17 15 14 
h=1,i=7: 1 2 3 6 7 8 9 12 11 4 16 10 13 5 18 17 15 14 
h=1,i=8: 1 2 3 6 7 8 9 11 12 4 16 10 13 5 18 17 15 14 
h=1,i=9: 1 2 3 4 6 7 8 9 11 12 16 10 13 5 18 17 15 14 
h=1,i=10: 1 2 3 4 6 7 8 9 11 12 16 10 13 5 18 17 15 14 
h=1,i=11: 1 2 3 4 6 7 8 9 10 11 12 16 13 5 18 17 15 14 
h=1,i=12: 1 2 3 4 6 7 8 9 10 11 12 13 16 5 18 17 15 14 
h=1,i=13: 1 2 3 4 5 6 7 8 9 10 11 12 13 16 18 17 15 14 
h=1,i=14: 1 2 3 4 5 6 7 8 9 10 11 12 13 16 18 17 15 14 
h=1,i=15: 1 2 3 4 5 6 7 8 9 10 11 12 13 16 17 18 15 14 
h=1,i=16: 1 2 3 4 5 6 7 8 9 10 11 12 13 15 16 17 18 14 
h=1,i=17: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 
[nitta@ni java]$ java ShellSort -d2
データの個数を入力して下さい  18
11 3 16 7 13 4 9 17 2 5 12 8 15 1 18 10 6 14
h=4,i=4: 11 3 16 7 13 4 9 17 2 5 12 8 15 1 18 10 6 14 
h=4,i=5: 11 3 16 7 13 4 9 17 2 5 12 8 15 1 18 10 6 14 
h=4,i=6,j=6: 11 3 9 7 13 4 16 17 2 5 12 8 15 1 18 10 6 14 
h=4,i=6: 11 3 9 7 13 4 16 17 2 5 12 8 15 1 18 10 6 14 
h=4,i=7: 11 3 9 7 13 4 16 17 2 5 12 8 15 1 18 10 6 14 
h=4,i=8,j=8: 11 3 9 7 2 4 16 17 13 5 12 8 15 1 18 10 6 14 
h=4,i=8,j=4: 2 3 9 7 11 4 16 17 13 5 12 8 15 1 18 10 6 14 
h=4,i=8: 2 3 9 7 11 4 16 17 13 5 12 8 15 1 18 10 6 14 
h=4,i=9: 2 3 9 7 11 4 16 17 13 5 12 8 15 1 18 10 6 14 
h=4,i=10,j=10: 2 3 9 7 11 4 12 17 13 5 16 8 15 1 18 10 6 14 
h=4,i=10: 2 3 9 7 11 4 12 17 13 5 16 8 15 1 18 10 6 14 
h=4,i=11,j=11: 2 3 9 7 11 4 12 8 13 5 16 17 15 1 18 10 6 14 
h=4,i=11: 2 3 9 7 11 4 12 8 13 5 16 17 15 1 18 10 6 14 
h=4,i=12: 2 3 9 7 11 4 12 8 13 5 16 17 15 1 18 10 6 14 
h=4,i=13,j=13: 2 3 9 7 11 4 12 8 13 1 16 17 15 5 18 10 6 14 
h=4,i=13,j=9: 2 3 9 7 11 1 12 8 13 4 16 17 15 5 18 10 6 14 
h=4,i=13,j=5: 2 1 9 7 11 3 12 8 13 4 16 17 15 5 18 10 6 14 
h=4,i=13: 2 1 9 7 11 3 12 8 13 4 16 17 15 5 18 10 6 14 
h=4,i=14: 2 1 9 7 11 3 12 8 13 4 16 17 15 5 18 10 6 14 
h=4,i=15,j=15: 2 1 9 7 11 3 12 8 13 4 16 10 15 5 18 17 6 14 
h=4,i=15: 2 1 9 7 11 3 12 8 13 4 16 10 15 5 18 17 6 14 
h=4,i=16,j=16: 2 1 9 7 11 3 12 8 13 4 16 10 6 5 18 17 15 14 
h=4,i=16,j=12: 2 1 9 7 11 3 12 8 6 4 16 10 13 5 18 17 15 14 
h=4,i=16,j=8: 2 1 9 7 6 3 12 8 11 4 16 10 13 5 18 17 15 14 
h=4,i=16: 2 1 9 7 6 3 12 8 11 4 16 10 13 5 18 17 15 14 
h=4,i=17: 2 1 9 7 6 3 12 8 11 4 16 10 13 5 18 17 15 14 
h=1,i=1,j=1: 1 2 9 7 6 3 12 8 11 4 16 10 13 5 18 17 15 14 
h=1,i=1: 1 2 9 7 6 3 12 8 11 4 16 10 13 5 18 17 15 14 
h=1,i=2: 1 2 9 7 6 3 12 8 11 4 16 10 13 5 18 17 15 14 
h=1,i=3,j=3: 1 2 7 9 6 3 12 8 11 4 16 10 13 5 18 17 15 14 
h=1,i=3: 1 2 7 9 6 3 12 8 11 4 16 10 13 5 18 17 15 14 
h=1,i=4,j=4: 1 2 7 6 9 3 12 8 11 4 16 10 13 5 18 17 15 14 
h=1,i=4,j=3: 1 2 6 7 9 3 12 8 11 4 16 10 13 5 18 17 15 14 
h=1,i=4: 1 2 6 7 9 3 12 8 11 4 16 10 13 5 18 17 15 14 
h=1,i=5,j=5: 1 2 6 7 3 9 12 8 11 4 16 10 13 5 18 17 15 14 
h=1,i=5,j=4: 1 2 6 3 7 9 12 8 11 4 16 10 13 5 18 17 15 14 
h=1,i=5,j=3: 1 2 3 6 7 9 12 8 11 4 16 10 13 5 18 17 15 14 
h=1,i=5: 1 2 3 6 7 9 12 8 11 4 16 10 13 5 18 17 15 14 
h=1,i=6: 1 2 3 6 7 9 12 8 11 4 16 10 13 5 18 17 15 14 
h=1,i=7,j=7: 1 2 3 6 7 9 8 12 11 4 16 10 13 5 18 17 15 14 
h=1,i=7,j=6: 1 2 3 6 7 8 9 12 11 4 16 10 13 5 18 17 15 14 
h=1,i=7: 1 2 3 6 7 8 9 12 11 4 16 10 13 5 18 17 15 14 
h=1,i=8,j=8: 1 2 3 6 7 8 9 11 12 4 16 10 13 5 18 17 15 14 
h=1,i=8: 1 2 3 6 7 8 9 11 12 4 16 10 13 5 18 17 15 14 
h=1,i=9,j=9: 1 2 3 6 7 8 9 11 4 12 16 10 13 5 18 17 15 14 
h=1,i=9,j=8: 1 2 3 6 7 8 9 4 11 12 16 10 13 5 18 17 15 14 
h=1,i=9,j=7: 1 2 3 6 7 8 4 9 11 12 16 10 13 5 18 17 15 14 
h=1,i=9,j=6: 1 2 3 6 7 4 8 9 11 12 16 10 13 5 18 17 15 14 
h=1,i=9,j=5: 1 2 3 6 4 7 8 9 11 12 16 10 13 5 18 17 15 14 
h=1,i=9,j=4: 1 2 3 4 6 7 8 9 11 12 16 10 13 5 18 17 15 14 
h=1,i=9: 1 2 3 4 6 7 8 9 11 12 16 10 13 5 18 17 15 14 
h=1,i=10: 1 2 3 4 6 7 8 9 11 12 16 10 13 5 18 17 15 14 
h=1,i=11,j=11: 1 2 3 4 6 7 8 9 11 12 10 16 13 5 18 17 15 14 
h=1,i=11,j=10: 1 2 3 4 6 7 8 9 11 10 12 16 13 5 18 17 15 14 
h=1,i=11,j=9: 1 2 3 4 6 7 8 9 10 11 12 16 13 5 18 17 15 14 
h=1,i=11: 1 2 3 4 6 7 8 9 10 11 12 16 13 5 18 17 15 14 
h=1,i=12,j=12: 1 2 3 4 6 7 8 9 10 11 12 13 16 5 18 17 15 14 
h=1,i=12: 1 2 3 4 6 7 8 9 10 11 12 13 16 5 18 17 15 14 
h=1,i=13,j=13: 1 2 3 4 6 7 8 9 10 11 12 13 5 16 18 17 15 14 
h=1,i=13,j=12: 1 2 3 4 6 7 8 9 10 11 12 5 13 16 18 17 15 14 
h=1,i=13,j=11: 1 2 3 4 6 7 8 9 10 11 5 12 13 16 18 17 15 14 
h=1,i=13,j=10: 1 2 3 4 6 7 8 9 10 5 11 12 13 16 18 17 15 14 
h=1,i=13,j=9: 1 2 3 4 6 7 8 9 5 10 11 12 13 16 18 17 15 14 
h=1,i=13,j=8: 1 2 3 4 6 7 8 5 9 10 11 12 13 16 18 17 15 14 
h=1,i=13,j=7: 1 2 3 4 6 7 5 8 9 10 11 12 13 16 18 17 15 14 
h=1,i=13,j=6: 1 2 3 4 6 5 7 8 9 10 11 12 13 16 18 17 15 14 
h=1,i=13,j=5: 1 2 3 4 5 6 7 8 9 10 11 12 13 16 18 17 15 14 
h=1,i=13: 1 2 3 4 5 6 7 8 9 10 11 12 13 16 18 17 15 14 
h=1,i=14: 1 2 3 4 5 6 7 8 9 10 11 12 13 16 18 17 15 14 
h=1,i=15,j=15: 1 2 3 4 5 6 7 8 9 10 11 12 13 16 17 18 15 14 
h=1,i=15: 1 2 3 4 5 6 7 8 9 10 11 12 13 16 17 18 15 14 
h=1,i=16,j=16: 1 2 3 4 5 6 7 8 9 10 11 12 13 16 17 15 18 14 
h=1,i=16,j=15: 1 2 3 4 5 6 7 8 9 10 11 12 13 16 15 17 18 14 
h=1,i=16,j=14: 1 2 3 4 5 6 7 8 9 10 11 12 13 15 16 17 18 14 
h=1,i=16: 1 2 3 4 5 6 7 8 9 10 11 12 13 15 16 17 18 14 
h=1,i=17,j=17: 1 2 3 4 5 6 7 8 9 10 11 12 13 15 16 17 14 18 
h=1,i=17,j=16: 1 2 3 4 5 6 7 8 9 10 11 12 13 15 16 14 17 18 
h=1,i=17,j=15: 1 2 3 4 5 6 7 8 9 10 11 12 13 15 14 16 17 18 
h=1,i=17,j=14: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 
h=1,i=17: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 

h=4のときの動作は、データの列を4で割った余りで分類してみると 理解しやすくなります。

       i-h          i →iを増やして行く
       ↓          ↓
index:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17
-------------------------------------------------------------
余り0: 11          13           2          15           6
余り1:     3           4           5           1          14
余り2:       16           9          12          18
余り3:           7          17           8          10
a.length<18のときa.length/9=0 or 1h=1のまま
a.length=18のときa.length/9=2h=4
a.length=45のときa.length/9=5h=13
a.length=126のときa.length/9=14h=40
a.length=369のときa.length/9=41h=121
a.length=1098のときa.length/9=122h=364
a.length=3285のときa.length/9=365h=1093
a.length=9846のときa.length/9=1094h=3280
a.length=29529のときa.length/9=3281h=9841

InsertSort.javaの実行例と見比べて、動作の似ている部分と、異なる部分に ついてよく理解して下さい。

単純なソートは、非常に要素数が少い(数十個とか)場合にのみ使うことができます。 要素数が多い場合(多過ぎないとき)は、シェルソートを使うべきです。 また、要素数が非常に多い場合(1000以上とか)は、クイックソートを使うべきです。



アルゴリズムA 演習


作成したプログラムが正しく動作することを確認したら、それぞれの 提出先に提出しなさい。 提出した後は、正しく提出されていることを http://nw.tsuda.ac.jp/class/algoA/local/handin/ で必ず確認しておいて下さい。 提出〆切は次回の講義の開始時刻です。

課題15a: ShellSortのプログラムを動かしてみる

提出ファイルShellSort.java
コメント欄:dec400k.txt, inc400k.txt, dec400k.txtそれぞれに対する「シェルソートと挿入ソートの計算時間と、シェルソートの速度が挿入ソートの何倍か」
提出先: 「宿題提出Web:アルゴリズムA:課題15a」 http://nw.tsuda.ac.jp/class/algoA/local/handin/up.php?id=kadai15a

http://nw.tsuda.ac.jp/class/algoB/sortdata/ の下に、次の入力仕様を満たす3種類のデータが置いてあります。

これらの中のデータは最小値が0以上で最大値が999999以下であることが保証されています。 (アルゴリズムA課題14で使った http://nw.tsuda.ac.jp/class/algoA/sortdata/ と比較すると、データの個数が2倍、最大値は10倍のデータです。)

InsertSort.javaとShellSort.javaがこれらの3種類のデータを処理するのに 必要な時間をそれぞれ計測し、答えなさい。 さらにShellSort.javaの処理速度がInsertSort.javaの何倍であるかを 3種類のデータ毎に答えなさい。

課題15b: ShellSortにおけるデータの交換回数

提出ファイルShellSort2.java
コメント欄:3種類のデータ対するデータ交換の回数
提出先: 「宿題提出Web:アルゴリズムA:課題15b」 http://nw.tsuda.ac.jp/class/algoA/local/handin/up.php?id=kadai15b

ShellSort.javaを変更して、sort()メソッドの中でデータの交換が 何回行われたかを記録しておくようにしましょう。 そして、その回数を返すメソッド static long getCount() を新たに追加して下さい。ファイル名はShellSort2.javaとしましょう。 上記の3種類のデータに対して動作させて、それぞれsort()の中で データ交換が何回行われたかを調べて下さい。

CountShellSort.java
授業で配布するプリントを参照して下さい。
CountShellSort.javaの実行例
% javac CountShellSort.java
% java CountShellSort < rand400k.txt
ここに表示される交換回数を答えなさい。
% java CountShellSort < inc400k.txt
ここに表示される交換回数を答えなさい。
%java CountShellSort < dec400k.txt
ここに表示される交換回数を答えなさい。

課題15c: 挿入ソートにおけるデータの交換回数

提出ファイルInsertSort2.java
コメント欄:データ交換の回数およびShellSort2.javaの何倍か
提出先: 「宿題提出Web:アルゴリズムA:課題15c」 http://nw.tsuda.ac.jp/class/algoA/local/handin/up.php?id=kadai15c

InsertSort.javaを変更して課題15bと同等な機能を追加し、 ファイル名をInsertSort2.javaとして下さい。 InsertSortの中で、 rand400k.txt, inc400k.txt, dec400k.txt のそれぞれに対して データ交換が何回行われるか計測し、答えなさい。 さらに、それぞれのデータに対して、InsertSortはShellSortの何倍多く データを交換しているかを答えなさい。(0/0の場合は1と答えればよいものとします)

CountInsertSort.java
授業で配布するプリントを参照して下さい。
CountInsertSort.javaの実行例
% javac CountInsertSort.java
$ java CountInsertSort <rand400k.txt
ここに表示される交換回数を答えなさい。
$ java CountInsertSort <inc400k.txt
ここに表示される交換回数を答えなさい。
$ java CountInsertSort <dec400k.txt
ここに表示される交換回数を答えなさい。

[注意]

データの交換回数を記録しておく整数型の変数の型は、 (4byte=32bit幅の)intでは駄目で (8byte=64bit幅の)longでなければならないことに注意すること。

int型は32bitで符号(正負)があるため、表現可能な正の最大値は 231-1である。 210が約103 (正確には1024)であることから、 231では約2×109までの正の数しか表せないことがわかる。

今回扱っているデータの個数は400,000なので、 O(n2)のアルゴリズムでは、 400,0002 = 1.6×1011 回のオーダーの比較が起こり得る。