【C言語】初心者向けバブルソートの解説とコード例

By /

はい、承知いたしました。C言語初心者向けに、バブルソートの詳細な解説とコード例を含む約5000語の記事を作成します。

【C言語】初心者向け バブルソート徹底解説：原理からコード、最適化まで

はじめに：ソートとは何か、なぜ学ぶのか

プログラミングの世界では、様々なデータを扱います。そのデータが、例えば数値であれば小さい順に並べたり、大きい順に並べたり、文字列であれば辞書順に並べたりしたい場面は非常に多くあります。このように、データを特定の基準（順序）に従って並べ替える操作を ソート（Sort） と呼びます。

ソートされたデータは、格段に扱いやすくなります。例えば、特定のデータを探す際に、ソートされていれば非常に効率的に検索することができます（二分探索など）。データベースで情報を整理したり、統計処理を行う際にもソートは欠かせない前処理です。

ソートのアルゴリズムは数多く存在します。それぞれに得意な状況や効率の違いがあります。プログラミング学習において、これらのソートアルゴリズムを理解することは、計算機科学の基本的な考え方や、効率的なプログラムの設計方法を学ぶ上で非常に重要です。

この記事では、数あるソートアルゴリズムの中でも、最もシンプルで理解しやすいとされている バブルソート（Bubble Sort） をC言語を使いながら、その原理から実装方法、そして少しの改善点まで、初心者の方にも徹底的に分かりやすく解説していきます。バブルソートは実用的にはあまり使われませんが、その単純さゆえにアルゴリズム学習の第一歩として非常に適しています。

さあ、一緒にバブルソートの世界に入り込みましょう！

第1章：ソートとは何か？ データ整理の基本

もう一度、ソートの定義を確認しましょう。
ソート とは、データの集まり（リストや配列など）を、ある特定の順序（昇順、降順など）に従って並べ替えることです。

例として、以下のような整数の配列があるとします。
[ 5, 2, 8, 1, 9, 4 ]

これを昇順（小さい順）にソートすると、以下のようになります。
[ 1, 2, 4, 5, 8, 9 ]

また、降順（大きい順）にソートすると、以下のようになります。
[ 9, 8, 5, 4, 2, 1 ]

ソートが必要となる典型的な場面は以下の通りです。

  • データの表示: 成績順、売上順、新着順など、ユーザーが見やすいように情報を整理して表示する場合。
  • 検索の高速化: ソート済みのデータに対しては、非ソートのデータよりもはるかに高速な検索アルゴリズム（例: 二分探索）を適用できます。
  • データ処理: 統計処理で中央値を求めたり、重複データを探したりする場合など、前もってソートしておくと処理が容易になることがあります。

世の中には、バブルソート以外にも様々なソートアルゴリズムがあります。代表的なものだけでも、選択ソート、挿入ソート、マージソート、クイックソート、ヒープソート、シェルソートなど、枚挙にいとまがありません。それぞれのアルゴリズムは、データの量、データの初期状態、使用できるメモリ容量などの条件によって、得意不得意があります。

この記事で学ぶバブルソートは、これらのアルゴリズムの中で最もシンプルですが、一般的には効率が悪いとされています。しかし、そのシンプルさゆえに、ソートアルゴリズムの基本的な考え方を学ぶのに最適なのです。

第2章：バブルソートの基本原理 – 隣と比べて、入れ替える

バブルソートは、その名前の通り、軽い要素が水中で泡（バブル）のように水面に浮き上がってくる様子に例えられます。昇順ソートの場合、小さい値が配列の先頭の方へ、大きい値が配列の後ろの方へ移動していくイメージです。

では、具体的にどのように動くのでしょうか？ バブルソートの基本原理は以下のたった二つの操作だけです。

  1. 隣り合う要素を比較する。
  2. もし順序が逆であれば、それらを交換（スワップ）する。

この操作を、配列の先頭から末尾にかけて繰り返し行います。一度配列の最後までこの操作を行うと、そのパス（一回の走査）の中で最も大きい要素が配列の最後の位置に確定します。なぜなら、その最大の要素は比較されるたびに必ず相手より大きく、交換を繰り返すことで自然と末尾へと移動していくからです。まるで一番重い玉が一番下に沈むように、あるいは一番軽い泡が一番上に浮かぶように、特定の要素が端に移動します。

例えば、昇順にソートする場合を考えます。配列 [5, 2, 8, 1] があったとします。

  1. 先頭から順に隣り合う要素を比較します。
  2. まず 5 と 2 を比較します。5 は 2 より大きいので、順序が逆です。交換します。
    配列は [2, 5, 8, 1] となります。
  3. 次に 5 と 8 を比較します。5 は 8 より大きくないので、順序は正しいです。交換はしません。
    配列は [2, 5, 8, 1] のままです。
  4. 次に 8 と 1 を比較します。8 は 1 より大きいので、順序が逆です。交換します。
    配列は [2, 5, 1, 8] となります。

これで配列の最後まで比較・交換が終わりました。この一連の操作を 1回のパス と呼びます。1回のパスが終わった時点で、最も大きい要素である 8 が配列の末尾（最後の位置）に移動し、そこに確定しました。つまり、次のパスからは最後の要素を比較対象から外すことができます。

この「隣接要素の比較と交換」というパスを、配列の要素が全て確定してソートが完了するまで繰り返します。

第3章：バブルソートのアルゴリズム詳細 – 手作業シミュレーション

具体的な配列を使って、バブルソートの動きをさらに詳しく見ていきましょう。
例として、サイズ6の整数の配列 [ 5, 2, 8, 1, 9, 4 ] を昇順にソートします。

最初の状態:
[ 5, 2, 8, 1, 9, 4 ]

1回目のパス:
隣接する要素を比較し、必要なら交換します。比較するペアは (5, 2), (2, 8), (8, 1), (1, 9), (9, 4) の順です。

  1. (5, 2) を比較：5 > 2 なので交換。 -> [ 2, 5, 8, 1, 9, 4 ]
  2. (5, 8) を比較：5 < 8 なので交換なし。 -> [ 2, 5, 8, 1, 9, 4 ]
  3. (8, 1) を比較：8 > 1 なので交換。 -> [ 2, 5, 1, 8, 9, 4 ]
  4. (8, 9) を比較：8 < 9 なので交換なし。 -> [ 2, 5, 1, 8, 9, 4 ]
  5. (9, 4) を比較：9 > 4 なので交換。 -> [ 2, 5, 1, 8, 4, 9 ]

1回目のパスが終了しました。配列の末尾に最も大きい要素 9 が確定しました。
現在の状態: [ 2, 5, 1, 8, 4, 9 ] （最後の 9 は確定）

2回目のパス:
今度は、最後の要素 (9) を除く、配列の先頭から5番目の要素までを対象に比較・交換を行います。比較するペアは (2, 5), (5, 1), (1, 8), (8, 4) の順です。対象範囲は [ 2, 5, 1, 8, 4 ] までです。

  1. (2, 5) を比較：2 < 5 なので交換なし。 -> [ 2, 5, 1, 8, 4, 9 ]
  2. (5, 1) を比較：5 > 1 なので交換。 -> [ 2, 1, 5, 8, 4, 9 ]
  3. (5, 8) を比較：5 < 8 なので交換なし。 -> [ 2, 1, 5, 8, 4, 9 ]
  4. (8, 4) を比較：8 > 4 なので交換。 -> [ 2, 1, 5, 4, 8, 9 ]

2回目のパスが終了しました。対象範囲 ([2, 1, 5, 4, 8]) の中で最も大きい要素 8 が、その対象範囲の末尾（配列全体としては末尾から2番目）に確定しました。
現在の状態: [ 2, 1, 5, 4, 8, 9 ] （最後の 8 と 9 は確定）

3回目のパス:
次は、末尾から2つの要素 (8, 9) を除く、配列の先頭から4番目の要素までを対象に比較・交換を行います。比較するペアは (2, 1), (1, 5), (5, 4) の順です。対象範囲は [ 2, 1, 5, 4 ] までです。

  1. (2, 1) を比較：2 > 1 なので交換。 -> [ 1, 2, 5, 4, 8, 9 ]
  2. (2, 5) を比較：2 < 5 なので交換なし。 -> [ 1, 2, 5, 4, 8, 9 ]
  3. (5, 4) を比較：5 > 4 なので交換。 -> [ 1, 2, 4, 5, 8, 9 ]

3回目のパスが終了しました。対象範囲 ([1, 2, 5, 4]) の中で最も大きい要素 5 が、その対象範囲の末尾（配列全体としては末尾から3番目）に確定しました。
現在の状態: [ 1, 2, 4, 5, 8, 9 ] （最後の 5, 8, 9 は確定）

4回目のパス:
次は、末尾から3つの要素 (5, 8, 9) を除く、配列の先頭から3番目の要素までを対象に比較・交換を行います。比較するペアは (1, 2), (2, 4) の順です。対象範囲は [ 1, 2, 4 ] までです。

  1. (1, 2) を比較：1 < 2 なので交換なし。 -> [ 1, 2, 4, 5, 8, 9 ]
  2. (2, 4) を比較：2 < 4 なので交換なし。 -> [ 1, 2, 4, 5, 8, 9 ]

4回目のパスが終了しました。対象範囲 ([1, 2, 4]) の中で最も大きい要素 4 が、その対象範囲の末尾（配列全体としては末尾から4番目）に確定しました。
現在の状態: [ 1, 2, 4, 5, 8, 9 ] （最後の 4, 5, 8, 9 は確定）

5回目のパス:
次は、末尾から4つの要素 (4, 5, 8, 9) を除く、配列の先頭から2番目の要素までを対象に比較・交換を行います。比較するペアは (1, 2) のみです。対象範囲は [ 1, 2 ] までです。

  1. (1, 2) を比較：1 < 2 なので交換なし。 -> [ 1, 2, 4, 5, 8, 9 ]

5回目のパスが終了しました。対象範囲 ([1, 2]) の中で最も大きい要素 2 が、その対象範囲の末尾（配列全体としては末尾から5番目）に確定しました。
現在の状態: [ 1, 2, 4, 5, 8, 9 ] （最後の 2, 4, 5, 8, 9 は確定）

配列のサイズが6だったので、5回目のパスまで行うと、先頭の要素 (1) も自動的に確定します。つまり、サイズがNの配列の場合、通常N-1回のパスを行えばソートが完了します。

最終的な状態: [ 1, 2, 4, 5, 8, 9 ]
これでソートが完了しました。

この手作業シミュレーションから、バブルソートの重要な性質が分かります。

  • 1回のパスで、未ソート部分の最も大きな要素が末尾に移動し確定する。
  • パスが進むごとに、ソート対象となる範囲が一つずつ狭まる。

この動きをC言語のコードで表現することを次に考えます。

第4章：C言語でのバブルソート実装 – 基本コード

それでは、先ほどのアルゴリズムをC言語で実装してみましょう。まずは最も基本的な形です。

“`c

include // 標準入出力ライブラリを使用するためのヘッダーファイル

// 配列の内容を表示する関数
void displayArray(int arr[], int size) {
printf(“[“);
for (int i = 0; i < size; i++) {
printf(“%d”, arr[i]);
if (i < size – 1) {
printf(“, “);
}
}
printf(“]\n”);
}

// バブルソートを実行する関数（昇順）
void bubbleSort(int arr[], int size) {
// 外側のループ: パスの回数を制御
// サイズがsizeの配列は、size-1回のパスでソートが完了する
for (int i = 0; i < size – 1; i++) {
// 内側のループ: 隣接要素の比較と交換
// 各パスで末尾からi個の要素は確定済みなので、比較対象から除く
for (int j = 0; j < size – 1 – i; j++) {
// 隣り合う要素 arr[j] と arr[j+1] を比較
// 昇順なので、もし arr[j] が arr[j+1] より大きければ順序が逆
if (arr[j] > arr[j+1]) {
// 要素を交換 (スワップ)
int temp = arr[j]; // arr[j] の値を一時変数に保存
arr[j] = arr[j+1]; // arr[j+1] の値を arr[j] に代入
arr[j+1] = temp; // 一時変数に保存しておいた元の arr[j] の値を arr[j+1] に代入
}
}
// (オプション) 各パス終了後の配列の状態を表示してみる
// printf(“Pass %d: “, i + 1);
// displayArray(arr, size);
}
}

int main() {
// ソートしたい整数の配列を準備
int myArray[] = {5, 2, 8, 1, 9, 4};
// 配列の要素数を計算
// sizeof(myArray) で配列全体のバイト数
// sizeof(myArray[0]) で要素一つあたりのバイト数
// これらを割ることで要素数が求まる
int arraySize = sizeof(myArray) / sizeof(myArray[0]);

printf("--- バブルソート (昇順) ---\n");

// ソート前の配列を表示
printf("ソート前: ");
displayArray(myArray, arraySize);

// バブルソートを実行
bubbleSort(myArray, arraySize);

// ソート後の配列を表示
printf("ソート後: ");
displayArray(myArray, arraySize);

printf("-------------------------\n");

return 0; // プログラム正常終了

}
“`

このコードをコンパイルして実行すると、以下のような出力が得られるはずです。

“`
— バブルソート (昇順) —
ソート前: [5, 2, 8, 1, 9, 4]
ソート後: [1, 2, 4, 5, 8, 9]

“`

期待通りの結果となりました。次に、このコードの各部分を詳しく見ていきましょう。

第5章：C言語コード徹底解説 – 各行の意味を理解する

先ほどのコードを一つずつ丁寧に解説していきます。

#include <stdio.h>

これは プリプロセッサディレクティブ と呼ばれるもので、コンパイルが始まる前に処理されます。#include は、指定されたヘッダーファイルの内容を、その #include が書かれた場所に読み込む指示です。
<stdio.h> は Standard Input/Output Header の略で、標準入出力に関する関数（例えば printf や scanf など）の宣言が含まれています。今回は配列の内容を表示するために printf 関数を使うため、このヘッダーファイルが必要です。

displayArray 関数

c
void displayArray(int arr[], int size) {
printf("["); // 配列の始まりを示す '[' を表示
for (int i = 0; i < size; i++) { // 配列の先頭から末尾までループ
printf("%d", arr[i]); // 現在の要素の値を表示
if (i < size - 1) { // 最後の要素以外の場合
printf(", "); // 要素の区切りとして ", " を表示
}
}
printf("]\n"); // 配列の終わりを示す ']' と改行を表示
}
この関数は、与えられた整数の配列 arr の内容を、引数 size で指定された要素数だけ、[要素1, 要素2, ...] の形式で整形して標準出力に表示するためのユーティリティです。
* void: この関数は何も値を返しません。
* int arr[]: 配列を受け取るためのパラメータです。C言語では、配列を関数に渡す際、実際には配列の先頭要素へのポインタと解釈されます。ここでは arr[] と書いても、実質的には int *arr と同じ意味になります（ただし、関数内で sizeof(arr) としても配列全体のサイズは取得できません。なので別途 size を渡す必要があります）。
* int size: 配列の要素数を渡します。これはループの範囲を指定するために必要です。
* for (int i = 0; i < size; i++): 配列の添え字は0から始まるため、i を0から size-1 まで変化させながらループを回します。
* printf("%d", arr[i]);: 現在の添え字 i の要素 arr[i] を10進数として表示します。
* if (i < size - 1): 最後の要素（添え字が size-1 の要素）を表示した後には , を表示したくないので、条件分岐を使っています。
* printf("]\n");: ループ終了後に ] を表示し、次の出力が新しい行から始まるように改行文字 \n を表示します。

bubbleSort 関数

これがバブルソートの核心部分です。

c
void bubbleSort(int arr[], int size) {
// 外側のループ: パスの回数を制御
// 配列サイズnに対して、n-1回のパスを行えば必ずソートが完了する
for (int i = 0; i < size - 1; i++) {
// 内側のループ: 隣接要素の比較と交換
// 各パス(i)ごとに、末尾からi個の要素はソート済み（確定済み）なので、
// 比較対象は arr[0] から arr[size - 1 - i] までとなる
// 比較は arr[j] と arr[j+1] で行うので、jは size - 1 - i の手前まで回る
// つまり、j の最大値は (size - 1 - i) - 1 = size - 2 - i となる
// forループの条件式 j < size - 1 - i は、jが size - 2 - i まで繰り返すことを意味する
for (int j = 0; j < size - 1 - i; j++) {
// 隣り合う要素 arr[j] と arr[j+1] を比較
if (arr[j] > arr[j+1]) { // 昇順の場合: arr[j] が arr[j+1] より大きければ交換
// 要素を交換 (スワップ)
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
// (オプション) 各パス終了後の配列の状態を表示
// printf("Pass %d: ", i + 1);
// displayArray(arr, size); // この行を有効にすると、各パスの途中経過が見られます
}
}

  • void bubbleSort(int arr[], int size): displayArray 関数と同様に、配列のポインタとサイズを受け取ります。返り値はありません（配列自体が関数内で直接変更されます）。
  • 外側のループ: for (int i = 0; i < size - 1; i++)
    • 変数 i は、何回目のパスか を表します（0から始まります）。
    • サイズ size の配列の場合、size - 1 回のパスを行えばソートは完了します。例えば、サイズ6の配列なら5回のパスで十分です。そのため、ループ条件は i < size - 1 となります。i は 0, 1, 2, ..., size-2 と変化します。
    • i が0のとき（1回目のパス）、末尾から0個の要素が確定しています。
    • i が1のとき（2回目のパス）、末尾から1個の要素が確定しています。
    • i がkのとき（k+1回目のパス）、末尾からk個の要素が確定しています。
  • 内側のループ: for (int j = 0; j < size - 1 - i; j++)
    • 変数 j は、現在比較している左側の要素の添え字 を表します。
    • このループの中で、arr[j] と arr[j+1] を比較・交換します。
    • ループ条件 j < size - 1 - i が重要です。
      • size - 1 は配列の最後の添え字です。
      • size - 1 - i は、現在のパス i で比較を行うべき最後の添え字の 次 の値です。
      • なぜ size - 1 - i までか？
        • 外側のループ変数 i が k のとき、配列の末尾から k 個の要素 (arr[size-k] から arr[size-1]) は既にソート済み（確定済み）です。
        • したがって、内側のループで比較・交換を行う必要があるのは、添え字 0 から size - 1 - i までの範囲です。
        • arr[j] と arr[j+1] を比較するので、j の最大値は (size - 1 - i) - 1 = size - 2 - i となります。
        • for (int j = 0; j < size - 1 - i; j++) という条件は、j が 0 から size - 2 - i まで変化することを意味しており、これは正しく比較範囲を指定しています。
        • 例えば、サイズ6 (size = 6) の配列の場合:
          • i = 0 (1パス目): j は 0 から 6 - 1 - 0 = 5 の手前、つまり 0 から 4 まで変化します。比較対象は (arr[0], arr[1]) から (arr[4], arr[5]) までとなり、最も大きい要素が arr[5] に移動・確定します。
          • i = 1 (2パス目): j は 0 から 6 - 1 - 1 = 4 の手前、つまり 0 から 3 まで変化します。比較対象は (arr[0], arr[1]) から (arr[3], arr[4]) までとなり、未ソート部分 (arr[0]～arr[4]) で最も大きい要素が arr[4] に移動・確定します。
          • …
          • i = size - 2 (最後のパス): j は 0 から size - 1 - (size - 2) = 1 の手前、つまり 0 まで変化します。比較対象は (arr[0], arr[1]) のみとなり、arr[0] と arr[1] がソートされます。これで配列全体がソート完了します。
  • if (arr[j] > arr[j+1]): arr[j] とその右隣の要素 arr[j+1] を比較します。昇順ソートなので、もし左側の要素 arr[j] が右側の要素 arr[j+1] より大きければ、順序が逆なので交換が必要です。
  • 要素の交換（スワップ）:
    c
    int temp = arr[j];
    arr[j] = arr[j+1];
    arr[j+1] = temp;
    これは C言語で二つの変数の値を交換する際の典型的なイディオム（慣用的な書き方）です。

    1. 一時変数 temp を用意し、arr[j] の値をそこに避難させます。
    2. arr[j+1] の値を arr[j] に上書きします。これで arr[j] には右隣の値が入ります。
    3. temp に避難させておいた元の arr[j] の値を arr[j+1] に代入します。これで arr[j+1] には元の左側の値が入ります。
      このように一時変数を使わないと、例えば arr[j] = arr[j+1]; arr[j+1] = arr[j]; と書いてしまうと、arr[j+1] の値が両方の変数に入ってしまい、元の arr[j] の値が失われてしまいます。

main 関数

プログラムのエントリーポイント（開始地点）です。

“`c
int main() {
// ソートしたい整数の配列を準備
int myArray[] = {5, 2, 8, 1, 9, 4};
// 配列の要素数を計算
int arraySize = sizeof(myArray) / sizeof(myArray[0]);

printf("--- バブルソート (昇順) ---\n");

// ソート前の配列を表示
printf("ソート前: ");
displayArray(myArray, arraySize);

// バブルソートを実行
bubbleSort(myArray, arraySize); // 関数呼び出し。配列とサイズを渡す

// ソート後の配列を表示
printf("ソート後: ");
displayArray(myArray, arraySize);

printf("-------------------------\n");

return 0; // プログラム正常終了を示す値を返す

}
“`

  • int myArray[] = {5, 2, 8, 1, 9, 4};: ソート対象となる整数の配列を宣言し、初期値を代入しています。
  • int arraySize = sizeof(myArray) / sizeof(myArray[0]);: 配列の要素数を計算するおなじみの方法です。sizeof(myArray) は配列全体のメモリ上のバイト数、sizeof(myArray[0]) は配列の最初の要素（int型）のバイト数です。全体のバイト数を要素一つのバイト数で割れば、要素数が求まります。この方法は、関数に渡された配列（ポインタとして扱われる）に対しては使えないため、main 関数内で配列サイズを計算し、ソート関数に引数として渡す必要があります。
  • printf(...): 標準出力に文字列を表示します。
  • displayArray(myArray, arraySize);: 作成した displayArray 関数を呼び出し、ソート前後の配列の状態を表示します。
  • bubbleSort(myArray, arraySize);: 作成した bubbleSort 関数を呼び出し、myArray の内容をソートします。関数に配列を渡すと、配列の先頭アドレスが渡される（参照渡しのような効果）ため、bubbleSort 関数内で配列の内容を直接書き換えることができます。

これで、基本的なバブルソートのC言語コードと、その詳細な仕組みを理解できたはずです。

第6章：バブルソートの効率と計算量 – なぜ「遅い」と言われるのか

バブルソートは原理が簡単な反面、効率が悪いことで知られています。プログラムの効率を評価する際には、主に 計算量（Computational Complexity） という考え方を使います。これは、アルゴリズムが問題を解決するために必要とする計算ステップの数や、使用するメモリの量を、入力データのサイズ（通常は n で表される）に対する関数として表現したものです。特に、データサイズが非常に大きくなったときに、処理時間がどのように増加するかに関心があります。

計算量を表現する際には、オーダー記法（O記法、Big O notation） がよく用いられます。これは、データサイズ n が無限に大きくなったときに、処理時間が最も影響を受ける主要な項だけを取り出して、定数倍や小さい次数の項を無視して簡潔に表現する方法です。

バブルソートの計算量分析

バブルソートがどれくらいの計算ステップを行うか、具体的に見ていきましょう。計算ステップとして、主に「比較」と「交換」の回数を考えます。

  • 1回目のパス (i=0): n-1 回の比較と、最大 n-1 回の交換が発生する可能性があります（j が 0 から n-2 まで）。
  • 2回目のパス (i=1): n-2 回の比較と、最大 n-2 回の交換が発生する可能性があります（j が 0 から n-3 まで）。
  • …
  • 最後のパス (i=n-2): 1 回の比較と、最大 1 回の交換が発生する可能性があります（j が 0 まで）。

パスの合計回数は n-1 回です。
合計の比較回数は (n-1) + (n-2) + ... + 1 となります。
これは等差数列の和であり、計算すると (n-1) * n / 2 となります。

合計の交換回数も、最悪の場合（完全に逆順にソートされている場合など）には比較回数に近い回数発生する可能性があります。

n(n-1)/2 を展開すると (n^2 - n) / 2 となります。
オーダー記法では、データサイズ n が大きくなったときに最も影響が大きい項、つまり n^2 の項だけに着目し、定数倍 (1/2) や次数が低い項 (-n) は無視します。

したがって、バブルソートの計算量は O(n^2) と表現されます。

これは、もしデータサイズが2倍になると、処理時間が約 2^2 = 4 倍になることを意味します。データサイズが10倍になると、処理時間は約 10^2 = 100 倍になります。データサイズが1000倍になると、処理時間は約 1000^2 = 1,000,000 倍になります。

例えば、100個のデータをソートするのに1秒かかるとしたら、10万個（1000倍）のデータをソートするには、単純計算で100万秒、つまり約11.5日かかることになります。

他のソートアルゴリズムとの比較

計算量がO(n^2)であるソートアルゴリズムは、バブルソートの他に、選択ソートや挿入ソートなどがあります。これらは一般的に「基本ソートアルゴリズム」と呼ばれ、原理がシンプルですが、大規模なデータには向きません。

一方、マージソートやクイックソートといったアルゴリズムは、より洗練されており、平均的な計算量が O(n log n) となります。
O(n log n) のアルゴリズムは、データサイズが2倍になっても処理時間は約 2 * log2(2) / (1 * log2(1)) ではなく 2 * log2(2n) / (n log2 n) のように増加し、O(n^2) に比べてはるかに増加率が緩やかです。
例えば、100個のデータに1秒かかるアルゴリズムがO(n log n)だったとすると、10万個のデータにかかる時間は、単純計算で (100000 * log(100000)) / (100 * log(100)) 秒程度となり、log の底を2とすると (100000 * 16.6) / (100 * 6.6) ≈ 1660000 / 660 ≈ 2500秒、つまり約40分程度で終わる可能性があります。11.5日と比較すると圧倒的な差があります。

このように、データサイズが大きくなるにつれて、O(n^2)とO(n log n)の差は非常に大きくなります。これが、バブルソートが「遅い」と言われ、実用的な場面で大規模データのソートに使われることが少ない理由です。

しかし、バブルソートを学ぶことには価値があります。そのシンプルな原理は、ソートという操作の基本を理解するのに最適であり、アルゴリズムの考え方を学ぶ上での良い出発点となります。また、後述する最適化を行うことで、特定のケース（例えば、ほとんどソート済みのデータ）では効率を改善することも可能です。

第7章：バブルソートの改善（最適化） – 早期終了の導入

基本的なバブルソートは、たとえデータが既に完全にソートされていても、最後まで全てのパスを実行します。これは無駄な処理です。もしあるパスで一度も要素の交換が発生しなかったとしたら、それは配列が既にソートされていることを意味します。この事実を利用して、ソートが完了したら処理を中断する最適化を加えることができます。

この最適化には、各パスの開始時にフラグ（旗印）を用意し、交換が発生するたびにそのフラグを立てる、という方法がよく使われます。パスの終わりにフラグが立っていなければ（一度も交換されていなければ）、ソートは完了していると判断できます。

最適化を施したバブルソートのC言語コードは以下のようになります。

“`c

include

include // bool型を使うために必要

// 配列の内容を表示する関数 (変更なし)
void displayArray(int arr[], int size) {
printf(“[“);
for (int i = 0; i < size; i++) {
printf(“%d”, arr[i]);
if (i < size – 1) {
printf(“, “);
}
}
printf(“]\n”);
}

// バブルソートを実行する関数（昇順、最適化済み）
void bubbleSortOptimized(int arr[], int size) {
// 外側のループ: パスの回数を制御 (最大size-1回)
for (int i = 0; i < size – 1; i++) {
// このパスで交換が発生したかを示すフラグ
bool swapped = false; // 最初は交換されていないと仮定

    // 内側のループ: 隣接要素の比較と交換
    // 末尾からi個は確定済みなので除く
    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 = true;
        }
    }

    // 各パス終了後の配列の状態を表示してみる
    // printf("Pass %d: ", i + 1);
    // displayArray(arr, size);

    // もしこのパスで一度も交換が発生しなかったら、配列は既にソートされている
    if (swapped == false) {
        // ソート完了なので外側のループを中断する
        printf("(Pass %d で交換なし、ソート完了と判断)\n", i + 1); // 最適化されたことを示すメッセージ
        break;
    }
}

}

int main() {
int myArray[] = {5, 2, 8, 1, 9, 4};
int arraySize = sizeof(myArray) / sizeof(myArray[0]);

printf("--- 最適化バブルソート (昇順) ---\n");

printf("ソート前: ");
displayArray(myArray, arraySize);

bubbleSortOptimized(myArray, arraySize);

printf("ソート後: ");
displayArray(myArray, arraySize);

printf("-------------------------\n");

// 既にソート済みの配列で試す場合
int sortedArray[] = {1, 2, 3, 4, 5, 6};
int sortedArraySize = sizeof(sortedArray) / sizeof(sortedArray[0]);

printf("\n--- 最適化バブルソート (ソート済み配列) ---\n");
printf("ソート前: ");
displayArray(sortedArray, sortedArraySize);
bubbleSortOptimized(sortedArray, sortedArraySize);
printf("ソート後: ");
displayArray(sortedArray, sortedArraySize);
printf("-------------------------\n");


return 0;

}
“`

最適化コードの解説

  • #include <stdbool.h>: bool 型（真偽値を表す型、true または false をとる）を使用するために必要なヘッダーファイルです。C99規格以降で利用可能です。
  • void bubbleSortOptimized(int arr[], int size): 最適化版の関数です。
  • bool swapped = false;: 内側のループ（1パス）が始まる直前に、swapped という名前の bool 型変数を false で初期化します。これは「このパスではまだ交換が発生していない」という状態を表します。
  • if (arr[j] > arr[j+1]) { ... swapped = true; }: 隣接要素を比較し、交換を行った場合に、この swapped フラグを true に設定します。
  • if (swapped == false) { break; }: 内側のループ（1パス）が終了した後、swapped フラグが false のままであれば、それはこのパスで一度も交換が行われなかったことを意味します。つまり、配列は既に完全にソートされています。この場合、外側のループを break 文で中断し、関数を終了します。

この最適化により、以下のような場合に効率が向上します。

  • 既にソートされている配列: 1回目のパスで一度も交換が発生しないため、内側のループを n-1 回実行した後、外側のループは1回だけ回って終了します。この場合の計算量は O(n) となります。要素一つ一つを比較するために配列を一度走査する必要があるため、これより速くすることはできません。
  • ほとんどソートされている配列: ソートが必要な要素が少ない場合、比較的少ないパスでソートが完了し、早期に終了できます。

ただし、データの状態がランダムである場合や、完全に逆順にソートされている最悪の場合には、交換フラグによる中断は発生せず、結局 n-1 回のパスを最後まで実行することになり、計算量はO(n^2)のままです。

この最適化は、バブルソートの最良ケースの計算量をO(n^2)からO(n)に改善するものですが、平均ケースや最悪ケースの計算量（O(n^2)）は変わりません。そのため、一般的にはやはり大規模データのソートには向かないアルゴリズムであることに変わりはありません。しかし、アルゴリズムの効率を改善する考え方を学ぶ上で、非常に良い例となります。

第8章：バブルソートのメリット・デメリット

ここで一度、バブルソートの長所と短所を整理してみましょう。

メリット

  1. 原理が非常にシンプル: 「隣り合う要素を比較して、順序が逆なら交換する」という操作を繰り返すだけという、極めて単純なアルゴリズムです。アルゴリズム学習の入門として最適です。
  2. 実装が容易: コード量が少なく、理解しやすい構造なので、プログラミング初心者でも比較的簡単に実装できます。
  3. 安定なソートアルゴリズムである: 同じ値を持つ要素が複数ある場合、ソート後もそれらの要素の相対的な順序が保たれます。これは、同じ値を持つ要素を比較しても交換が発生しないためです。安定なソートは、複数のキーでソートを行う場合などに重要になることがあります。
  4. 追加の記憶領域（メモリ）があまり必要ない: 要素の交換のために一時変数が一つ必要なだけで、入力配列とは別に大きな作業領域を用意する必要がありません。このようなソートを in-placeソート と呼びます。

デメリット

  1. 非常に非効率: 平均的な計算量、最悪計算量が O(n^2) と、データサイズの増加に対して処理時間が急激に増加します。数万件、数十万件といった大規模なデータをソートするには現実的ではありません。
  2. 常に多くの交換が発生する: データがソートされていない場合、隣接要素の比較・交換が頻繁に発生します。特に、配列の先頭にある小さい値が配列の末尾の方にある場合、その値が適切な位置まで移動するためには、多くのパスと交換が必要になります。これを「ウミガメ問題（Turtle Problem）」と呼ぶこともあります。重い要素は末尾にすぐに沈みますが、軽い要素が先頭に「浮かび上がる」のは時間がかかります。
  3. 実用的な場面での使用は限定的: 上記の非効率性から、高速性が求められる場面や大規模データを扱う場面ではほとんど使用されません。教育目的、あるいは非常に小規模なデータ（せいぜい数百件以下）のソートに限定されます。最適化を加えた場合でも、ほとんどソート済みのデータや、ランダムなデータに対する効率は他のアルゴリズムに劣ります。

第9章：バブルソートの学習意義と次のステップ

実用性は低いとされるバブルソートですが、それを学ぶことには確かな意義があります。

  1. アルゴリズムの基礎を理解する: バブルソートは、ソートという問題を解決するための最も素朴なアプローチを示しています。隣接要素の比較と交換というシンプルな操作の繰り返しで、最終的に全体の順序が整う、という「要素の局所的な操作が全体の構造に影響を与える」というアルゴリズム的な思考の基礎を学ぶことができます。
  2. ループ構造や配列操作の練習: C言語において、配列を関数に渡したり、二重ループを使って配列の要素にアクセスしたり、要素を交換したりといった基本的な操作の良い練習台となります。
  3. アルゴリズムの効率を考えるきっかけ: なぜ O(n^2) が遅いのか、なぜ計算量を評価することが重要なのかを理解する上で、具体的な O(n^2) のアルゴリズムを学ぶことは非常に有効です。より高速なアルゴリズムを学ぶ際の比較対象となります。
  4. 最適化の考え方を学ぶ: 交換フラグによる最適化は、単純なアルゴリズムでも工夫次第で特定のケースの効率を改善できることを示しています。これは、より複雑なアルゴリズムの最適化を理解する上での基礎となります。

バブルソートを理解したら、次に学ぶべきソートアルゴリズムはいくつかあります。いずれもバブルソートよりも効率が良いか、異なる特徴を持っています。

  • 選択ソート (Selection Sort): 未ソート部分から最小（または最大）の要素を探し出し、それを未ソート部分の先頭と交換していくアルゴリズム。これも O(n^2) ですが、バブルソートより交換回数が少ないという特徴があります。
  • 挿入ソート (Insertion Sort): 配列を「ソート済み部分」と「未ソート部分」に分け、未ソート部分から要素を一つずつ取り出し、ソート済み部分の適切な位置に挿入していくアルゴリズム。最良ケースが O(n) であり、配列がほとんどソートされている場合に効率が良いという特徴があります。小規模なデータに対しては比較的効率的です。
  • マージソート (Merge Sort): 配列を分割し、それぞれを再帰的にソートし、最後にソート済みの部分配列を結合（マージ）していくアルゴリズム。常に O(n log n) の計算量ですが、追加のメモリ領域が必要になります。
  • クイックソート (Quick Sort): 配列の中から基準となる要素（ピボット）を選び、ピボットより小さい要素をその左に、大きい要素を右に集める（分割）操作を繰り返すアルゴリズム。平均的な計算量が O(n log n) で非常に高速ですが、最悪ケースは O(n^2) になる可能性があります。実際によく使われるソートアルゴリズムの一つです。

これらのアルゴリズムを順に学ぶことで、様々なソート手法とその効率、トレードオフについての理解を深めることができます。バブルソートはそのための最初の、大切なステップなのです。

第10章：練習問題

理解を深めるために、以下の練習問題に取り組んでみましょう。

  1. 降順ソート: 現在の bubbleSort 関数は昇順（小さい順）にソートします。比較条件 if (arr[j] > arr[j+1]) を変更して、降順（大きい順）にソートできるように改良してみましょう。
    • ヒント: どのように比較すれば、大きい要素が配列の先頭の方に「浮かび上がる」でしょうか？
  2. 最適化フラグの実装: 基本的な bubbleSort 関数を、第7章で解説した交換フラグによる最適化を自分で実装してみてください。
  3. 配列サイズをユーザー入力に: main 関数で、配列のサイズをユーザーにキーボードから入力させ、そのサイズの動的な配列（ポインタと malloc を使用）を作成し、要素をユーザーに入力させてからバブルソートを実行するように変更してみましょう。
    • ヒント: malloc 関数、scanf 関数、そして free 関数（メモリ解放のため）が必要になります。配列を関数に渡す際は、先頭アドレスとサイズを渡すことになります。
  4. 構造体のソート: 例えば、名前（文字列）と点数（整数）を持つ学生の構造体配列を作成し、点数の昇順でバブルソートできるように変更してみましょう。
    • ヒント: 比較演算子 < や > は構造体には直接使えません。構造体の特定のメンバ（この場合は点数）を比較する必要があります。要素を交換する際も、構造体全体を交換する必要があります。

これらの練習問題を通して、バブルソートだけでなく、C言語の配列、ポインタ、構造体、動的メモリ割り当て、関数の使い方など、様々な基本スキルを同時に習得することができます。

まとめ：バブルソートを理解して、アルゴリズム学習の第一歩を踏み出そう

この記事では、バブルソートについて、その基本的な原理、具体的なアルゴリズムのステップ、C言語での詳細な実装方法、計算量に基づく効率の評価、そして簡単な最適化の手法まで、幅広く解説しました。

バブルソートは、確かに最も効率の良いソートアルゴリズムではありません。大規模なデータを扱う実際のアプリケーションで直接使われる機会は少ないでしょう。しかし、その驚くほどシンプルな仕組みは、アルゴリズムの入門として、またC言語の基本要素（ループ、配列、ポインタ、条件分岐、変数の交換）の良い練習問題として、非常に価値があります。

バブルソートを通して、あなたは「問題を解決するための手順（アルゴリズム）」を考え、それを「プログラムコードに落とし込む」という経験をしました。また、「アルゴリズムの効率」という重要な概念に触れ、なぜ同じ問題を解くにも様々なアルゴリズムが存在するのか、その理由の一端を知ることができました。

これは、アルゴリズム学習の素晴らしい第一歩です。次に、選択ソートや挿入ソートといった他の O(n^2) のアルゴリズムを学び、バブルソートと比較してみるのも良いでしょう。さらに、マージソートやクイックソートといった高速な O(n log n) のアルゴリズムに挑戦すれば、アルゴリズムの世界がさらに広がるはずです。

プログラミングは、ただコードを書くだけでなく、効率的で洗練された手順を考えることが重要です。バブルソートの学習で得た知識と経験を活かして、ぜひ次のステップへと進んでください。

これで、C言語初心者向けバブルソートの詳細な解説記事を終わりにします。お疲れ様でした！

コメントする

メールアドレスが公開されることはありません。 ※ が付いている欄は必須項目です

上部へスクロール