2008 年度「計算機基礎論3B」 2008-12-19

§43 Shell ソート

(43.1) ここから、素朴でないソートについて学び始める。 自明なアルゴリズムではないので、しっかり取り組むこと。 初めに学ぶ Shell ソートでは、「どんな手順でやるか」がまずわかりにくい。 それを理解したうえで、 「ちょっと見たところ手間がかかるのに、なぜこのほうが速いのか?」 を考えることになる。 なお、Shell は人名である。

(43.2) (正の)自然数 m を一つ選んで固定する。 配列 a[1], ..., a[N] を、 その中から m おきに取り出した、 次の m 本の部分配列に分割する。

普通の日本語ではこれを「m-1 おきに取り出した」と呼ぶかもしれない。 このそれぞれの部分配列の中でソートを行ない、 それぞれの部分配列の中では小さい順にならんでいるようにすることを、 ここでは「m おきにソートする」と呼ぼう。

(43.3) 具体例で説明する。 次を「3 おきにソートする」としよう。

    18 08 13 93 78 32 81 65 02 40

まずは a[1] から始まる部分配列を考える。 “いまは見ない”部分は「..」とする。

    18 .. .. 93 .. .. 81 .. .. 40

これをこの中で小さい順に並べ替えるとこうなる。

    18 .. .. 40 .. .. 81 .. .. 93

こんどは a[2] から始まる部分配列を考え、それを小さい順に並べ替える。

    .. 08 .. .. 78 .. .. 65 .. ..
                  ↓
    .. 08 .. .. 65 .. .. 78 .. ..

最後に a[3] から始まる部分配列を考え、それを小さい順に並べ替える。

    .. .. 13 .. .. 32 .. .. 02 ..
                  ↓
    .. .. 02 .. .. 13 .. .. 32 ..

よって、最終的にはこうなる。

    18 08 02 40 65 13 81 78 32 93

(43.4) たとえば配列の大きさ N が 1000 のとき、

とするのが Shell ソートである。 各ステップは挿入ソートで行なう。 この数列 364, 121, 40, 13, 4, 1 は漸化式 m1 = 1, mn+1 = 3 * mn + 1 で定義される数列を逆順に見たものである。 この数列に特別な意味があるわけではない。 1 で終わる別の単調減少数列を選んでもよい。 ただし、あとでわかるように、 隣り合った項が互いに素であるほうが望ましいようである。

(43.5) 1 おきのソートとは普通のソートのことである。 それを最後に行なうから、 上のアルゴリズムで正しくソートが行なわれることは間違いない。 よって、これから考えるべき問題は、 「なぜこれが速いのか?」である。

(43.6) 整数 m, M が 0 < m < M を満たすとき、 次の事実が成り立つ。

M おきにソートしてから m おきにソートした結果は、 M おきにソートされている。

(43.7) (証明の概略: 「m おきの転倒数」を # {(i, j) | i < j かつ j-im の倍数、かつ a[i] > a[j]} で定義する。 いま、配列は M おきにソートされているとしよう。 m おきのソートが完了していなければ、 m おきの転倒数は 0 でなく、 転倒している組 a[i], a[i+m] が存在する。 この i に対し、 組 a[i+k*M], a[i+m+k*M]k は整数)のうち、転倒している組すべてに互換をほどこす。 この操作のあと、m おき転倒数が減少していること、 および M おきにソートされたままであることを観察せよ。 この操作を m おき転倒数が 0 になるまでくり返してゆけば m おきのソートが完了するのだから、 主張は正しい。)

(43.8) 仮に M が 5, m が 3 だったとしよう。 5 おきにソートし、それから 3 おきにソートしたあと、

であることはもちろんだが、a[i-5] <= a[i] にも注意すると が言える。 a[i-10] <= a[i] であることからは が出てくる。 ここに出てくる項をよく見ると、 「c が 8 以上ならば a[i-c] <= a[i]」が成り立つことがわかる。

(43.9) このあとに 1 おきのソートを挿入ソートで行なえばソートが完了するが、 上の考察から、任意の i に対し #{j | j < i かつ a[j] > a[i]} < 8 であることがわかるから、 どの要素を挿入する際も高々 8 回の比較・交換で十分である。 計算量をおおざっぱに調べてみよう。

Ο(N2) であることに変わりはないが、 挿入ソートの計算量の N2/4 と比べると、 N2 の係数が小さくなった分だけ、 速いはずである。

(43.10) ※ 実験してみると、 3 おきにソートする際の計算量はこれよりはるかに小さい。 それは、 その前に 5 おきにソートしたことで、小さいものが左に、 大きいものが右に寄っているためであろう。

(43.11) 上の例では「5 おき」「3 おき」にソートしたのがよい“下準備”となった。 そこから 8 という数が出てきて、 最後の「1 おき」のソートの計算量が 7N となったのだった。 一般の場合を考えよう。 整数 m, M が 0 < m < M を満たすとき、 M おきにソートしてから m おきにソートしたあとでは 0 以上の整数 x, y に対し a[i-(m*x+M*y)] <= a[i] が成り立つ。

(43.12) 次の定理 (Chinese Remainder Theorem) はすでに代数学の時間に習ったであろう。

a と b を互いに素な自然数とし、 d を整数とするとき、 方程式 ax+by = d は整数解 (x, y) をもつ。

(43.13) ことばを変えて言えば、 a と b とが互いに素なら直線 ax+by = d の上には格子点 (= x 座標も y 座標も整数である点)が存在する、 ということである。 (x, y) が解であるとき、任意の整数 k に対し (x+kb, y-ka) も解である。 これ以外の解がないことはすぐわかる。 よって、格子点は直線 ax+by = d の上に x 座標でみて b おき、y 座標でみて a おきに並んでいる。

(43.14) この定理から次が得られる。

a と b を互いに素な自然数とするとき、 整数 d が (a-1)(b-1) 以上ならば方程式 ax+by = d は 0 以上の整数の解 (x, y) をもつ。

(43.15) (証明の概略: 上の定理から、直線 ax+by = d の上に格子点があることはわかる。 この直線が二直線 x = -1, y = -1 と交わる点の、x 座標の差を考えよう。 d = (a-1)(b-1) のとき、 直線 y = -1 とは x = b-1+1/a で交わる。 これと x = -1 との差は b+1/a となり、b よりも大きい。 直線 ax+by = d は、d が大きくなるほど上方へ移動するので、 d がより大きければ、この差はさらに大きくなる。 よって、d が (a-1)(b-1) 以上であるならば、 直線 ax+by = d のうち x > -1 かつ y > -1 である部分に格子点があることがわかる。)

(43.16) ※ 方程式 ax+by = (a-1)(b-1)-1 は 0 以上の整数の解 (x, y) を持たない。 これは (b-1, -1) と (-1, a-1) とが隣り合った解であることからわかる。

(43.17) ※ さっきの例で出てきた「8」は (M-1)(m-1) にあたる。

(43.18) 上の例では「5 おき」「3 おき」「1 おき」にソートしたが、 この授業の実習では (43.4) で述べた単調増加数列を逆にたどりつつ、 もっと何度も「m おきのソート」を行なう。 mN 以上なら 「m おきのソート」とは何もしないことだから、 m が大きすぎても別に困らない。 よって、m の値は、(43.4) で述べた単調増加数列の項のうち、 いま使っているコンパイラの int 型で表せる最大の数から始めればよい。 その値は、次のプログラムを動かすことで求められるように 1743392200 である。 (このプログラム中の「25」という定数の値は試行錯誤を行なって決めた。)

#include <stdio.h>

main() {
    int i, m;

    m = 1;
    for (i = 1; i < 25; i++) {
        printf("%d\n", m);
        m = 3*m+1;
    }
}
このようにした場合の Shell ソートの理論的な計算量は私には全くわからない。

(43.19) 上では m 本の部分配列をそれぞれ m おきにソートすると説明したが、 実際には

とするほうが楽だろう。これなら三重ループで済むからである。

§44 課題3

(44.1) 課題2と同様のことを、Shell ソートについて行なえ。

(44.2) ※ Shell ソートのプログラムを書く際には、 最初から配列を画面いっぱいにとること。 N が 10 ぐらいでは意味がない。 また、初めのうちは、 途中で m が変わるごとに 「40 おきにソートします」 などと出力させるとよいかもしれない。 (これらの間にソートされてゆく過程が出力されることになる。)

(44.3) (43.4) で述べた単調増加数列を逆にたどる際の漸化式は m = (m-1)/3 でもよいが、 C言語では int 型の正の数どうしの割り算では余りは切り捨てられるから、 m = m/3 と書けばよい。

(44.4) N を大きくしての実験は、 N を 10000, 100000, 1000000 の三通りに変えて行え。

(44.5) 件名は「kadai3」(←全て半角文字、アルファベットは小文字、 途中にスペースをいれない)としてください。 これ以外の注意点は課題2と同じです。

§45 発展問題

(45.1) ここは、時間などに余裕がある人のためのオプション項目である。

(45.2) 5 おき、3 おき、1 おきにソートする Shell ソートのプログラムを書いてみよ。 それぞれの段階における比較回数・交換回数を出力するようにしてみよ。

(45.3) Shell ソートの m の取り方を別のものに変えたらどうなるか。 効率を調べてみよ。 (K&R2 の教科書に出ているものは N/2 から始めて 2 で割ってゆくものである。 これは、N が 2 のベキ乗のとき効率がよくないと言われている。 それを確かめてみるのもよい。)

(45.4) 上で書いたプログラムは、 int 型が 32 ビットの場合のものである。 それ以外の場合でも適切に動作する Shell ソートのプログラムを書いてみよ。


岩瀬順一