具体的なアルゴリズム

アルゴリズム一覧

（徹底攻略 応用情報技術者教科書 平成30年度を参考に執筆しました。）

探索アルゴリズムには、

探索アルゴリズム	説明
線形探索	先頭からひとつひとつ順番に探索する
二分探索	データは最初からあらかじめ整列させておき、 真ん中から二分割して「前」と「後」のどちらかにデータがあると予測しながら、 真ん中の値と比較してどちらに行くべきかを判断した上で、 前あるいは後の部分の真ん中と比較し、 これを繰り返してデータを探索する
ハッシュテーブル探索	データのハッシュ値をハッシュ関数で求めることで探索する

などがある。

また、整列アルゴリズムには、

整列アルゴリズム	説明
バブルソート	隣り合う要素を比較し、大小関係に基づいて入れ替えし続ける
挿入ソート	まっさらな新しい整列された列の、的確な場所に要素を挿入し続ける
選択ソート	整列されていない列の最大値あるいは最小値を検索し続ける
クイックソート	中間となる基準値を設定し、それよりも大きな値を含む列と、 小さな値を含む列に振り分け、その中でさらに基準値を設定する
シェルソート	ある一定の間隔で取り出した要素を整列させ、 間隔を少しずつ狭めていき、最終的に間隔を1にする
ヒープソート	整列されていない列をヒープとし、ヒープの根から最大値・最小値を取り出し、 それを整列された列に渡す
マージソート	整列されていない列を前半部分と後半部分に分け、 それ以上分割できず大きさが1になるまで分割を繰り返し、 分割を最後まで行った後で前半と後半をマージして、 整列後の列を作るということを繰り返し、最後に全体をマージする

などがある。

計算量オーダーとオーダー記法

アルゴリズムの計算量を表すために、O記法（オーダー記法）というのを使用する。

ハッシュテーブル探索はO(1)、二分探索はO(log N)、線形探索はO(N)となる。

バブルソート・挿入ソート・選択ソートは計算量がO(N²)と時間がかかる。

これに対してクイックソート・シェルソート・ヒープソート・マージソートは計算量がO(N log N)と高速。

詳しくは以下の書籍・ページが参考になる。

• 徹底攻略 応用情報技術者教科書 平成30年度
• 計算量オーダーについて - Qiita

二分探索と二分探索木

二分探索において、目的の値や単語などを探すには、まず単語を小さいほうから大きいほうへとソートして整理しておく。まず、中央値と比較し、それよりも小さければ左、それよりも大きければ右に移動して、左側あるいは右側の、全体の半分の中の中央値を比較し、左または右に移動し、これを繰り返す。

このようにすることで、片方に移動した場合、もう片方には単語は存在しないことが分かっているため、それを除いていくことで、最短で値や単語を探索できる。

二分探索木は、二分木を用いた、二分探索がしやすいようにツリー構造を構築する方法。

二分探索木において、要素の左の子要素は必ず親よりも小さく、要素の右の子要素は必ず親よりも大きくなる。そのようにツリーは常に整理されて築かれている。探索を行う際は、要素より小さければ左、大きければ右へと辿っていく。新しい値を配置する場合は、それを適切な要素の左あるいは右の子要素とする。

また、ツリーの深さが深くなりすぎないように、中心を回転させる平衡木のことをAVL木と呼ぶ。

（詳しくはプログラミング言語C（K&R）が参考になります。）

アルゴリズムのコード例

The Algorithms

アルゴリズムの勉強をするために参考になるサイトとして、The Algorithmsが挙げられる。

さまざまな言語で記述されたさまざまなアルゴリズムのコード例が掲載されている。

アルゴリズムの図鑑として勉強のために使う以外にも、アルゴリズムを自分で実装する際、The Algorithmsのコードを参考にして実装することで手間と負担を軽減できる。

• The Algorithms
• @Comamoca_さんのツイート

AIによるサンプル

以下はGoogleのAIが書いたバブルソートと二分探索のサンプルコード。バブルソートで昇順に並べ替えた後で、二分探索で特定の値を探索する。

#include <stdio.h>

// バブルソート関数
void bubbleSort(int arr[], int n) {
    int i, j, temp;
    for (i = 0; i < n - 1; i++) {
        for (j = 0; j < n - i - 1; j++) {
            // 隣り合う要素を比較し、前が大きければ入れ替える
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

// 二分探索関数 (見つかった場合はインデックス、見つからない場合は-1を返す)
int binarySearch(int arr[], int n, int target) {
    int left = 0;
    int right = n - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2; // 中央の要素

        if (arr[mid] == target) {
            return mid; // 見つかった
        }
        if (arr[mid] < target) {
            left = mid + 1; // 右半分を探す
        } else {
            right = mid - 1; // 左半分を探す
        }
    }
    return -1; // 見つからなかった
}

int main() {
    int data[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(data) / sizeof(data[0]);
    int target = 22;

    printf("--- バブルソート前 ---\n");
    for (int i = 0; i < n; i++) printf("%d ", data[i]);
    printf("\n");

    // 1. バブルソートを実行
    bubbleSort(data, n);

    printf("\n--- バブルソート後 ---\n");
    for (int i = 0; i < n; i++) printf("%d ", data[i]);
    printf("\n");

    // 2. 二分探索を実行
    int result = binarySearch(data, n, target);

    printf("\n--- 二分探索 ---\n");
    if (result != -1) {
        printf("値 %d はインデックス %d に見つかりました。\n", target, result);
    } else {
        printf("値 %d は見つかりませんでした。\n", target);
    }

    return 0;
}

実行結果：

--- バブルソート前 ---
64 34 25 12 22 11 90 

--- バブルソート後 ---
11 12 22 25 34 64 90 

--- 二分探索 ---
値 22 はインデックス 2 に見つかりました。