MENU
  1. ホーム
  2. C言語
  3. アルゴリズム
  4. [C言語] バブルソートとは？実装方法をサンプルコード付きで解説

[C言語] バブルソートとは？実装方法をサンプルコード付きで解説

バブルソートは、隣接する要素を比較し、必要に応じて交換することでリストをソートする単純なアルゴリズムです。

このプロセスをリスト全体に対して繰り返し、リストが完全にソートされるまで続けます。

バブルソートは、実装が簡単で理解しやすい反面、効率が悪く、大規模なデータセットには不向きです。

特に、最悪および平均の時間計算量がO(n^2)であるため、他のソートアルゴリズムと比較してパフォーマンスが劣ります。

しかし、教育目的や小規模なデータセットには適しています。

この記事でわかること
  • C言語でのバブルソートの基本的な実装方法
  • バブルソートの応用例と最適化手法
  • 他のソートアルゴリズムとの比較と特徴
  • バブルソートが教育的に重要とされる理由
  • バブルソートの適用場面と効率改善の方法

目次から探す

C言語でのバブルソート実装

必要な準備と環境設定

バブルソートをC言語で実装するためには、基本的なC言語の開発環境が必要です。

以下に、準備すべき項目を示します。

スクロールできます
項目説明
コンパイラGCCやClangなどのC言語コンパイラをインストールします。
テキストエディタVisual Studio CodeやSublime Textなど、コードを書くためのエディタを用意します。
ターミナルコマンドラインでコンパイルと実行を行うためのターミナルを使用します。

これらの環境が整っていれば、C言語でのプログラミングを始めることができます。

基本的なバブルソートの実装

バブルソートは、隣接する要素を比較し、必要に応じて交換することでリストをソートするシンプルなアルゴリズムです。

以下に、基本的なバブルソートの実装を示します。

#include <stdio.h>
// バブルソート関数
void bubbleSort(int array[], int size) {
    for (int step = 0; step < size - 1; ++step) {
        for (int i = 0; i < size - step - 1; ++i) {
            // 隣接する要素を比較
            if (array[i] > array[i + 1]) {
                // 要素を交換
                int temp = array[i];
                array[i] = array[i + 1];
                array[i + 1] = temp;
            }
        }
    }
}
// メイン関数
int main() {
    int data[] = {5, 2, 9, 1, 5, 6};
    int size = sizeof(data) / sizeof(data[0]);
    bubbleSort(data, size);
    printf("ソート後の配列: ");
    for (int i = 0; i < size; ++i) {
        printf("%d ", data[i]);
    }
    printf("\n");
    return 0;
}

サンプルコードの解説

上記のサンプルコードでは、bubbleSort関数を用いて整数の配列をソートしています。

bubbleSort関数は、配列とそのサイズを引数として受け取り、配列を昇順にソートします。

  • forループを二重に使用して、配列内の要素を順に比較します。
  • 内側のループでは、隣接する要素を比較し、必要に応じて交換を行います。
  • 外側のループは、配列全体を何度も繰り返し処理することで、すべての要素が正しい位置に来るまで続けます。

このコードを実行すると、配列dataが昇順にソートされ、結果が表示されます。

ソート後の配列: 1 2 5 5 6 9

このように、バブルソートはシンプルで理解しやすいアルゴリズムですが、効率が良くないため、大規模なデータセットには向いていません。

バブルソートの応用例

昇順・降順の切り替え

バブルソートは、比較条件を変更することで、昇順だけでなく降順にもソートすることができます。

以下に、昇順と降順を切り替える方法を示します。

#include <stdio.h>
// バブルソート関数(昇順・降順切り替え)
void bubbleSort(int array[], int size, int ascending) {
    for (int step = 0; step < size - 1; ++step) {
        for (int i = 0; i < size - step - 1; ++i) {
            // 昇順の場合
            if (ascending && array[i] > array[i + 1]) {
                int temp = array[i];
                array[i] = array[i + 1];
                array[i + 1] = temp;
            }
            // 降順の場合
            else if (!ascending && array[i] < array[i + 1]) {
                int temp = array[i];
                array[i] = array[i + 1];
                array[i + 1] = temp;
            }
        }
    }
}
// メイン関数
int main() {
    int data[] = {5, 2, 9, 1, 5, 6};
    int size = sizeof(data) / sizeof(data[0]);
    // 昇順ソート
    bubbleSort(data, size, 1);
    printf("昇順ソート: ");
    for (int i = 0; i < size; ++i) {
        printf("%d ", data[i]);
    }
    printf("\n");
    // 降順ソート
    bubbleSort(data, size, 0);
    printf("降順ソート: ");
    for (int i = 0; i < size; ++i) {
        printf("%d ", data[i]);
    }
    printf("\n");
    return 0;
}

このコードでは、ascendingというフラグを用いて、昇順(1)または降順(0)を選択できます。

実行すると、配列が指定された順序でソートされます。

部分的なソートの実装

バブルソートを用いて、配列の一部だけをソートすることも可能です。

以下に、部分的なソートの例を示します。

#include <stdio.h>
// 部分的なバブルソート関数
void partialBubbleSort(int array[], int start, int end) {
    for (int step = start; step < end - 1; ++step) {
        for (int i = start; i < end - step - 1; ++i) {
            if (array[i] > array[i + 1]) {
                int temp = array[i];
                array[i] = array[i + 1];
                array[i + 1] = temp;
            }
        }
    }
}
// メイン関数
int main() {
    int data[] = {5, 2, 9, 1, 5, 6};
    int size = sizeof(data) / sizeof(data[0]);
    // 配列の一部をソート(インデックス1から4まで)
    partialBubbleSort(data, 1, 5);
    printf("部分的なソート: ");
    for (int i = 0; i < size; ++i) {
        printf("%d ", data[i]);
    }
    printf("\n");
    return 0;
}

このコードでは、partialBubbleSort関数を用いて、配列の指定された範囲だけをソートします。

これにより、特定の部分だけを効率的にソートすることができます。

バブルソートを用いたデータの安定性の確認

バブルソートは安定なソートアルゴリズムであり、同じ値の要素が元の順序を保つことが保証されます。

以下に、データの安定性を確認する例を示します。

#include <stdio.h>
// 構造体の定義
typedef struct {
    int value;
    char label;
} Element;
// バブルソート関数(安定性の確認)
void stableBubbleSort(Element array[], int size) {
    for (int step = 0; step < size - 1; ++step) {
        for (int i = 0; i < size - step - 1; ++i) {
            if (array[i].value > array[i + 1].value) {
                Element temp = array[i];
                array[i] = array[i + 1];
                array[i + 1] = temp;
            }
        }
    }
}
// メイン関数
int main() {
    Element data[] = {{5, 'A'}, {2, 'B'}, {5, 'C'}, {1, 'D'}, {5, 'E'}, {6, 'F'}};
    int size = sizeof(data) / sizeof(data[0]);
    stableBubbleSort(data, size);
    printf("安定性の確認: ");
    for (int i = 0; i < size; ++i) {
        printf("(%d, %c) ", data[i].value, data[i].label);
    }
    printf("\n");
    return 0;
}

このコードでは、Elementという構造体を用いて、同じ値を持つ要素が元の順序を保つことを確認しています。

実行すると、同じ値の要素が元の順序を維持していることがわかります。

バブルソートの最適化

バブルソートはシンプルなアルゴリズムですが、効率が良くないため、いくつかの最適化手法を用いることでパフォーマンスを向上させることができます。

以下に、バブルソートの最適化方法を紹介します。

フラグを用いた最適化

フラグを用いることで、配列がすでにソートされている場合に無駄なループを回避することができます。

以下に、フラグを用いた最適化の例を示します。

#include <stdio.h>
// フラグを用いたバブルソート関数
void optimizedBubbleSort(int array[], int size) {
    int swapped;
    for (int step = 0; step < size - 1; ++step) {
        swapped = 0; // フラグをリセット
        for (int i = 0; i < size - step - 1; ++i) {
            if (array[i] > array[i + 1]) {
                int temp = array[i];
                array[i] = array[i + 1];
                array[i + 1] = temp;
                swapped = 1; // 要素が交換されたことを記録
            }
        }
        // 交換が行われなかった場合、ソート済みと判断して終了
        if (!swapped) {
            break;
        }
    }
}
// メイン関数
int main() {
    int data[] = {5, 2, 9, 1, 5, 6};
    int size = sizeof(data) / sizeof(data[0]);
    optimizedBubbleSort(data, size);
    printf("最適化されたソート: ");
    for (int i = 0; i < size; ++i) {
        printf("%d ", data[i]);
    }
    printf("\n");
    return 0;
}

このコードでは、swappedというフラグを用いて、要素の交換が行われたかどうかを記録します。

交換が行われなかった場合、配列はすでにソートされているため、ループを早期に終了します。

ループ回数の削減

バブルソートでは、各ステップで最後の要素が確定するため、次のステップではその要素を無視することができます。

これにより、ループ回数を削減できます。

#include <stdio.h>
// ループ回数を削減したバブルソート関数
void reducedLoopBubbleSort(int array[], int size) {
    for (int step = 0; step < size - 1; ++step) {
        for (int i = 0; i < size - step - 1; ++i) {
            if (array[i] > array[i + 1]) {
                int temp = array[i];
                array[i] = array[i + 1];
                array[i + 1] = temp;
            }
        }
    }
}
// メイン関数
int main() {
    int data[] = {5, 2, 9, 1, 5, 6};
    int size = sizeof(data) / sizeof(data[0]);
    reducedLoopBubbleSort(data, size);
    printf("ループ回数削減: ");
    for (int i = 0; i < size; ++i) {
        printf("%d ", data[i]);
    }
    printf("\n");
    return 0;
}

このコードでは、size - step - 1までのループを行うことで、すでにソート済みの部分を無視しています。

早期終了の実装

バブルソートの最適化として、早期終了を実装することで、無駄な計算を省くことができます。

これは、フラグを用いた最適化と似ていますが、より明示的に早期終了を行います。

#include <stdio.h>
// 早期終了を実装したバブルソート関数
void earlyExitBubbleSort(int array[], int size) {
    int swapped;
    for (int step = 0; step < size - 1; ++step) {
        swapped = 0;
        for (int i = 0; i < size - step - 1; ++i) {
            if (array[i] > array[i + 1]) {
                int temp = array[i];
                array[i] = array[i + 1];
                array[i + 1] = temp;
                swapped = 1;
            }
        }
        if (!swapped) {
            printf("早期終了: ステップ %d でソート完了\n", step + 1);
            break;
        }
    }
}
// メイン関数
int main() {
    int data[] = {1, 2, 3, 4, 5, 6};
    int size = sizeof(data) / sizeof(data[0]);
    earlyExitBubbleSort(data, size);
    printf("早期終了ソート: ");
    for (int i = 0; i < size; ++i) {
        printf("%d ", data[i]);
    }
    printf("\n");
    return 0;
}

このコードでは、配列がすでにソートされている場合、早期に終了することを明示的に示しています。

これにより、無駄な計算を省き、効率的にソートを行うことができます。

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

バブルソートはシンプルで理解しやすいアルゴリズムですが、他のソートアルゴリズムと比較すると効率が劣ることがあります。

ここでは、選択ソート、挿入ソート、クイックソートと比較して、バブルソートの特徴を見ていきます。

選択ソートとの比較

選択ソートは、未ソート部分から最小(または最大)の要素を選んで、ソート済み部分の末尾に追加するアルゴリズムです。

バブルソートと選択ソートの主な違いは以下の通りです。

スクロールできます
特徴バブルソート選択ソート
時間計算量O(n^2)O(n^2)
安定性安定不安定
メモリ使用量O(1)O(1)
特徴隣接要素を交換最小/最大を選択

選択ソートは、バブルソートと同じく時間計算量がO(n^2)ですが、安定性がないため、同じ値の要素の順序が変わる可能性があります。

挿入ソートとの比較

挿入ソートは、配列を部分的にソートしながら、未ソート部分から要素を取り出して適切な位置に挿入するアルゴリズムです。

バブルソートと挿入ソートの違いは以下の通りです。

スクロールできます
特徴バブルソート挿入ソート
時間計算量O(n^2)O(n^2)
安定性安定安定
メモリ使用量O(1)O(1)
特徴隣接要素を交換適切な位置に挿入

挿入ソートは、バブルソートと同じく安定なソートですが、データがほぼ整列されている場合に効率が良くなります。

クイックソートとの比較

クイックソートは、分割統治法を用いた効率的なソートアルゴリズムで、平均時間計算量がO(n log n)です。

バブルソートとクイックソートの違いは以下の通りです。

スクロールできます
特徴バブルソートクイックソート
時間計算量O(n^2)O(n log n)
安定性安定不安定
メモリ使用量O(1)O(log n)
特徴隣接要素を交換ピボットを用いた分割

クイックソートは、バブルソートよりも効率的で、大規模なデータセットに適していますが、安定性がないため、同じ値の要素の順序が変わる可能性があります。

これらの比較から、バブルソートは教育的な目的で使われることが多く、実際のアプリケーションでは他のソートアルゴリズムが選ばれることが多いです。

選択する際は、データの特性や必要な安定性を考慮することが重要です。

よくある質問

バブルソートはどのような場合に適していますか？

バブルソートは、以下のような場合に適しています。

  • データセットが非常に小さい場合。
  • ソートの安定性が必要で、他のソートアルゴリズムを実装するのが過剰な場合。
  • 教育目的で、ソートアルゴリズムの基本的な概念を学ぶ場合。

バブルソートは効率が良くないため、大規模なデータセットには向いていませんが、簡単に実装できるため、特定の条件下では有用です。

バブルソートの実行速度を改善する方法はありますか？

バブルソートの実行速度を改善するための方法はいくつかあります。

  • フラグを用いた最適化: 配列がすでにソートされている場合に、無駄なループを回避するためにフラグを使用します。
  • ループ回数の削減: 各ステップで最後の要素が確定するため、次のステップではその要素を無視することでループ回数を削減します。
  • 早期終了の実装: 配列がソート済みであることを検出した場合に、早期にループを終了します。

これらの最適化により、バブルソートの効率を多少改善することができます。

バブルソートはなぜ教育的に重要とされるのですか？

バブルソートは教育的に重要とされる理由は以下の通りです。

  • シンプルな構造: バブルソートは非常にシンプルで、基本的なループと条件分岐を用いるため、プログラミング初心者にとって理解しやすいです。
  • 基本概念の理解: ソートアルゴリズムの基本的な概念を学ぶのに適しており、他の複雑なアルゴリズムを学ぶ前の導入として有用です。
  • 安定性の理解: 安定なソートアルゴリズムとして、同じ値の要素の順序が保持されることを学ぶことができます。

これらの理由から、バブルソートは教育の場でよく使用されます。

まとめ

バブルソートは、シンプルで理解しやすいソートアルゴリズムであり、教育的な目的でよく使用されます。

振り返ると、バブルソートは小規模なデータセットや安定性が必要な場合に適しており、最適化を施すことで多少の効率改善が可能です。

この記事を通じて、バブルソートの基本的な理解を深め、他のソートアルゴリズムとの比較を通じて、適切なアルゴリズム選択の判断材料を得ることができたでしょう。

これを機に、他のソートアルゴリズムについても学び、実際のプログラミングに応用してみてください。

目次に戻る

当サイトはリンクフリーです。出典元を明記していただければ、ご自由に引用していただいて構いません。

C言語
C++
Python
HTML
Java
HTTP

関連カテゴリーから探す

アルゴリズム
  • URLをコピーしました！

関連記事

目次から探す