Yet Another Clang Problems (2)
●問題11
下記に示すデータの度数分布表と累積度数表を求めるプログラムを作ってください。
リスト : 身長のデータ
double height[] = {
148.7, 149.5, 133.7, 157.9, 154.2, 147.8, 154.6, 159.1, 148.2, 153.1,
138.2, 138.7, 143.5, 153.2, 150.2, 157.3, 145.1, 157.2, 152.3, 148.3,
152.0, 146.0, 151.5, 139.4, 158.8, 147.6, 144.0, 145.8, 155.4, 155.5,
153.6, 138.5, 147.1, 149.6, 160.9, 148.9, 157.5, 155.1, 138.9, 153.0,
153.9, 150.9, 144.4, 160.3, 153.4, 163.0, 150.9, 153.3, 146.6, 153.3,
152.3, 153.3, 142.8, 149.0, 149.4, 156.5, 141.7, 146.2, 151.0, 156.5,
150.8, 141.0, 149.0, 163.2, 144.1, 147.1, 167.9, 155.3, 142.9, 148.7,
164.8, 154.1, 150.4, 154.2, 161.4, 155.0, 146.8, 154.2, 152.7, 149.7,
151.5, 154.5, 156.8, 150.3, 143.2, 149.5, 145.6, 140.4, 136.5, 146.9,
158.9, 144.4, 148.1, 155.5, 152.4, 153.3, 142.3, 155.3, 153.1, 152.3
};
階級 度数 累積度数 ------------------------ 130 - 135 1 1 135 - 140 6 7 140 - 145 12 19 145 - 150 25 44 150 - 155 32 76 155 - 160 17 93 160 - 165 6 99 165 - 170 1 100
階級はデータの範囲を表します。この表では x cm 以上 y cm 未満を x - y で表しています。度数はその階級に出現したデータの個数です。度数を示してある表のことを「度数分布表」といいます。累積度数はその階級までの度数を全部加えたものです。累積度数を示してある表を「累積度数分布表」といいます。
●問題12
問題11 のデータで、平均値と標準偏差を求めるプログラムを作ってください。データを x1, x2, ... , xN とすると、総計量 (合計値) と平均値は次式で求めることができます。
総計量 T = x1 + x2 + ... + xN
N
= Σ xi
i=1
平均値 M = (x1 + x2 + ... + xN) / N
N
= (1/N) * Σ xi
i=1
平均値が同じ場合でも、データの特徴が異なる場合があります。たとえば、A = {4, 4, 5, 5, 5, 6, 6, 6, 7, 7} と B = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} の平均値は 5.5 になります。A のデータは平均値の近くに集まっていてますが、B のデータはバラバラになっていますね。統計学では、ばらつきの大きさを表すために「分散 (variance)」という値を使います。分散の定義を次に示します。
分散 S2 = ((x1 - M)2 + (x2 - M)2 + ... + (xN - M)2) / N
N
= (1/N) * Σ (xi - M)2
i=1
標準偏差 S = √(S2)
分散の定義からわかるように、平均値から離れたデータが多いほど、分散の値は大きくなります。逆に、平均値に近いデータが多くなると分散は小さな値になります。そして、分散の平方根が「標準偏差 (SD : standard deviation)」になります。
●問題13
double 型の配列の中から最大値を求める関数 maximum と最小値を求める関数 minimum を定義してください。
double maximum(double buff[], int size); double minimum(double buff[], int size);
●問題14
double 型の配列 buff の中から引数 x と等しい要素があるか探索する関数 member, 位置を返す関数 position, 個数を数える関数 count を定義してください。等しい要素が見つからない場合、member は false を、position は -1 を返すものとします。
bool member(double x, double buff[], int size); int position(double x, double buff[], int size); int count(double x, double buff[], int size);
●問題15
文字列の長さを求める関数 length, 文字列をコピーする関数 copy, 文字列を連結する関数 concat を定義してください。なお、Ｃ言語の標準ライブラリ (string.h) には同等の機能を持つ関数 strlen, strcat, strcat が用意されています。
int length(char *s); char *copy(char *dst, char *src); char *concat(char *dst, char *src);
copy と concat は dst の先頭アドレスを返すものとします。
●問題16
文字列の中に文字があるか探索する関数 search_char, 文字列を比較する関数 string_compare, 文字列の中に文字列が含まれているか探索する関数 search_string を定義してください。なお、Ｃ言語の標準ライブラリ (string.h) には、同等の機能を持つ関数 strchr, strcmp, strstr が用意されています。
char *search_char(char c, char *buff); int string_comper(char *s1, char *s2); char *search_string(char *s, char *buff);
search_char と search_string の返り値は見つけた文字 (文字列の先頭) の位置 (アドレス) で、見つからない場合は NULL を返すものとします。sting_compare は、文字列 s1 と s2 が等しい場合は 0 を、s1 が s2 よりも大きい場合は正の整数を、s1 が s2 よりも小さい場合は負の整数を返すものとします。
●問題17
int 型の配列を「二分探索 (バイナリサーチ：binary searching)」する関数 binary_search を定義してください。
bool binary_search(int x, int buff[], int size);
線形探索の実行時間は要素数 N に比例するので、N が大きくなると時間がかかるようになります。これに対し、二分探索は log2 N に比例する時間でデータを探すことができます。ただし、探索するデータはあらかじめ昇順に並べておく必要があります。この操作を「ソート (sort)」といいます。二分探索は最初にデータをソートしておかないといけないので、線形探索に比べて準備に時間がかかります。
二分探索の動作を下図に示します。
図 : 二分探索
二分探索は探索する区間を半分に分割しながら調べていきます。キーが 66 の場合を考えてみましょう。まず区間の中央値 55 とキーを比較します。データが昇順にソートされている場合、66 は中央値 55 より大きいので区間の前半を調べる必要はありません。したがって、後半部分だけを探索すればいいのです。
あとは、これと同じことを後半部分に対して行います。最後には区間の要素が一つしかなくなり、それとキーが一致すれば探索は成功、そうでなければ探索は失敗です。ようするに、探索するデータ数が 1 / 2 ずつ減少していくわけです。上図の場合、線形探索ではデータの比較が 6 回必要になりますが、二分探索であれば 4 回で済みます。また、データ数が 1,000,000 個になったとしても、二分探索を使えば高々 20 回程度の比較で探索を完了することができます。
●問題18
「ソート (sort)」はある規則に従ってデータを順番に並べ換える操作です。たとえば、データが整数であれば大きい順に並べる、もしくは小さい順に並べます。ソートは昔から研究されている分野で、優秀なアルゴリズムが確立しています。ここでは簡単なソートアルゴリズム (遅いソート) を実際にプログラムしてみましょう。
バブルソート (buble sort) は泡がぶくぶくと浮いてくるように、いちばん小さいデータが後ろから前に浮かび上がってくるアルゴリズムです。隣接する 2 つのデータを比較して、順序が逆であれば入れ換えます。これを順番に後ろから前に行っていけば、いちばん小さなデータは頂上に浮かび上がっているというわけです。先頭が決まったならば、残りのデータに対して同じことを行えば、2 番目には残りのデータの中でいちばん小さいものが浮かび上がります。これをデータ数だけ繰り返せばソートが完了します。
9 5 3 7 6 4 8 交換しない
~~~
9 5 3 7 6 4 8 交換する
~~~
9 5 3 7 4 6 8 交換する
~~~
9 5 3 4 7 6 8 交換しない
~~~
9 5 3 4 7 6 8 交換する
~~~
9 3 5 4 7 6 8 交換する
~~~
3 9 5 4 7 6 8 いちばん小さいデータが決定する
+ 残りのデータに対して同様な操作を行う
図 : バブルソート
int 型の配列をバブルソートする関数 buble_sort を定義してください。
void buble_sort(int buff[], int size);
●問題19
選択ソート (selection sort) は、ソートしていないデータの中から最小値（または最大値）を見つけ、それを先頭のデータと交換する、という手順を繰り返すことでソートを行います。最初は、すべてのデータの中から最小値を探し、それを配列の先頭 buff[0] と交換します。次は、buff[1] 以降のデータの中から最小値を探し、それを buff[1] と交換します。これを繰り返すことでソートすることができます。
[9 5 3 7 6 4 8] 3 と 9 を交換する
+ +
3 [5 9 7 6 4 8] 5 と 4 を交換する
+ +
3 4 [9 7 6 5 8] 9 と 5 を交換する
+ +
3 4 5 [7 6 9 8] 7 と 6 を交換する
+ +
3 4 5 6 [7 9 8] 7 と 7 を交換する
+
3 4 5 6 7 [9 8] 9 と 8 を交換してソート終了
+ +
図 : 選択ソート
int 型の配列を選択ソートする関数 select_sort を定義してください。
void select_sort(int buff[], int size);
●問題20
単純挿入ソートの考え方はとても簡単です。ソート済みの配列に新しいデータを挿入していくことでソートを行います。次の図を見てください。
[9] 5 3 7 6 4 8 5 を取り出す
[9] * 3 7 6 4 8 5 を[9]の中に挿入する
[5 9] 3 7 6 4 8 9 をひとつずらして先頭に 5 を挿入
[5 9] * 7 6 4 8 3 を取り出して[5 9]の中に挿入する
[3 5 9] 7 6 4 8 先頭に 3 を挿入
[3 5 9] * 6 4 8 7 を取り出して[3 5 9] に挿入
[3 5 7 9] 6 4 8 9 を動かして 7 を挿入
残りの要素も同様に行う
図 : 挿入ソート
最初は先頭のデータひとつがソート済みと考えて、2 番目のデータをそこに挿入することからスタートします。データを挿入するので、そこにあるデータをどかさないといけません。そこで、挿入位置を決めるため後ろから順番に比較するとき、いっしょにデータの移動も行うことにします。
int 型の配列を単純挿入ソートする関数 insert_sort を定義してください。
void insert_sort(int buff[], int size);
●解答11
リスト : 度数分布表と累積度数表
#include <stdio.h>
#define N 100
#define M 8
double height[N] = {
・・・省略・・・
};
int main(void)
{
int freq[M] = {0}; // 度数分布表
int cum[M]; // 累積度数表
double low = 130.0;
double z = 5.0;
// 度数分布表の作成
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (height[i] < low + z * (j + 1)) {
freq[j]++;
break;
}
}
}
// 累積度数表の作成
cum[0] = freq[0];
for (int i = 1; i < M; i++)
cum[i] = cum[i - 1] + freq[i];
// 表示
for (int i = 0; i < M; i++) {
printf("%.1f - %.1f | ", low + z * i, low + z * (i + 1));
printf("%3d %3d\n", freq[i], cum[i]);
}
return 0;
}
配列 freq が度数分布表、cum が累積度数表、変数 low が階級の下限値、z が階級の幅を表します。freq は 0 で初期化します。度数分布表の作成は簡単です。最初の for ループで height の要素を取り出します。次の for ループで階級を求めます。変数 j が階級を表し、その上限値は low + z * (j + 1) で求めることができます。height[i] がこの値よりも小さい場合、その要素は階級 j であることがわかります。freq[j] の値をインクリメントして、for ループを脱出します。
累積度数表の作成も簡単です。cum[0] を freq[0] で初期化します。あとは、度数分布表の値 freq[i] と累積度数表の値 cum[i - 1] を足し算していくだけです。最後に、for ループで 2 つの表を出力します。
実行結果は次のようになります。
$ clang yacp11.c $ ./a.out 130.0 - 135.0 | 1 1 135.0 - 140.0 | 6 7 140.0 - 145.0 | 12 19 145.0 - 150.0 | 25 44 150.0 - 155.0 | 32 76 155.0 - 160.0 | 17 93 160.0 - 165.0 | 6 99 165.0 - 170.0 | 1 100
●解答12
平均値と標準偏差を求めるプログラムは簡単です。次のリストを見てください。
リスト : 平均値と標準偏差
#include <stdio.h>
#include <math.h>
#define N 100
double height[N] = {
・・・省略・・・
};
// 合計値を求める
double sum(double buff[], int size)
{
double a = 0.0;
for (int i = 0; i < size; i++) a += buff[i];
return a;
}
// 平均値と標準偏差
void meansd(double buff[], int size)
{
double m = sum(buff, size) / size;
double s = 0.0;
for (int i = 0; i < size; i++) {
double x = buff[i];
s += (x - m) * (x - m);
}
printf("mean = %.14f, sd = %f\n", m, sqrt(s / size));
}
void meansd2(double buff[], int size)
{
double m = 0.0, s = 0.0;
for (int i = 0; i < size; i++) {
double x = buff[i] - m;
m += x / (i + 1);
s += (i * x * x) / (i + 1);
}
printf("mean = %f, sd = %f\n", m, sqrt(s / size));
}
int main(void)
{
meansd(height, N);
meansd2(height, N);
return 0;
}
プログラムは簡単なので、説明は不要でしょう。参考文献 3 によると、データを 1 回通読するだけで平均値と標準偏差 (分散) を求めることができるそうです。これを参考にプログラムしたものが関数 meansd2 です。
$ clang -lm yacp12.c $ ./a.out mean = 150.62699999999998, sd = 6.433473 mean = 150.627000, sd = 6.433473
平均値は 150.63 cm で、標準偏差は 6.43 cm になりました。
●解答13
リスト : 最大値と最小値
#include <stdio.h>
#define N 100
double height[N] = {
・・・省略・・・
};
// 最大値
double maximum(double buff[], int size)
{
double max = buff[0];
for (int i = 1; i < size; i++)
if (max < buff[i]) max = buff[i];
return max;
}
// 最小値
double minimum(double buff[], int size)
{
double min = buff[0];
for (int i = 1; i < size; i++)
if (min > buff[i]) min = buff[i];
return min;
}
int main(void)
{
printf("max = %f\n", maximum(height, N));
printf("mix = %f\n", minimum(height, N));
return 0;
}
$ clang yacp13.c $ ./a.out max = 167.900000 mix = 133.700000
プログラムは簡単です。buff の先頭要素を変数 max (または min) に格納します。そして、for ループで 1 番目から順番に要素を取り出して、変数と比較します。buff[i] が max よりも大きい (または min よりも小さい) 場合は変数の値を buff[i] に書き換えます。最後に return で変数の値を返すだけです。
●解答14
リスト : 配列の線形探索
#include <stdio.h>
#include <stdbool.h>
bool member(double x, double buff[], int size)
{
for (int i = 0; i < size; i++)
if (x == buff[i]) return true;
return false;
}
int position(double x, double buff[], int size)
{
for (int i = 0; i < size; i++ )
if (x == buff[i]) return i;
return -1;
}
int count(double x, double buff[], int size)
{
int c = 0;
for (int i = 0; i < size; i++)
if (x == buff[i]) c++;
return c;
}
int main(void)
{
double a[] = {1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5};
if (member(4, a, 12))
printf("found\n");
else
printf("not found\n");
if (member(6, a, 12))
printf("found\n");
else
printf("not found\n");
printf("%d\n", position(1, a, 12));
printf("%d\n", position(5, a, 12));
printf("%d\n", position(6, a, 12));
printf("%d\n", count(1, a, 12));
printf("%d\n", count(5, a, 12));
printf("%d\n", count(6, a, 12));
return 0;
}
$ clang yacp14.c $ ./a.out found not found 0 11 -1 3 1 0
プログラムは簡単です。配列の先頭から順番にデータを比較していくだけです。これを「線形探索 (linear searching)」といいます。member はデータを発見したとき return で true を返します。for ループを終了したとき、データが見つからなかったので false を返します。position はデータが見つかったとき、要素の位置 (添字) を返します。見つからなかった場合は -1 を返します。count はデータを見つけたら変数 c を +1 します。最後に return で c を返すだけです。
●解答15
リスト : 文字列の操作 (1)
#include <stdio.h>
// 文字列の長さ
int length(char *s)
{
int len = 0;
while (*s++ != '\0') len++;
return len;
}
// 文字列のコピー
char *copy(char *dst, char *src)
{
char *p = dst;
while ((*p++ = *src++) != '\0');
return dst;
}
// 文字列の連結
char *concat(char *dst, char *src)
{
char *p = dst;
// ヌル文字のサーチ
while (*p != '\0') p++;
copy(p, src);
return dst;
}
int main(void)
{
char a[] = "hello,";
char b[] = "world";
char c[16];
printf("%d\n", length(a));
printf("%d\n", length(b));
printf("%s\n", copy(c, a));
printf("%s\n", concat(c, b));
return 0;
}
$ clang yacp15.c $ ./a.out 6 5 hello, hello,world
文字列はヌル文字 '\0' で終端されているので、文字数を数えるのは簡単です。*s がヌル文字でなければ s と len をインクリメントしていくだけです。文字列のコピーも簡単です。p を dst に初期化します。*p の値を *src に代入して、その値がヌル文字でなければ p と src をインクリメントしていきます。最後に dst を返します。concat も簡単です。while ループでヌル文字の位置を探し、そこから copy で src をコピーするだけです。
●解答16
リスト : 文字列の操作 (2)
#include <stdio.h>
char *search_char(char c, char *buff)
{
while (*buff != '\0') {
if (*buff == c) return buff;
buff++;
}
return NULL;
}
int string_compare(char *s1, char *s2)
{
while (*s1 == *s2) {
if (*s1 == '\0') return 0;
s1++;
s2++;
}
return *s1 - *s2;
}
char *search_string(char *s, char *buff)
{
if (*s == '\0') return buff;
for (; (buff = search_char(*s, buff)) != NULL; buff++) {
char *p = buff + 1;
char *q = s + 1;
while (*p != '\0' && *p == *q) {
p++;
q++;
}
if (*q == '\0') return buff;
}
return NULL;
}
int main(void)
{
char a[] = "abc def ghi foo bar baz";
char *p;
if ((p = search_char('a', a)) != NULL) printf("%c\n", *p);
if ((p = search_char('z', a)) != NULL) printf("%c\n", *p);
if ((p = search_char('A', a)) != NULL) printf("%c\n", *p);
printf("%d\n", string_compare("abc", "abc"));
printf("%d\n", string_compare("abc", "abC"));
printf("%d\n", string_compare("aBc", "abc"));
if ((p = search_string("abc", a)) != NULL) printf("%s\n", p);
if ((p = search_string("baz", a)) != NULL) printf("%s\n", p);
if ((p = search_string("oops", a)) != NULL) printf("%s\n", p);
return 0;
}
$ clang yacp16.c $ ./a.out a z 0 32 -32 abc def ghi foo bar baz baz
関数 search_char は文字を線形探索するだけです。見つけた場合は要素へのポインタを返し、見つからない場合は NULL を返します。関数 string_compare も簡単です。p と q を初期化して、*p と *q が等しいあいだ、p と q をインクリメントします。このとき、*p がヌル文字かチェックします。そうであれば文字列の内容は等しいので、return で 0 を返します。 while ループが終了したら、return で *s1 - *s2 を返します。
文字列の探索でいちばん簡単な方法は、テキストの先頭から探索する文字列（以降パターンと表記）を重ね合わせていくことです。テキストとパターンの文字を順番に比較し、パターンの末尾文字まで一致すれば探索は成功です。途中で文字が違っていれば探索は失敗です。パターンを重ね合わせる位置を一つずらして再度比較を行います。これを「力まかせの探索 (brute-force searching)」といいます。
最初に *s がヌル文字かチェックします。この場合、*s は空文字列になるので、buff の先頭とマッチングすると考えて、buff を返します。次の for ループで、先頭文字 *s を string_search で検索します。見つからなければ、for ループを終了して NULL を返します。
次の while ループでパターンとテキストを照合します。ポインタ p, q を buff + 1 と s + 1 に初期化します。そして、*p がヌル文字ではなく、かつ *p == *q の間は p, q をインクリメントします。while ループを終了したあと、*q がヌル文字であれば、パターンはすべてテキストと一致しました。return で buff を返します。そうでなければ、buff をインクリメントして探索を繰り返します。
●解答17
リスト : 二分探索
#include <stdio.h>
#include <stdbool.h>
bool binary_search(int x, int buff[], int size)
{
int low = 0, high = size - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (buff[mid] == x)
return true;
else if (buff[mid] < x)
low = mid + 1;
else
high = mid - 1;
}
return false;
}
int main(void)
{
int a[] = {10, 20, 30, 40, 50, 60, 70, 80, 90};
printf("%d\n", binary_search(0, a, 9));
printf("%d\n", binary_search(10, a, 9));
printf("%d\n", binary_search(40, a, 9));
printf("%d\n", binary_search(90, a, 9));
printf("%d\n", binary_search(100, a, 9));
return 0;
}
最初に、探索する区間を示す変数 low と high を初期化します。low を 0 に、最後の要素の位置 (size - 1) を high にセットします。次の while ループで、探索区間を半分ずつに狭めていきます。まず、区間の中央値を求めて変数 mid にセットします。if 文で mid の位置にある要素と x を比較し、等しい場合は探索成功です。return で true を返します。
x が大きい場合は区間の後半を調べます。変数 low に mid + 1 をセットします。逆に、x が小さい場合は前半を調べるため、変数 high に mid - 1 をセットします。これを二分割できる間繰り返します。low が high より大きくなったら分割できないので繰り返しを終了し false を返します。
実行結果を示します。
$ clang yacp17.c $ ./a.out 0 1 1 1 0
二分探索はデータを高速に探索することができますが、あらかじめデータをソートしておく必要があります。このため、途中でデータを追加するには、データを挿入する位置を求め、それ以降のデータを後ろへ移動する処理が必要になります。つまり、データの登録には時間がかかるのです。
したがって、二分探索はプログラムの実行中にデータを登録し、同時に探索も行うという使い方には向いていません。途中でデータを追加して探索も行う場合は、他の高速な探索アルゴリズムを検討してみてください。
●解答18
リスト : バブルソート
#include <stdio.h>
void buble_sort(int buff[], int size)
{
for (int i = 0; i < size; i++) {
for (int j = size - 1; j > i; j--) {
if (buff[j] < buff[j - 1]) {
int temp = buff[j];
buff[j] = buff[j - 1];
buff[j - 1] = temp;
}
}
}
}
// 配列の表示
void print_buff(int buff[], int size)
{
for (int i = 0; i < size; i++) printf("%d ", buff[i]);
printf("\n");
}
int main(void)
{
int a[] = {5,6,4,7,3,8,2,9,1,0};
int b[] = {9,8,7,6,5,4,3,2,1,0};
int c[] = {0,1,2,3,4,5,6,7,8,9};
buble_sort(a, 10);
print_buff(a, 10);
buble_sort(b, 10);
print_buff(b, 10);
buble_sort(c, 10);
print_buff(c, 10);
return 0;
}
最初のループで size 回だけ繰り返します。2 番目のループで buff の後ろから前に向かって、確定していないデータを比較していき、もしも順番が逆になっていたら交換します。とても簡単ですね。
実行結果を示します。
$ clang yacp18.c $ ./a.out 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
●解答19
リスト : 選択ソート
#include <stdio.h>
void select_sort(int buff[], int size)
{
for (int i = 0; i < size - 1; i++) {
int min = buff[i];
int n = i;
for (int j = i + 1; j < size; j++) {
if (buff[j] < min) {
min = buff[j];
n = j;
}
}
buff[n] = buff[i];
buff[i] = min;
}
}
// 配列の表示
void print_buff(int buff[], int size)
{
for (int i = 0; i < size; i++) printf("%d ", buff[i]);
printf("\n");
}
int main(void)
{
int a[] = {5,6,4,7,3,8,2,9,1,0};
int b[] = {9,8,7,6,5,4,3,2,1,0};
int c[] = {0,1,2,3,4,5,6,7,8,9};
select_sort(a, 10);
print_buff(a, 10);
select_sort(b, 10);
print_buff(b, 10);
select_sort(c, 10);
print_buff(c, 10);
return 0;
}
最初のループで変数 i の値は 0 から size - 1 まで動きます。2 番目のループで buff[i] から buff[size - 1] までの中から最小値を探し、それを buff[i] と交換します。最小値とその位置は変数 min と n に格納します。2 番目のループを終了したら、buff[i] と buff[n] の値を交換します。
実行結果を示します。
$ clang yacp19.c $ ./a.out 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
選択ソートも実行時間はデータの個数の 2 乗に比例します。
●解答20
リスト : 単純挿入ソート
#include <stdio.h>
void insert_sort(int buff[], int size)
{
for (int i = 1; i < size; i++) {
int j, temp = buff[i];
for (j = i - 1; j >= 0 && temp < buff[j]; j--) {
buff[j + 1] = buff[j];
}
buff[j + 1] = temp;
}
}
void print_buff(int buff[], int size)
{
for (int i = 0; i < size; i++) printf("%d ", buff[i]);
printf("\n");
}
int main(void)
{
int a[] = {5,6,4,7,3,8,2,9,1,0};
int b[] = {9,8,7,6,5,4,3,2,1,0};
int c[] = {0,1,2,3,4,5,6,7,8,9};
insert_sort(a, 10);
print_buff(a, 10);
insert_sort(b, 10);
print_buff(b, 10);
insert_sort(c, 10);
print_buff(c, 10);
return 0;
}
最初のループで挿入するデータを選びます。ソート開始時は先頭のデータひとつがソート済みと考えるるので、2 番目のデータ（添字では 1）を取り出して挿入していきます。2 番目のループで挿入する位置を探しています。探索は後ろから前に向かって行います。このとき、挿入位置の検索と同時にデータの移動も行っています。ループが最後まで回れば、そのデータは先頭に挿入されることになります。
実行結果を示します。
$ clang yacp20.c $ ./a.out 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
挿入ソートも実行時間はデータの個数の 2 乗に比例します。
ところで、単純挿入ソートは面白い特徴があり、ソート済みのデータは高速にソートできることが知られています。データがソートされていれば、2 番目のループは繰り返しを行わずに終了するため、最初のループの繰り返し回数でソートが完了することになります。したがって、与えられたデータが大まかにでもソートされていれば、2 番目のループで繰り返す回数が少なくなり、挿入ソートでも高速にソートすることができます。
改訂 2023 年 4 月 2 日