1. 配列の並び替えアルゴリズム

1.1 選択ソート —— 最小値を特定の位置に配置する

各ステップで未ソート部分から最小値（または最大値）を選び、それを対応する位置と交換することで、全体がソートされるまで処理を繰り返す。昇順での例を示す：

#include <stdio.h>

int main() {
    int data[] = {4, 8, 7, 6, 2, 5, 3, 9, 1};
    int length = sizeof(data) / sizeof(data[0]);
    
    for (int i = 0; i < length - 1; i++) {
        for (int j = i + 1; j < length; j++) {
            if (data[j] < data[i]) {
                int temp = data[i];
                data[i] = data[j];
                data[j] = temp;
            }
        }
    }
    
    for (int i = 0; i < length; i++) {
        printf("%d ", data[i]);
    }
    printf("\n");
    
    return 0;
}

このアルゴリズムでは、最初の要素を「優勝者」と見なし、他の要素と比較して最も小さな値を見つける。その後、その値を正しい位置に移動させる。

1.2 バブルソート —— 直接隣同士を比較し、順序を調整する

隣接する要素を比較し、順序が逆であれば入れ替える。このプロセスを繰り返すことで、最大値が配列の末尾に「浮かび」上がる。昇順での実装例は以下の通り：

#include <stdio.h>

int main() {
    int data[] = {4, 8, 7, 6, 2, 5, 3, 9, 1};
    int length = sizeof(data) / sizeof(data[0]);
    
    for (int i = 1; i < length; i++) {
        for (int j = 0; j < length - i; j++) {
            if (data[j] > data[j + 1]) {
                int temp = data[j];
                data[j] = data[j + 1];
                data[j + 1] = temp;
            }
        }
    }
    
    for (int i = 0; i < length; i++) {
        printf("%d ", data[i]);
    }
    printf("\n");
    
    return 0;
}

バブルソートは、水の中の泡が上に浮かぶように、データを順番に交換して最終的に昇順に整列させていく。

1.3 挿入ソート —— 既存の順序に適切な場所に挿入する

既にソートされた部分に新しい要素を挿入していく方法。各要素を適切な位置に挿入することで、全体をソートする。以下のように実装できる：

#include <stdio.h>

int main() {
    int data[] = {4, 8, 7, 6, 2, 5, 3, 9, 1};
    int length = sizeof(data) / sizeof(data[0]);
    
    for (int i = 1; i < length; i++) {
        int key = data[i];
        int j = i;
        
        while (j > 0 && data[j - 1] > key) {
            data[j] = data[j - 1];
            j--;
        }
        data[j] = key;
    }
    
    for (int i = 0; i < length; i++) {
        printf("%d ", data[i]);
    }
    printf("\n");
    
    return 0;
}

挿入ソートは、手元のトランプを整理するようなイメージ。既に整っているカード列に対して、新しいカードを適切な位置に挿入していく。

2. 検索アルゴリズム

2.1 二分探索 —— 探索範囲を半分に絞る

データが事前にソートされている必要がある。昇順の配列に対する二分探索の例を示す：

#include <stdio.h>

int binarySearch(int arr[], int size, int target) {
    int left = 0;
    int right = size - 1;
    
    while (left <= right) {
        int middle = (left + right) / 2;
        
        if (arr[middle] > target) {
            right = middle - 1;
        } else if (arr[middle] < target) {
            left = middle + 1;
        } else {
            return middle;
        }
    }
    return -1;
}

int main() {
    int data[] = {4, 8, 7, 6, 2, 5, 3, 9, 1};
    int length = sizeof(data) / sizeof(data[0]);
    
    // ソート
    for (int i = 1; i < length; i++) {
        int key = data[i];
        int j = i;
        while (j > 0 && data[j - 1] > key) {
            data[j] = data[j - 1];
            j--;
        }
        data[j] = key;
    }
    
    int searchValue;
    printf("検索する値を入力: ");
    scanf("%d", &searchValue);
    
    int result = binarySearch(data, length, searchValue);
    
    if (result != -1)
        printf("発見しました！\n");
    else
        printf("見つかりません。\n");
        
    return 0;
}

二分探索では、探索範囲を半分ずつに狭めていき、目的の値を効率よく見つける。配列の中央要素と比較し、探索範囲を左または右に移動する。