C言語基礎｜バブルソートの仕組み
「となり同士を比べるだけ！バブルソートの“動き”が見えると、ソートが一気に身近になる」
バブルソートってどんなソート？
ソートは、データを小さい順（昇順）や大きい順（降順）に並べ替えることでしたね。
その中でも バブルソート は、とても素朴で覚えやすい方法です。
やることはシンプルで、
- となり同士を比べる
- 順番が逆なら交換する
- これを何度も繰り返す
これだけで、最終的に全体が整列します。
名前の由来は、交換を繰り返すうちに「正しい位置に値が泡（bubble）のように移動していく」イメージからです。
このページでは、元の「身長5人」ではなく、もっとシンプルに 5個の点数 を昇順に並べ替える例に変えて、
バブルソートがどの順番で比較・交換していくのかを、表と図で丁寧に追いかけます。
サンプルプログラム
「5個の点数を入力して、昇順にソートして表示する」プログラムです。
プロジェクト名：chap8-5-1 ソースファイル名：chap8-5-1.c
Visual Studio でこのプログラムを実行するには、SDLチェック設定を変更しておく必要があります。
１．プロジェクト名を右クリックして、「プロパティ」をクリックします。
２．「C/C++」→「全般」→「SDLチェック」を「いいえ」に切り替えて「OK」をクリックします。
#include <stdio.h>
#define COUNT 5
//--- バブルソート（昇順） ---//
void bsort(int a[], int n)
{
for (int i = 0; i < n - 1; i++) { // パスは n-1 回
for (int j = n - 1; j > i; j--) { // 末尾から先頭へ走査
if (a[j - 1] > a[j]) { // 左が大きければ交換
int tmp = a[j];
a[j] = a[j - 1];
a[j - 1] = tmp;
}
}
}
}
int main(void)
{
int score[COUNT];
printf("%d個の点数を入力してください。\n", COUNT);
for (int i = 0; i < COUNT; i++) {
printf("%d番目：", i + 1);
scanf("%d", &score[i]);
}
bsort(score, COUNT);
puts("小さい順に並べました。");
for (int i = 0; i < COUNT; i++) {
printf("%d番目：%d\n", i + 1, score[i]);
}
return 0;
}実行例
5個の点数を入力してください。
1番目：72
2番目：55
3番目：90
4番目：60
5番目：78
小さい順に並べました。
1番目：55
2番目：60
3番目：72
4番目：78
5番目：90まず用語を整理：ソート・昇順・降順
用語
| 用語 | 意味 | 例 |
|---|---|---|
| ソート | 並べ替え | 点数を順番に並べる |
| 昇順 | 小さい→大きい | 55, 60, 72, 78, 90 |
| 降順 | 大きい→小さい | 90, 78, 72, 60, 55 |
バブルソートの中身：パスとは何か
バブルソートは「パス」と呼ばれる作業を繰り返します。
1回のパスでは、配列の中を一定の方向に走査して、となり同士を比較し、必要なら交換します。
このサンプルでは 末尾から先頭へ走査 しています。
パスのイメージ（末尾→先頭）
末尾側から (a[j-1], a[j]) を順に比較
必要なら入れ替える
1パス終わると、先頭側に小さい値が集まってくる
手で追ってみよう：実際の比較・交換の流れ
例として、入力が次の5個だったとします。
72 55 90 60 78
1パス目（i = 0）：末尾から先頭へ
比較するペアは右から順に
(60, 78) → (90, 60) → (55, 90) → (72, 55)
1パス目の変化
| 比較する位置 | 比較 | 交換？ | 配列の状態 |
|---|---|---|---|
| (3,4) | 60 と 78 | しない | 72 55 90 60 78 |
| (2,3) | 90 と 60 | する | 72 55 60 90 78 |
| (1,2) | 55 と 60 | しない | 72 55 60 90 78 |
| (0,1) | 72 と 55 | する | 55 72 60 90 78 |
表の説明
末尾から見ていき、逆順のペアだけ交換します。
1パスが終わった時点で、最小の 55 が先頭に移動しました。ここがバブルソートらしい動きです。
2パス目（i = 1）：先頭1個はもう確定
2パス目では、先頭の 55 はもう動かさない前提になります。
つまり「未ソート部分」は index 1〜4 です。
ソート済み領域と未ソート領域
↓ここを並べる
________________
55 | 72 60 90 78
↑ここは確定
2パス目の変化
開始状態
55 72 60 90 78
| 比較する位置 | 比較 | 交換？ | 配列の状態 |
|---|---|---|---|
| (3,4) | 90 と 78 | する | 55 72 60 78 90 |
| (2,3) | 60 と 78 | しない | 55 72 60 78 90 |
| (1,2) | 72 と 60 | する | 55 60 72 78 90 |
2パス目が終わると、先頭2個（55, 60）が確定します。
3パス目（i = 2）と 4パス目（i = 3）
3パス目：未ソートは index 2〜4
4パス目：未ソートは index 3〜4
と、だんだん比較範囲が狭くなります。
完成までのイメージ
1パス目：最小が先頭へ
2パス目：2番目に小さい値が2番目へ
3パス目：3番目が3番目へ
4パス目：残り2つを整えて完了
ポイント
要素数が n のとき、必要なパスは n-1 回です。
今回なら 5個なので 4回パスを行えば並び替えが完了します。
コードで理解：2重ループが何をしているか
ループ変数 i と j の役割
| 変数 | 何を表す？ | どんな動き？ |
|---|---|---|
| i | 何パス目か | 0 → 1 → 2 → … と増える。 |
| j | そのパスで走査する位置 | 末尾(n-1) から i+1 まで減る。 |
表の説明
- 外側 for（i）：パスの回数を担当
- 内側 for（j）：そのパスでの比較・交換を担当
- j > i になっているのは、「先頭 i 個は確定だから、そこまでは踏み込まない」という意味です
交換処理（swap）の仕組み
交換は一時変数 tmp を使って行います。
交換のイメージ
tmp に右を退避
右に左を入れる
左に tmp を戻す
交換の3手順
| 手順 | 代入 | 意味 |
|---|---|---|
| 1 | tmp = a[j] | a[j] を一時退避 |
| 2 | a[j] = a[j-1] | 左の値を右へ移動 |
| 3 | a[j-1] = tmp | 退避した値を左へ |
計算量の話（ざっくりでOK）
バブルソートは分かりやすい代わりに、データが多いと遅くなりがちです。
バブルソートの特徴
| 観点 | 内容 |
|---|---|
| 比較回数 | だいたい n(n-1)/2 回 |
| 速さの傾向 | 大きな n では遅め |
| 良い点 | 実装が簡単、動きが追いやすい |
| 注意点 | 交換が多いと時間がかかる |
登場する命令・構文の書式と役割まとめ
#define の書式
#define 名前 値
何をする？
定数のように使える名前を作ります。今回は COUNT を 5 にしています。
配列の宣言
int score[COUNT];
何をする？
int を COUNT 個まとめて持てる箱を用意します。
関数の宣言（配列を受け取る）
void bsort(int a[], int n)
何をする？
配列 a を、要素数 n として受け取り、a の中身を並べ替えます。
配列は渡すときに「中身全部をコピー」ではなく「同じ配列を操作する形」になりやすいので、関数の中で並べ替えた結果が main 側にも反映されます。
for 文の書式
for (初期化; 条件; 更新) { ... }
何をする？
決まった回数や条件で繰り返します。
外側 for はパス回数、内側 for は比較・交換の走査担当でした。
if 文の書式
if (条件) { ... }
何をする？
条件が真のときだけ処理します。今回は a[j - 1] > a[j] のときに交換します。
printf / scanf / puts の書式
- printf：表示（書式付き）
- scanf：入力（変数のアドレスに格納）
- puts：文字列を表示して改行
まとめ：バブルソートの“仕組み”はここだけ押さえればOK
- となり同士を比べて、逆なら交換
- 1パス終わると、先頭側に小さい値が集まり、確定していく
- n 個ならパスは n-1 回
- コードは 2重ループで表せる（外側＝パス、内側＝比較と交換）