【基本情報技術者試験】バブルソート問題をC言語のコードで確認してみよう！

以前、「C言語のきほん『バブルソート』」で、身長データを昇順に並べ替える実装を解説した。この記事は「バブルソートをC言語でどう書くか」に焦点を当てたものだったが、今回は少し角度を変えて、基本情報技術者試験のアルゴリズムで問われる「トレース問題」を解けるようになることを目的にした。

基本情報技術者試験では擬似言語（試験独自の記法）でアルゴリズムが出題され、「変数〇〇に入る値を答えよ」「ループを〇回通過した時点の配列の状態を答えよ」といった穴埋め・トレース問題が頻出である。つまり、コードを書けることよりも、コードを1行ずつ目で追って、変数や配列がどう変化していくかを正確に把握する力が問われる。

そこで今回は、C言語のコードを使いながら、あえて「パスごとの状態変化」を細かく確認していく構成にした。実装方法そのものの基礎は前回の記事で扱っているので、そちらもあわせてご覧いただきたい。

今回使うコード（バブルソート）

#include <stdio.h>

#define SIZE 6

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

void bubble_sort(int arr[], int size) {
    for (int i = 0; i < size - 1; i++) {
        int swapped = 0; /* このパスで1回でも交換が起きたかを記録するフラグ */

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

        printf("%d回目のパス後: ", i + 1);
        print_array(arr, size);

        if (swapped == 0) {
            break; /* 交換が起きなければ整列完了とみなして打ち切る */
        }
    }
}

int main(void) {
    int data[SIZE] = {5, 2, 8, 1, 9, 3};

    printf("ソート前: ");
    print_array(data, SIZE);

    bubble_sort(data, SIZE);

    printf("ソート後: ");
    print_array(data, SIZE);

    return 0;
}

実行結果

ソート前: 5 2 8 1 9 3 
1回目のパス後: 2 5 1 8 3 9 
2回目のパス後: 2 1 5 3 8 9 
3回目のパス後: 1 2 3 5 8 9 
4回目のパス後: 1 2 3 5 8 9 
ソート後: 1 2 3 5 8 9 

前回の記事とほぼ同じ骨格だが、試験対策として重要な swapped フラグ（無駄なパスを打ち切る改善）を今回は主役として扱う。

【トレースしてみよう】パスごとに何が起きているか

試験本番のつもりで、配列 {5, 2, 8, 1, 9, 3} が1回のパスでどう変化するか、i = 0（1回目のパス）を手を動かして追ってみよう。

1回目のパスが終わった時点で、末尾の 9 が確定する。
これをそのまま i = 1, 2, 3, 4 と続けていくと、以下のように整列が進む。

ソート前:        5 2 8 1 9 3
1回目のパス後:   2 5 1 8 3 9
2回目のパス後:   2 1 5 3 8 9
3回目のパス後:   1 2 3 5 8 9
4回目のパス後:   1 2 3 5 8 9（交換が1回も発生しない）

ここがトレース問題を解くときの一番のポイントである。4回目のパスで交換が1回も起きていないため、swapped は0のままとなり、5回目のパスに入らずに break で処理を打ち切る。試験問題では、この「早期終了の条件」を問う設問がよく出題される。

試験問題を解くときの読み方のコツ

1. 外側ループが「確定させる回数」、内側ループが「その回で比較する範囲」を表していることをまず押さえる
2. 内側ループの範囲が size - 1 - i のように、外側ループが進むほど狭くなっている場合は、「末尾側から確定していくタイプのバブルソート」だと判断できる
3. swapped のようなフラグ変数が出てきたら、「もう整列済みかどうかを判定する仕組みが入っている」と読み取り、それがどの時点でループを打ち切らせるのかを追う
4. 穴埋め問題では、まず「この変数は何を数えているのか」「このフラグはどんな条件でオンになるのか」を日本語で言い換えてから空欄を埋めると、ケアレスミスが減る

計算量の確認（頻出ポイント）

配列サイズを n とすると、比較回数は最大で

(n-1) + (n-2) + ... + 1 = n(n-1)/2

となり、オーダー記法では O(n²) である。試験では、バブルソート・選択ソート・挿入ソート・クイックソートなど複数のアルゴリズムの計算量を比較させる問題も頻出なので、余力があれば他のソートとの違いも押さえておくと得点源になる。

まとめ

• 実装方法そのものは、C言語のきほん「バブルソート」で解説済みなので、今回はトレースの読み方に絞って解説した。
• 試験対策としては、「外側・内側ループが何を意味するか」「フラグ変数がどんな条件で処理を打ち切らせるか」を説明できる状態を目指すのが目標である。
• 計算量O(n²)という弱点も、他のソートと比較して問われやすいポイントである。

次回は、同じくアルゴリズム問題の定番である「線形探索と二分探索」を取り上げ、探索の効率の違いをトレース問題形式で確認していく。

この記事で扱ったコードは、GitHubの c-language-studies リポジトリ
（FE-algorithm/01_bubble_sort/c/）で公開している。今後、同じアルゴリズムをGo/Kotlinに移植した比較記事も予定しているので、興味のある方は、このリポジトリもチェックしていただきたい。