はじめての C

「ソート法 5」

シェルソートの 背後にある アイデアとして、要素の交換が 挿入整列法と 比べて より 大きな距離で 行なわれる ということがあり、それで 高速度が 実現されるのです。

この分岐操作の テクニックは、"h-整列" - "h-sorting" - として 知られていて、シェルソートでは 通常、h 間で どの シーケンス(間隔) - sequence of h's - を 使うかによる 設計が されています。

シェルソートが、どのように 分岐操作を するかは、そのシーケンスに もとづいて 決められていて、前の例で いうと、4 と 2 と 1 に なります。

どんな シーケンスでも、それが 着実に 減算していく間は、使うことができます。 h が 1 に なると、そこで 終わりとなり また、ふつうの 挿入整列法が 使えますから、ここで 挿入整列法を 選ぶことで、たいていの ソートリストで 動かすことが できるようになります。

あるシーケンス h のほうが、他の それより 優れていることが あります。 評価の高い シーケンスとしては、1969年に クヌースによって 推奨された ものがあり、このシーケンスは、
1, 4, 13, 40, 121, 364, 1039, 3280, 9841, ...
と なっています。

これは 簡単ですし、他のシーケンスで もっと 効率的なのが あっても、それより 効果を 20% 以上 増やすことは むずかしいのです。

C/C++ の 実装では、これを 用いることにしましょう。

ところで、h の値が 1 に なったら 即、シェルソートを 挿入整列法に する、ということを 忘れては いませんね ?

ここでは うまい具合に、挿入整列法のために コードを 再実装しなくても、以前 書いておいた関数を 使うことができます。