挿入ソートを変形したアルゴリズム(p.306, Fig 13.1 「シェルソートの原理」参照)。 実用上、性能がよい。$O(n^{2.5})$ 〜 $O(n^{1.5})$
シェルソートのアイディア |
挿入ソートは、ほとんど整列されているデータを速く整列できる。 前処理によってデータの整列度を高めておいてから挿入ソートを使えば 高速にソートができるはずである。 |
シェルソートの定義 |
減少数列 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 が解析&実験的に求めたところ
$h_i = 3 \times h_{i+1} + 1$
とすれば、よい結果 $O(n^{1.25})$ が得られることがわかりました。
$h_i = \mbox{「} 2^i -1 \mbox{の逆順」}$
とすると
$O(n^{1.5})$
となることは証明されています。
教科書のプログラム(p.313, List13.1)では、Knuthの「$h \leftarrow 3 * h + 1$ の逆順」 を使って $h$ を $121$, $40$, $13$, $4$, $1$ と変化させる方法を採用しています。 $h$ を求める際に $n/9$ を越えない間、 $h \leftarrow 3*h+1$ を計算しています。 「$n/9$ を越えない」ようにしているのは、極端に離れた要素を $h$-ソート してもあまり高速化されず、むしろ欠点(余分な手間が増える)の方が大きいためです。
$h$ が $1$ より大きい値となるためには、$h$ の初期値の計算で 1 < a.length / 9
が成り立てばいいので a.length ≥ 18
となります(整数で計算することに注意)。
データの個数を 18 個にして動作させてみます。
ShellSort.javaの実行例 |
|
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 1 | h=1のまま |
a.length=18のとき | a.length/9=2 | h=4 |
a.length=45のとき | a.length/9=5 | h=13 |
a.length=126のとき | a.length/9=14 | h=40 |
a.length=369のとき | a.length/9=41 | h=121 |
a.length=1098のとき | a.length/9=122 | h=364 |
a.length=3285のとき | a.length/9=365 | h=1093 |
a.length=9846のとき | a.length/9=1094 | h=3280 |
a.length=29529のとき | a.length/9=3281 | h=9841 |
InsertSort.javaの実行例と見比べて、動作の似ている部分と、異なる部分に ついてよく理解して下さい。
単純なソートは、非常に要素数が少い(数十個とか)場合にのみ使うことができます。 要素数が多い場合(多過ぎないとき)は、シェルソートを使うべきです。 また、要素数が非常に多い場合(1000以上とか)は、クイックソートを使うべきです。
作成したプログラムが正しく動作することを確認したら、それぞれの 提出先に提出しなさい。 提出した後は、正しく提出されていることを http://ynitta.com/class/algoB/local/handin/ で必ず確認しておいて下さい。 提出〆切は次回の講義の開始時刻です。
提出ファイル | ShellSort.java |
---|---|
コメント欄: | dec400k.txt, inc400k.txt, dec400k.txtそれぞれに対する「シェルソートと挿入ソートの計算時間と、シェルソートの速度が挿入ソートの何倍か」 |
提出先: | 「宿題提出Web:アルゴリズムA:課題3a」 http://ynitta.com/class/algoB/local/handin/up.php?id=kadai3a |
http://ynitta.com/class/algoB/sortdata/ の下に、次の入力仕様を満たす3種類のデータが置いてあります。
InsertSort.javaとShellSort.javaがこれらの3種類のデータを処理するのに 必要な時間をそれぞれ計測し、答えなさい。 さらにShellSort.javaの処理速度がInsertSort.javaの何倍であるかを 3種類のデータ毎に答えなさい。
提出ファイル | ShellSort2.java |
---|---|
コメント欄: | 3種類のデータ対するデータ交換の回数 |
提出先: | 「宿題提出Web:アルゴリズムA:課題3b」 http://ynitta.com/class/algoB/local/handin/up.php?id=kadai3b |
ShellSort.javaを変更して、sort()メソッドの中でデータの交換が 何回行われたかを記録しておくようにしましょう。 そして、その回数を返すメソッド static long getCount() を新たに追加して下さい。ファイル名はShellSort2.javaとしましょう。 上記の3種類のデータに対して動作させて、それぞれsort()の中で データ交換が何回行われたかを調べて下さい。
CountShellSort.javaの実行例 |
|
提出ファイル | InsertSort2.java |
---|---|
コメント欄: | データ交換の回数およびShellSort2.javaの何倍か |
提出先: | 「宿題提出Web:アルゴリズムA:課題3c」 http://ynitta.com/class/algoB/local/handin/up.php?id=kadai3c |
InsertSort.javaを変更して課題3bと同等な機能を追加し、 ファイル名をInsertSort2.javaとして下さい。 InsertSortの中で、 rand400k.txt, inc400k.txt, dec400k.txt のそれぞれに対して データ交換が何回行われるか計測し、答えなさい。 さらに、それぞれのデータに対して、InsertSortはShellSortの何倍多く データを交換しているかを答えなさい。(0/0の場合は1と答えればよいものとします)
CountInsertSort.javaの実行例 |
|
データの交換回数を記録しておく整数型の変数の型は、
4byte (= 32bit) 幅の int
型では駄目で
8byte (= 64bit) 幅の long 型でなければならない。
int型は32bitで符号(正負)があるため、表現可能な正の最大値は $2^{31} - 1$ である。 $2^{10}$ が約 $10^3$ (正確には $1024$ )であることから、 $2^{31}$ では約 $2 \times 10^9$ までの正の整数しか表せないことがわかる。
今回扱っているデータの個数は $400,000$ なので、 $O(n^2)$ のアルゴリズムでは、 $400,000^2 = 1.6 \times 10^{11}$ 回のオーダーの比較が起こり得る。