K.Maebashi's BBS

前橋さんの「C言語体当たり学習」の読者です。 正誤表に反映されてない誤りと思われる記述を見つけたので報告させていただきます。 p106のmy_sort5.cのソースコード36行目から始まる単純挿入ソートなのですが、 誤：for(sorted_count = 0; sorted_count < score_count; sorted_count++) { 正：for(sorted_count = 0; sorted_count < score_count - 1; sorted_count++) { ではないでしょうか（判定条件の-1が抜けてる）。 誤りと思われるコードでは、配列の範囲外を（配列の要素数より1つ分多く）参照してしまうと思います。

>p106のmy_sort5.cのソースコード36行目から始まる単純挿入ソートなのですが、 >誤：for(sorted_count = 0; sorted_count < score_count; sorted_count++) { >正：for(sorted_count = 0; sorted_count < score_count - 1; sorted_count++) { >ではないでしょうか（判定条件の-1が抜けてる）。 >誤りと思われるコードでは、配列の範囲外を（配列の要素数より1つ分多く） >参照してしまうと思います。 my_sort5.cは挿入ソートではなく、単純選択ソートですね。 ソースを確認しましたが、 (1)条件は「<」なのですから、sorted_countのループ内での最大値は 　score_count-1です。よって、score[sorted_count]で参照する限り、 　範囲外を参照することはありません。 (2)38行目からのループは、 　for (i = sorted_count + 1; i < score_count; i++) { 　で始まっています。iがsorted_count + 1から始まりますが、 　sorted_countが最大のとき、このループは1回も回らないので、score[i]で 　範囲外が参照されることもありません。 ただ、単純選択ソートの原理は「未ソート部分から最小値を探してきて左端に持ってくる」というものですから、最後にひとつ残された未ソートの要素は最大値に決まっているので、無駄といえば無駄ではあります。現状のソースだと43～45行目のスワップで、必ず同じ変数をひっくり返します。 これはバグとは思いませんが、補足かなにかで書いておいた方がよいかもしれませんね(今日は時間が時間なのでアレですが)。 ご意見ありがとうございました。

>my_sort5.cは挿入ソートではなく、単純選択ソートですね。 間違えました。 >(1)条件は「<」なのですから、sorted_countのループ内での最大値は >　score_count-1です。よって、score[sorted_count]で参照する限り、 >　範囲外を参照することはありません。 >(2)38行目からのループは、 >　for (i = sorted_count + 1; i < score_count; i++) { >　で始まっています。iがsorted_count + 1から始まりますが、 >　sorted_countが最大のとき、このループは1回も回らないので、score[i]で >　範囲外が参照されることもありません。 こちらから指摘しておいてすいません。その通りのようです。私が勘違いしていました。 もう一つ質問なのですが、36行目から始まる外側のforループの判定条件を 「i < score_count - 1」としなかったのは何か訳があってのことでしょうか？もし何か訳があれば補足をお願い致します。

面白い話題ですね。 私だったら、実行時の無駄を承知の上で判定条件を sorted_count < score_count; /* (-1)は付けない */ とします。 最小値を表す記号を min{x, y, z, ...} と書いたとき、 min{5, 3, 8} = 3 min{2, 2} = 2 min{6} = 6 などとなりますが、このminを定義(あるいは実装)するときに、 ・要素数が2個以上のとき……最小の要素を選ぶ ・要素数が1個　　のとき……その要素そのもの と場合分けするのが良いと考える人は少ないと思います。 そんな話はこの判定条件の問題とは違うのかもしれませんが、 大局的には同じようなセンスの問題をはらんでいると私には感じられます。 経験上は(って、アマチュアですけど)、このようなスタンスで臨むほうが 仕様変更や拡張に強いコーディングになるような気がします。

> 36行目から始まる外側のforループの判定条件を > 「i < score_count - 1」としなかったのは何か訳があってのことでしょうか？ > もし何か訳があれば補足をお願い致します。 C言語のfor文の判定条件は毎回評価されるので、年寄りとしては ループ内で不変な値を条件式に書くのは躊躇しちゃいますね。 たいてい lim = score_count - 1; for (sorted_count = 0; sorted_count < lim; sorted_count++) { としちゃいます。 まあ score_count が auto 変数でかつアドレス参照されてなければ、 あるいはループ内に関数呼びだしがなければ、いまどきのコンパイラは 自動的に同等な機械語に変換してくれるんでしょうけど。

>もう一つ質問なのですが、36行目から始まる外側のforループの判定条件を >「i < score_count - 1」としなかったのは何か訳があってのことでしょうか？ >もし何か訳があれば補足をお願い致します。 特に理由があるわけではないですし、こっちがよいとか主張したいわけでもないですが。 ・sorted_countは「ソートされた要素の数」である。 ・すべての要素がソートされた要素になればよいのだから、sorted_countが 　score_countになるまで回せばよい。 ということで、直感的であるかとは思います。 　107ページの図(Fig.2-7)に、「ソートずみの範囲」と「未ソートの範囲」を色分けし、間に線を引いた図がありますが、ソートが進むにつれ、この境界線がだんだん右に移動し、ついに右端に至ったときがソートの終了と考えれば、「sorted_count < score_count」になるように思います。境界線の右から左に、ぽいぽい要素を放り込んでいくイメージです。 　単純選択ソートにおいて、未ソート範囲から最小値を選ぶとき、たまたま未ソート範囲内の左端が最小値であれば、事実上交換は発生しません(同じ変数同士の交換になる)。、「sorted_count < score_count」としたとき最後に起きる無駄な交換も、現象としてはこれと同じです。単純選択ソートであれば、確かに言われてみれば最後に残った要素は最大値に決まってますから「境界線の右から左に放り込む」必要はないわけなのですが、コメントでも書いておかないと、私の場合「あれっ」とか思ってしまいそうです。 　挿入ソート(List 4-6)でも、「境界線の右から左に、ぽいぽい要素を放り込んでいく」操作を行いますが、こちらでは、最後に残るのが最大値とは限りません。単純選択ソートにおいて最後に最大値が残るのは、あくまでこのソート方法の特性なので、そこを理解して効率のよいコードを書くのもよいですが、必ずしもそこまでやらなくてもバチはあたらないのではないでしょうか。 # とか言いつつ挿入ソートのサンプルソースでは、sorted_countを1から始めてるな…(^^;

丁寧な解説ありがとうございます。 確かに、前橋さんのおっしゃるとおり、 >・sorted_countは「ソートされた要素の数」である。 >・すべての要素がソートされた要素になればよいのだから、sorted_countが 　score_countになるまで回せばよい。 と考えるのは直感的で分かりやすいと思います。 >　単純選択ソートにおいて、未ソート範囲から最小値を選ぶとき、たまたま未ソート範囲内の左端が最小値であれば、事実上交換は発生しません(同じ変数同士の交換になる)。、「sorted_count < score_count」としたとき最後に起きる無駄な交換も、現象としてはこれと同じです。 確かに、言われてみればそのとおりですね。 なんだか重箱の隅をつつくような質問ですいませんでした。