シェルソートを徹底的に分解する

void shellsort(int v[], int n)
{
    int gap, i, j, temp;

    for (gap = n/2; gap > 0; gap /= 2)
        for (i = gap; i < n; i++)
            for (j = i - gap; j >= 0 && v[j] > v[j+gap]; j -= gap){
                temp = v[j];
                v[j] = v[j+gap];
                v[j+gap] = temp;
            }
}

これはシェルソートと呼ばれる関数である。n個の数値の配列を突っ込むと、その要素を小さい順にソートして返してくれる。たとえば、3,5,2,2,6,5,17と投げたら、2、2,3、5,5,6、17と返ってくるような関数。

これの中身がわかりづらかったので、分解して考えてみる。

まずここには3つのループがある。

複数のループは慣れないと混乱しやすい。押さえるべきポイントとしては、外側のループの1ループ目は内側のループがすべて終わらないかぎり、2ループ目には進めない。これを頭に叩き込むことが大事だ。だから外側のループの全体像を把握しながらも、まずは内側のループを精密に見ていくことから始めないといけない。

1番外側のループは、1回のループの操作で要素の数を半分に区切っていく。gap /= 2 というのはそういう処理である。半分といっても、Cでは int が割り切れない場合は小数点以下は切り捨てられる仕様である。たとえば、8個の要素があるとしたら、4個と4個に分ける。次のループでは2個、2個、2個、2個、1個に分ける。最後は全部1個になる。9個の要素があるとしたら、4個と4個と1個に分ける。次は2個2個2個2個1個。最後は全部1個。これを一般化すると、gap個とgap個とgap個と、、、、残り数個のグループができる。 最初の処理はn(配列の要素の数)を2で割るところから、それからさらにどんどん2で割っていってそれが1個になるまでやる。

2番目のループは、要素を左から右に進んでいくというループ。起点はどこからかというと、上のループで分けたグループの左から2つめの先頭(一番左)から。それが i = gap の意味。つまりv[gap]というのは左から2番目のグループの先頭に位置する。起点はそこからで、終点は一番右のv[n-1]の要素まで。ここで別々のグループの左からの順序が同じ要素を同じ組としてとらえる発想が大事。つまり、

v[i] と v[i + gap] と v[i + 2gap] ,,,,,,,,,

というふうに各グループからいっこずつ取ってきて組を作るイメージをもつこと。数学っぽく書くと、n mod gapの合同群という感じ。

最後のループ、つまり一番内側のループは、前のループの一個の左のグループからはじまる。たとえば4個,4個,1個でわかれていたとして、現在が2番目のループが2つめのグループの2番目だとしたら、それに対応するj= i- gapなので、一個左のグループの2番目。つまりi = v[5]のときは j = v[1]になる。そしてv[1]をv[5]と大小比較する。この大小比較からの交換こそが、このソートの具体的作業である。

これを比較して左<=右になるように交換する。そして操作対象を左にgroup個だけ移動する。入れ替えプロセスをするまでは、自分と同じ組の左側には自分よりも大きい数は存在しない。だが、入れ替えた時点で、右側からすごい小さい数が入ってくる可能性がある。だからこうやって戻らないといけない。そしてこれが一番大事なことだが、3番目のループが全部完了したということは、グループの i 番目の対応関係の要素のソートは完了したということを示している。つまり、

v[i] <= v[i + gap] <= v[i + 2gap],,,

という関係は必ず成立している。2番目のループが完了したということは、すべての i において、上の関係が成立したということである。

それからこのgapの幅を小さくしていくと、最終的には要素が1のグループがn個できることになって、それで上の関係が成立する。(遅くとも)この時点でソートは確実に完了している。


自分の中では完全に理解した感じがある。1時間以上、散歩をしながら考えていたらすっきりした。ループが複雑にネストしているときは、内側のネストが完了した時に一体どういう状態になっていることが意図されているのか、ということを想像していくのがポイントである。おそらくは関数の設計もそういう発想がないと筋道を立ててできないのだろうと思う。