[アルゴリズム] 挿入ソートの実装(C言語編)

cube-896419_1280
LINEで送る
Share on GREE
Share on LinkedIn

改めてC言語の物足りなさを実感しました。
今回の挿入ソートは、処理別に作られた関数に対して配列の受け渡しを行う事を基本としていたのですが、C言語は配列送りはポインタを使い、受取はNGということで改めてオブジェクト指向ではないプログラム言語の洗礼を受けてしまいました・・・orz
でも、こうした言語での慣れも必要ということは十分に認識しているので、今回のプログラムはフロー自体を変えて処理しています。
ローカライズを期待していた人はどうもすみません。

ソースコード

実行

解説

フロー変更について

挿入ソートの基本は、全体の数値軍の左側と右側とその間に位置する対象値の3ブロックあり、
対象値を左側の数字軍に当てはめていく方式なので、2次元のfor文で対応して関数を極力なくしました。

左側数値軍の入れ替え処理

プログラムの32行目からのfor文処理ですが、インクリメント方式ではなく、デクリメント方式を使っていますが、これは、
対象値を数値軍に差し込む時に数値を上書きしていくと、入れ替えた直後に、次の数値を上書きして消してしまうため、
数値軍を終わりから処理してく必要があったためです。
実際にやってみると、配列の内容が変に上書きされて壊れる事がわかるので、そのようにしてますが、新たに配列を格納する変数を作って対応してもいいんですが、無駄にメモリを使うよりも効率的な方法をとっていると理解してください。

wikipediaに乗っているサンプル

while文を使ってもう少し効率的に書かれていたので参考として載せておきます。

関連リンク

挿入ソート

解説
Javascript
PHP
Python
Shell
AWK
C言語

アルゴリズム過去記事

http://wordpress.ideacompo.com/?cat=562&tag=Algorithm

Leave a Reply

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です