EnglishEnglish العربيةالعربية PortuguêsPortuguês 日本語日本語

練習：配列と関数の総合

いくつ技術を学んでも、リングに上がらなければ理論にすぎません。この章では4つのハンズオンプロジェクトを通じて配列、関数、ポインタを統合し、本当の腕を試します。

プロジェクト1：バブルソート

バブルソートは最も基本的なソートアルゴリズムです。配列を繰り返し走査し、隣接要素を比較して順序が逆なら入れ替える、という操作を交換が起きなくなるまで続けます。各パスで現在の最大値が末尾に「泡のように浮かび上がる」ことからこの名前があります。

アルゴリズムの手順

  1. 最初の要素から始め、隣接要素の各ペアを比較する
  2. 左の要素が右より大きければ、入れ替える
  3. 1パス終えると、最大値が正しい位置に来る
  4. 残りの部分について繰り返す。完全にソートされるまで続ける

実装

C 
#include <stdio.h>

void bubble_sort(int *arr, int len) {
    int i, j;
    int swapped;

    for (i = 0; i < len - 1; i++) {
        swapped = 0;
        for (j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = 1;
            }
        }
        if (!swapped) break;
    }
}

void print_array(const int *arr, int len) {
    int i;
    for (i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

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

    printf("Before: ");
    print_array(data, len);

    bubble_sort(data, len);

    printf("After:  ");
    print_array(data, len);

    return 0;
}
TEXT 
Before: 64 34 25 12 22 11 90
After:  11 12 22 25 34 64 90

swappedフラグの最適化：1パスで交換が起きなければ、配列はすでにソート済みであり、アルゴリズムは早期に終了します。最良ケース（すでにソート済み）では時間計算量がO(n)に低下します。

💡 ヒント： バブルソートの平均・最悪ケースの時間計算量はO(n^2)で、小さなデータセットや教育目的にのみ適しています。実際のプロジェクトではqsortを使ってください。

例

バブルソートで成績を降順にソートします。

C 
#include <stdio.h>

void sort_desc(int *arr, int len) {
    int i, j, swapped;
    for (i = 0; i < len - 1; i++) {
        swapped = 0;
        for (j = 0; j < len - 1 - i; j++) {
            if (arr[j] < arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = 1;
            }
        }
        if (!swapped) break;
    }
}

int main(void) {
    int scores[] = {85, 92, 78, 95, 88};
    int len = sizeof(scores) / sizeof(scores[0]);
    int i;

    sort_desc(scores, len);
    printf("Ranking: ");
    for (i = 0; i < len; i++) {
        printf("%d ", scores[i]);
    }
    printf("\n");
    return 0;
}
▶ 試してみよう
TEXT 
Ranking: 95 92 88 85 78

降順にするには、比較を>から<に変えるだけです。

プロジェクト2：二分探索

二分探索はソート済み配列内で目標値を効率的に見つけます。各ステップで探索範囲を半分に絞ります。

アルゴリズムの手順

  1. 探索範囲を[low, high]に設定する
  2. 中央位置を計算：mid = (low + high) / 2
  3. arr[mid]が目標と等しければ発見
  4. arr[mid]が目標より小さければ、右半分を探索
  5. arr[mid]が目標より大きければ、左半分を探索
  6. 範囲が空になっても見つからなければ、目標は存在しない

実装

C 
#include <stdio.h>

int binary_search(const int *arr, int len, int target) {
    int low = 0;
    int high = len - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    return -1;
}

int main(void) {
    int data[] = {2, 5, 8, 12, 16, 23, 38, 45, 56, 78};
    int len = sizeof(data) / sizeof(data[0]);
    int targets[] = {23, 7, 78, 1};
    int num = sizeof(targets) / sizeof(targets[0]);
    int i;

    for (i = 0; i < num; i++) {
        int pos = binary_search(data, len, targets[i]);
        if (pos >= 0) {
            printf("%d found at index %d\n", targets[i], pos);
        } else {
            printf("%d not found\n", targets[i]);
        }
    }
    return 0;
}
TEXT 
23 found at index 5
7 not found
78 found at index 9
1 not found
💡 ヒント： (low + high) / 2の代わりにlow + (high - low) / 2を使ってください。整数オーバーフローを防げます。これは二分探索の古典的なディテールです。

時間計算量はO(log n)です。10億要素でも最大30回の比較で済みます。

例

目標以上の最初の要素の位置を見つける（下限探索）。

C 
#include <stdio.h>

int lower_bound(const int *arr, int len, int target) {
    int low = 0;
    int high = len;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
}

int main(void) {
    int data[] = {1, 3, 3, 5, 7, 7, 7, 9, 11};
    int len = sizeof(data) / sizeof(data[0]);
    int pos = lower_bound(data, len, 7);
    printf("First >= 7 at index %d, value=%d\n", pos, data[pos]);
    return 0;
}
▶ 試してみよう
TEXT 
First >= 7 at index 4, value=7

下限探索は競技プログラミングやSTLで非常に一般的です。

プロジェクト3：文字列の反転

文字列の前後の文字を入れ替えます。例えば"hello"は"olleh"になります。双ポインタテクニックでインプレース操作でき、追加の配列は不要です。

実装

C 
#include <stdio.h>
#include <string.h>

void str_reverse(char *s) {
    char *left = s;
    char *right = s + strlen(s) - 1;

    while (left < right) {
        char temp = *left;
        *left = *right;
        *right = temp;
        left++;
        right--;
    }
}

int main(void) {
    char s1[] = "Hello World";
    char s2[] = "ABCDE";
    char s3[] = "racecar";

    str_reverse(s1);
    str_reverse(s2);
    str_reverse(s3);

    printf("%s\n", s1);
    printf("%s\n", s2);
    printf("%s\n", s3);

    return 0;
}
TEXT 
dlroW olleH
EDCBA
racecar

注意：文字列リテラルへのポインタではなく、文字配列（変更可能）を使う必要があります。

例

文字列が回文かどうかを判定します（英数字以外をスキップし、大文字小文字を無視）。

C 
#include <stdio.h>
#include <string.h>
#include <ctype.h>

int is_palindrome(const char *s) {
    const char *left = s;
    const char *right = s + strlen(s) - 1;
    while (left < right) {
        while (left < right && !isalnum((unsigned char)*left)) left++;
        while (left < right && !isalnum((unsigned char)*right)) right--;
        if (tolower((unsigned char)*left) != tolower((unsigned char)*right)) {
            return 0;
        }
        left++;
        right--;
    }
    return 1;
}

int main(void) {
    printf("%d\n", is_palindrome("racecar"));
    printf("%d\n", is_palindrome("hello"));
    printf("%d\n", is_palindrome("A man a plan a canal Panama"));
    return 0;
}
▶ 試してみよう
TEXT 
1
0
1

プロジェクト4：文字頻度分析

文字列中で各文字が何回出現するかを数えます。基本的なテキスト分析操作です。

実装

C 
#include <stdio.h>
#include <string.h>

void char_freq(const char *s, int *freq, int size) {
    int i;
    for (i = 0; i < size; i++) freq[i] = 0;
    while (*s != '\0') {
        unsigned char ch = (unsigned char)*s;
        if (ch < (unsigned)size) freq[ch]++;
        s++;
    }
}

int main(void) {
    char text[] = "Hello World!";
    int freq[256] = {0};
    int i;

    char_freq(text, freq, 256);

    for (i = 32; i < 127; i++) {
        if (freq[i] > 0) printf("'%c': %d  ", i, freq[i]);
    }
    printf("\n");
    return 0;
}
TEXT 
' ': 1  '!': 1  'H': 1  'W': 1  'd': 1  'e': 1  'l': 3  'o': 2  'r': 1

ASCII値を配列の添字として使い、1パスでカウントが完了します。256スロットですべての8ビット文字をカバーします。

例

文字の出現頻度を数え、最も頻出な文字を見つけます。

C 
#include <stdio.h>
#include <ctype.h>
#include <string.h>

void letter_freq(const char *s, int *freq) {
    int i;
    for (i = 0; i < 26; i++) freq[i] = 0;
    while (*s != '\0') {
        if (isalpha((unsigned char)*s)) {
            freq[tolower((unsigned char)*s) - 'a']++;
        }
        s++;
    }
}

char find_max(const int *freq, int size) {
    int max_idx = 0;
    int i;
    for (i = 1; i < size; i++) {
        if (freq[i] > freq[max_idx]) max_idx = i;
    }
    return 'a' + max_idx;
}

int main(void) {
    const char *text = "The quick brown fox jumps over the lazy dog";
    int freq[26];
    letter_freq(text, freq);
    char max_ch = find_max(freq, 26);
    printf("Most frequent letter: %c (%d times)\n", max_ch, freq[max_ch - 'a']);
    return 0;
}
▶ 試してみよう
TEXT 
Most frequent letter: o (4 times)

❓ よくある質問

Q バブルソートと選択ソートはどちらが良いですか？
A どちらも時間計算量はO(n^2)ですが、バブルソートには早期終了の最適化があり、最良ケースがO(n)です。実用上の差は小さく、どちらも大きなデータセットには不向きです。
Q 二分探索の前提条件は何ですか？
A 配列がソート済みであり、ランダムアクセスをサポートしている必要があります。連結リストでは中央要素にO(1)でアクセスできないため、二分探索は使えません。
Q 文字列反転のライブラリ関数はありますか？
A C標準ライブラリには直接的な反転関数はありません。C++には<algorithm>のstd::reverseがありますが、Cでは自分で実装する必要があります。
Q 頻度カウントに256要素の配列を使うのはなぜですか？
A unsigned charは0〜255の範囲で、合計256値です。文字のASCII値を添字として使えば、256スロットですべての可能な文字をカバーでき、1パスでカウントが完了します。

📖 まとめ

📝 練習問題

  1. バブルソートを拡張し、関数ポインタの仮引数で昇順・降順を制御できるソート関数を実装してください。
  2. 二分探索の再帰版int bin_search_rec(const int *arr, int low, int high, int target)を実装してください。
  3. 拡張文字頻度アナライザを書いてください。ユーザー入力1行を読み取り、出現頻度上位3文字とその回数を出力します。
100%