C言語の基本｜代表的なアルゴリズム

C言語の基本｜代表的なアルゴリズム

探す・並べる・計算する。定番のアルゴリズムを知れば、問題に合った解き方を選べるようになる。

アルゴリズムは、問題を解決するための手順です。

プログラムで扱う問題には、よく似たものが何度も登場します。たとえば、配列から目的の値を探す、複数の数値を小さい順に並べる、2つの整数から最大公約数を求めるといった問題です。

こうした問題には、以前から使われてきた代表的な解き方があります。

• データを探すなら探索アルゴリズム
• データを並べるならソートアルゴリズム
• 最大公約数を求めるならユークリッドの互除法
• 規則に従って数を作るなら数列のアルゴリズム

定番のアルゴリズムを知っていると、問題に出会うたびに手順を最初から考える必要がなくなります。目的やデータの状態を確認し、適したアルゴリズムを選べるようになるからです。

この記事では、C言語の初心者が最初に押さえておきたい探索、ソート、計算、数列のアルゴリズムを取り上げます。

代表的なアルゴリズムの全体像

代表的なアルゴリズムは、目的によって次のように整理できます。

同じ分野でも、データの状態や処理回数によって適したアルゴリズムが変わります。

たとえば探索では、データが並んでいなければ線形探索が使いやすく、整列済みなら二分探索を選べます。

図1：目的から選ぶ代表的なアルゴリズム

この図から分かること

アルゴリズムは、処理の目的によって分類できます。

目的の値を探す場合は探索、データを順番に並べる場合はソートを使います。最大公約数のような計算には専用の計算手順があり、規則に従って値を作る処理には数列のアルゴリズムがあります。

最初に何を実現したいのかを整理すると、候補となるアルゴリズムを選びやすくなります。

線形探索は先頭から順番に探す

線形探索は、配列の先頭から要素を1つずつ調べ、目的の値と一致するか確認する方法です。

リニアサーチとも呼ばれます。

基本的な手順は次のとおりです。

1. 配列の先頭要素を調べる
2. 目的の値と一致するか比較する
3. 一致したら探索を終了する
4. 一致しなければ次の要素を調べる
5. 最後まで一致しなければ、見つからなかったと判定する

線形探索では、データが小さい順や大きい順に並んでいる必要はありません。順番がばらばらの配列でも利用できます。

線形探索の利点と弱点

目的の値が配列の先頭付近にあれば、少ない比較で見つかります。

一方、目的の値が末尾にある場合や、配列内に存在しない場合は、すべての要素を調べることになります。

船舶センサーの識別番号を線形探索で探すプログラム

ファイル名：7_6_1.c

#include <stdio.h>

int main(void)
{
    int sensor_ids[] = {410, 275, 830, 146, 590};
    int count = 5;
    int target;
    int i;
    int found_index = -1;

    printf("探したいセンサーIDを入力してください > ");
    scanf("%d", &target);

    /* 線形探索で先頭から順番に調べる */
    for (i = 0; i < count; i++) {
        if (sensor_ids[i] == target) {
            found_index = i;
            break;
        }
    }

    if (found_index >= 0) {
        printf("センサーIDが見つかりました。\n");
        printf("配列の%d番目にあります。\n", found_index + 1);
    } else {
        printf("センサーIDは見つかりませんでした。\n");
    }

    printf("線形探索で先頭から順番に調べました。\n");

    return 0;
}

実行結果の例

探したいセンサーIDを入力してください > 830
センサーIDが見つかりました。
配列の3番目にあります。
線形探索で先頭から順番に調べました。

線形探索のプログラムを詳しく確認する

sensor_idsは、探索対象となる5個のセンサーIDを保存した配列です。

found_indexは、探索を始める前に-1で初期化しています。

配列の有効な添字は0から4なので、-1はまだ見つかっていないことを表す特別な値として利用できます。

forでは、iを0から1ずつ増やし、sensor_ids[i]とtargetを比較します。

targetとして830を入力した場合は、次の順番で探索します。

iが2のときに一致するため、found_indexへ2を代入してbreakを実行します。それ以降にある146と590は調べません。

配列の添字は0から始まりますが、実行結果では人が数える位置に合わせるため、found_index + 1を表示しています。そのため、添字2の要素は3番目と表示されます。

二分探索は範囲を半分ずつ絞る

二分探索は、整列済みのデータから目的の値を探すアルゴリズムです。バイナリサーチとも呼ばれます。

探索範囲の中央にある値を調べ、目的の値が中央より小さいか大きいかによって、次に調べる範囲を半分に絞ります。

昇順の配列では、次の手順で探索します。

1. 探索範囲の左端と右端を決める
2. 左端と右端の中央位置を求める
3. 中央の値と目的の値を比較する
4. 一致したら探索を終了する
5. 目的の値が中央より大きければ右半分に絞る
6. 目的の値が中央より小さければ左半分に絞る
7. 探索範囲がなくなるまで繰り返す

二分探索には整列済みのデータが必要

二分探索では、中央の値との大小関係から、片方の範囲を調べなくてもよいと判断します。

この判断ができるのは、データが順番に並んでいるからです。

配列が昇順なら、中央の値より左側には小さい値、右側には大きい値が並んでいます。データがばらばらでは、目的の値がどちら側にあるか判断できません。

整列済みのセンサーIDを二分探索で探すプログラム

ファイル名：7_6_2.c

#include <stdio.h>

int main(void)
{
    int sensor_ids[] = {120, 245, 310, 480, 625, 770, 910};
    int count = 7;
    int target;
    int left = 0;
    int right = count - 1;
    int middle;
    int found_index = -1;

    printf("探したいセンサーIDを入力してください > ");
    scanf("%d", &target);

    /* 二分探索で探索範囲を半分ずつ絞る */
    while (left <= right) {
        middle = (left + right) / 2;

        if (sensor_ids[middle] == target) {
            found_index = middle;
            break;
        } else if (sensor_ids[middle] < target) {
            left = middle + 1;
        } else {
            right = middle - 1;
        }
    }

    if (found_index >= 0) {
        printf("センサーIDが見つかりました。\n");
        printf("配列の%d番目にあります。\n", found_index + 1);
    } else {
        printf("センサーIDは見つかりませんでした。\n");
    }

    printf("二分探索で範囲を半分ずつ絞りました。\n");

    return 0;
}

実行結果の例

探したいセンサーIDを入力してください > 625
センサーIDが見つかりました。
配列の5番目にあります。
二分探索で範囲を半分ずつ絞りました。

二分探索のプログラムを詳しく確認する

leftは探索範囲の左端、rightは右端を表します。

最初は、添字0から6までの配列全体が探索範囲です。

middleはleftとrightを足して2で割ることで求めています。

625を探す場合は、次のように探索範囲が変化します。

最初の中央値は480です。目的の625は480より大きいため、添字0から3までは探索対象から外します。leftへmiddle + 1を代入し、探索範囲を添字4から6へ変更します。

次の中央値は770です。625は770より小さいため、rightへmiddle - 1を代入します。

最後は添字4の625と一致し、found_indexへ4を保存して探索を終了します。

leftがrightより大きくなった場合は、探索範囲がなくなったことを意味します。この状態まで一致する値がなければ、見つからなかったと判定します。

図2：線形探索と二分探索の探し方の違い

この図から分かること

線形探索は、配列の先頭から順番に調べます。データが並んでいなくても使用できますが、目的の値によっては多くの要素を調べる必要があります。

二分探索は、中央の値を基準に探索範囲を半分ずつ狭めます。調べる範囲を大きく減らせますが、データが整列されていることが条件です。

探索方法は速さだけで決めるのではなく、データが整列されているかどうかも確認して選びます。

ソートアルゴリズムはデータを順番に並べる

ソートは、複数のデータを決められた順番に並べ替える処理です。

小さい値から大きい値へ並べることを昇順、大きい値から小さい値へ並べることを降順といいます。

代表的なソートアルゴリズムには、次のものがあります。

どのアルゴリズムも最終的にはデータを同じ順番に並べられますが、比較や移動の手順が異なります。

インサーションソートは整列済みの範囲へ値を挿入する

インサーションソートは、配列の左側を整列済みの範囲として扱い、次の値を適切な位置へ挿入する方法です。

基本挿入法とも呼ばれます。

手元のカードを小さい順に並べる動きを考えると分かりやすいでしょう。新しいカードを1枚取り出し、すでに並んでいるカードの中から適切な位置を探して差し込みます。

基本的な手順は次のとおりです。

1. 先頭の要素を整列済みと考える
2. 2番目の要素を取り出す
3. 左側の整列済み要素と比較する
4. 取り出した値より大きい要素を右へ移動する
5. 空いた位置へ取り出した値を挿入する
6. 次の要素でも同じ処理を繰り返す

配列をインサーションソートで昇順に並べるプログラム

ファイル名：7_6_3.c

#include <stdio.h>

int main(void)
{
    int values[] = {7, 3, 8, 2, 5};
    int count = 5;
    int i;
    int j;
    int key;

    printf("並べ替え前: ");
    for (i = 0; i < count; i++) {
        printf("%d ", values[i]);
    }
    printf("\n");

    /* インサーションソートで昇順に並べる */
    for (i = 1; i < count; i++) {
        key = values[i];
        j = i - 1;

        while (j >= 0 && values[j] > key) {
            values[j + 1] = values[j];
            j--;
        }

        values[j + 1] = key;
    }

    printf("並べ替え後: ");
    for (i = 0; i < count; i++) {
        printf("%d ", values[i]);
    }
    printf("\n");

    printf("整列済みの範囲へ値を挿入しました。\n");

    return 0;
}

実行結果の例

並べ替え前: 7 3 8 2 5
並べ替え後: 2 3 5 7 8
整列済みの範囲へ値を挿入しました。

インサーションソートのプログラムを詳しく確認する

外側のforは、添字1から処理を始めます。先頭の要素だけなら、それだけで整列済みと考えられるからです。

keyへvalues[i]を保存した後、整列済み範囲の右端から値を比較します。

values[j]がkeyより大きければ、その値を1つ右へ移動します。keyを挿入できる位置が見つかるまで、この移動を繰り返します。

配列の変化は次のようになります。

iが1のときは3を取り出します。左側にある7は3より大きいため、7を右へ移動し、先頭へ3を挿入します。

iが2のときは8を取り出します。左側の7より大きいため、移動は発生しません。

iが3のときは2を取り出します。8、7、3を右へ移動し、先頭へ2を挿入します。

最後に5を取り出し、3と7の間へ挿入すると昇順の並びが完成します。

クイックソートは基準値でデータを分割する

クイックソートは、基準となる値を1つ選び、その値を使ってデータを分割するアルゴリズムです。

この基準値をピボットと呼びます。

基本的な考え方は次のとおりです。

1. 配列からピボットを選ぶ
2. ピボットより小さい値を一方へ集める
3. ピボットより大きい値をもう一方へ集める
4. 分割したそれぞれの範囲で同じ処理を行う
5. 分割できなくなるまで繰り返す

大きな問題を小さな問題へ分けて処理する考え方は、分割統治法と呼ばれます。

クイックソートは高速に動くことが多く、大量のデータを並べ替える方法として知られています。一方、処理を再帰的に繰り返す実装が登場するため、最初は分割して並べる考え方を理解できれば十分です。

ユークリッドの互除法は最大公約数を求める

ユークリッドの互除法は、2つの整数の最大公約数を求めるアルゴリズムです。

最大公約数は、2つの整数をどちらも割り切れる整数のうち、最も大きいものです。

互除法では、割り算の余りを使って値を小さくしていきます。

1. aをbで割った余りをrとする
2. aへbを代入する
3. bへrを代入する
4. bが0になるまで繰り返す
5. bが0になったときのaが最大公約数になる

84と30の最大公約数を求める場合は、次のように進みます。

余りが0になった時点のaは6です。そのため、84と30の最大公約数は6です。

2つの正の整数から最大公約数を求めるプログラム

ファイル名：7_6_4.c

#include <stdio.h>

int main(void)
{
    int first;
    int second;
    int remainder;

    printf("正の整数を2つ入力してください > ");
    scanf("%d %d", &first, &second);

    /* ユークリッドの互除法 */
    while (second != 0) {
        remainder = first % second;
        first = second;
        second = remainder;
    }

    printf("最大公約数は%dです。\n", first);
    printf("余りを使って値を小さくしました。\n");

    return 0;
}

実行結果の例

正の整数を2つ入力してください > 84 30
最大公約数は6です。
余りを使って値を小さくしました。

ユークリッドの互除法を詳しく確認する

firstとsecondには、入力された2つの正の整数を保存します。remainderには、割り算の余りを保存します。

最初はfirstが84、secondが30です。

84を30で割った余りは24なので、次の繰り返しではfirstが30、secondが24になります。

30を24で割った余りは6です。次はfirstが24、secondが6になります。

24を6で割った余りは0です。secondへ0が代入されるとwhileの条件が偽になり、繰り返しを終了します。

終了時のfirstには6が保存されているため、最大公約数として表示されます。

フィボナッチ数列は前2つの値から次の値を作る

フィボナッチ数列は、前の2つの値を足して次の値を作る数列です。

最初の2つを0と1にすると、次のように続きます。

0, 1, 1, 2, 3, 5, 8, 13, …

値の変化は次のとおりです。

フィボナッチ数列は再帰を使っても表現できます。しかし、単純な再帰では同じ計算を何度も行うことがあります。

初めて実装する場合は、forを使って順番に値を更新する方法が分かりやすくなります。

フィボナッチ数列を指定した個数だけ表示するプログラム

ファイル名：7_6_5.c

#include <stdio.h>

int main(void)
{
    int count;
    int i;
    int first = 0;
    int second = 1;
    int next;

    printf("表示する個数を入力してください > ");
    scanf("%d", &count);

    printf("フィボナッチ数列: ");

    for (i = 0; i < count; i++) {
        printf("%d ", first);

        next = first + second;
        first = second;
        second = next;
    }

    printf("\n");
    printf("前2つの値を足して次の値を作りました。\n");

    return 0;
}

実行結果の例

表示する個数を入力してください > 8
フィボナッチ数列: 0 1 1 2 3 5 8 13
前2つの値を足して次の値を作りました。

フィボナッチ数列のプログラムを詳しく確認する

最初にfirstを0、secondを1で初期化します。

forの中では、最初にfirstを表示します。その後、次の3つの処理で値を更新します。

1. firstとsecondを加算してnextへ保存する
2. secondをfirstへ移動する
3. nextをsecondへ移動する

countに8を入力した場合の変化は次のとおりです。

表示してから値を更新するため、最初の出力は0になります。これを指定された回数だけ繰り返すと、フィボナッチ数列を順番に表示できます。

線形探索と二分探索の比較回数

探索アルゴリズムを選ぶときは、目的の値を見つけるまでに何回程度の比較が必要になるかを考えます。

データ数をnとした場合の目安は次のとおりです。

二分探索では、1回比較するたびに探索範囲が半分になります。

1000個のデータは、おおよそ次のように絞られます。

• 1000個から500個
• 500個から250個
• 250個から125個
• 125個から約62個
• さらに半分ずつ減らす
• 最後は1個になる

2の10乗は1024なので、1000個程度のデータなら約10回で範囲を1個まで絞れます。

ただし、二分探索を使うにはデータが整列されている必要があります。データが未整列で、探索を1回だけ行う場合は、線形探索のほうが準備なしで利用できます。

ソートと探索をセットで考える

二分探索は高速ですが、データが整列されていなければ使えません。

そのため、未整列のデータに二分探索を使いたい場合は、先にソートする必要があります。

1回の検索だけなら、ソートにかかる処理のほうが大きくなる場合があります。

一方、会員番号やセンサーIDを何度も検索する場合は、最初にデータを並べておくことで、その後の検索回数を減らせます。

処理の前にデータを整えて、その後の処理を効率化する考え方は、前処理と呼ばれます。

バブル・セレクション・インサーションの動きを比較する

3つの基本的なソートは、確定していく位置とデータの動かし方が異なります。

バブルソートは比較の途中で何度も交換する場合があります。

セレクションソートは、最小値を探し終えてから交換するため、交換回数が少なくなりやすい方法です。

インサーションソートは、すでに並んでいる部分を利用します。最初からある程度並んでいるデータでは、移動する値が少なくなります。

図3：3つの基本ソートの動き

この図から分かること

バブルソートは、隣り合う値を比較しながら大きい値を右へ移動させます。

セレクションソートは、未整列範囲から最小値を探し、その範囲の先頭へ置きます。

インサーションソートは、左側の整列済み範囲へ新しい値を差し込みます。

最終的な並びが同じでも、比較する対象やデータの移動方法は異なります。途中の動きを追うことで、各アルゴリズムの特徴を理解しやすくなります。

代表的なアルゴリズムを学ぶ順番

アルゴリズムは、配列、繰り返し、条件分岐などの知識と結び付けながら学ぶと理解しやすくなります。

1. 線形探索
   配列をforで先頭から調べる基本を確認します。
2. バブルソート
   隣り合う値の比較と、一時変数を使った交換に慣れます。
3. セレクションソート
   未整列範囲から最小値を探す処理を学びます。
4. インサーションソート
   値を移動させ、適切な位置へ挿入する考え方を学びます。
5. 二分探索
   整列済みデータと探索範囲の管理を学びます。
6. ユークリッドの互除法
   whileを使って問題を少しずつ小さくする考え方を学びます。
7. フィボナッチ数列
   複数の変数を順番に更新する処理に慣れます。
8. クイックソート
   データの分割と再帰的な処理へ進みます。

最初はコードを暗記するのではなく、何を比較し、どの値を更新し、どの条件で終了するのかを追うことが大切です。

手順を言葉や表にしてからC言語へ置き換えると、代表的なアルゴリズムを別のデータにも応用しやすくなります。