はじめての C

「ソート法 2」

挿入整列法は とても簡単で、新しい要素 - new item - を 挿入するため、はじめに 要素を 右側に 移動させることによって、それぞれの 新しい要素を その位置 - position - に ソートできるように スペースを つくるのです。

例えば、次のような 数の リストが あるとします ▽

1, 2, 3, 4, 6, 7

数字の 5 を このリストに 挿入するのでしたら、はじめに 5 より大きな要素 - elements - を シフトして、空白 - gap - を 1つ セットします ▽

1, 2, 3, 4, , 6, 7

ひとたび シフトが 終われば、新しい要素を 空いている位置へと セットします ▽

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

挿入整列法で、なにか 気をつけるとすれば、それは 1つの要素が セットされたとしても、そこが 最終的な位置に なるとは 限らない、ということです。

次に入る 新しい要素が より小さければ、それより 大きな要素は シフトすることを 求められるからです。

挿入整列法は、元のリストが どう並んでいる - ordering - か 次第のところが あります。 なぜなら、リストも 順次に 始まっているなら、挿入整列法は 高速に なりますが、しかし、もし リストが 逆順だとすると、より 遅くなるからです。

このことは、挿入整列法を 実装するときに、よく 考えておかないと いけない、設計時の判定 - design decision - と なってきます。

もし ソートされる リストが、より逆順に 並んでいる - reverse sorted - のなら、ソートは その最後の要素から 走査を 始めるべきでしょう。

一般的な 解決法 - solution - であれば、リストが たとえ どんな順次で あったとしても、たぶん より 前方向 - forward - に ソートされているだろうとして、挿入整列法の 疑似コード - pseudocode - を つくってみることですね。

(疑似コードは 省略)