改めてC言語の物足りなさを実感しました。
今回の挿入ソートは、処理別に作られた関数に対して配列の受け渡しを行う事を基本としていたのですが、C言語は配列送りはポインタを使い、受取はNGということで改めてオブジェクト指向ではないプログラム言語の洗礼を受けてしまいました・・・orz
でも、こうした言語での慣れも必要ということは十分に認識しているので、今回のプログラムはフロー自体を変えて処理しています。
ローカライズを期待していた人はどうもすみません。
ソースコード
#include <stdio.h>
void insertSort(int *nums , int numsCount);
void arrayView(int *nums , int numsCount);
int main(){
// Data
int numbers[] = {10,2,12,7,16,8,13};
int numbersCount = (sizeof numbers / sizeof numbers[0]);
insertSort(numbers , numbersCount);
arrayView(numbers , numbersCount);
return 0;
}
void insertSort(int *nums , int numsCount){
for(int i=1; i<numsCount; i++){
// 対象値がひとつ左よりも小さい場合に移動する
if(nums[i-1] > nums[i]){
// 対象値
int targetNum = nums[i];
// 仮配列
int tmpNums[numsCount];
// 値入れ替え処理
for(int j=i-1; j>=0; j--){
if(nums[j] > targetNum){
nums[j+1] = nums[j];
nums[j] = targetNum;
}
else{
break;
}
}
}
}
}
void arrayView(int *nums , int numsCount){
for (int i=0; i<numsCount; i++) {
printf("%d \n",nums[i]);
}
}
実行
$ gcc -o insertSort insertSort.c
$ ./insertSort
2
7
8
10
12
13
16
解説
フロー変更について
挿入ソートの基本は、全体の数値軍の左側と右側とその間に位置する対象値の3ブロックあり、
対象値を左側の数字軍に当てはめていく方式なので、2次元のfor文で対応して関数を極力なくしました。
左側数値軍の入れ替え処理
プログラムの32行目からのfor文処理ですが、インクリメント方式ではなく、デクリメント方式を使っていますが、
これは、対象値を数値軍に差し込む時に数値を上書きしていくと、入れ替えた直後に、次の数値を上書きして消してしまうため、
数値軍を終わりから処理してく必要があったためです。
実際にやってみると、配列の内容が変に上書きされて壊れる事がわかるので、そのようにしてますが、新たに配列を格納する変数を作って対応してもいいんですが、無駄にメモリを使うよりも効率的な方法をとっていると理解してください。
wikipediaに乗っているサンプル
while文を使ってもう少し効率的に書かれていたので参考として載せておきます。
https://ja.wikipedia.org/wiki/挿入ソート
for (i = 1; i < n; i++) {
tmp = data[i];
if (data[i - 1] > tmp) {
j = i;
do {
data[j] = data[j - 1];
j--;
} while (j > 0 && data[j - 1] > tmp);
data[j] = tmp;
}
}
関連リンク
いろいろなプログラム言語でアルゴリズム学習
