はじめての C

「ソート法 4」

シェルソートは、挿入整列法の 1つの バリエーションです。

挿入整列法であることを示す 理由の 1つに、要素は その右側の 要素としか 互いに 交換できない、ということがあり、配列を 通して、一度に 1ヶ所に 動けるだけです。 それで、時間が かかってしまいます。

シェルソートは、その分岐操作 - subdriving - で、要素を インタリーブ(介在)グループ - interleaved groups - に 収納し、各グループごとに ソートすることで、この問題を 解決しています。

例題で 考えてみましょう。

元になる リストです ▽

5, 6, 2, 7, 8, 4, 3, 1

シェルソートの 実装によって、リストの要素は 4組の ペアに 分割されます ▽

(5, 8) (6, 4) (2, 3) (7, 1)

それぞれのペアを ソートします ▽

5, 4, 2, 1, 8, 6, 3, 7

リストが 4要素ずつ 2セットに 分割されます ▽

(5, 2, 8, 3) (4, 1, 6, 7)

リストを ソートします ▽

2, 1, 3, 4, 5, 6, 8, 7

もう一度 全体を ソートすれば ▽

1, 2, 3, 4, 5, 6, 7, 8

なんだか、カードマジックみたいだ ...