[C言語] while文を使ってバブルソートを実装する方法

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

C言語でバブルソートを実装する際、while文を使用することで、ソートが完了するまで繰り返し処理を行います。

この方法では、whileループ内でforループを使用して配列の要素を順に比較し、交換が行われたかどうかを追跡するフラグを用いて、ソートが完了したかを判断します。

この実装は、シンプルで理解しやすい反面、効率が悪く、大規模なデータセットには不向きです。

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

バブルソートのアルゴリズム

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

以下にその基本的な流れを示します。

1. リストの先頭から始めて、隣接する要素を比較します。
2. 要素が順序通りでない場合、交換します。
3. リストの末尾までこの操作を繰り返します。
4. 1回のリスト走査が終わると、最大の要素がリストの末尾に移動します。
5. リスト全体がソートされるまで、上記の操作を繰り返します。

while文を使ったバブルソートの実装手順

バブルソートをwhile文で実装する際の手順は以下の通りです。

1. ソートが完了するまでループを続けるためのフラグを用意します。
2. フラグを用いて、リストの走査中に交換が発生したかを記録します。
3. 交換が発生しなくなるまで、whileループを続けます。

サンプルコードの解説

以下に、while文を使ったバブルソートのサンプルコードを示します。

#include <stdio.h>
void bubbleSort(int array[], int size) {
    int swapped;
    do {
        swapped = 0; // 交換が発生したかを記録するフラグ
        for (int i = 0; i < size - 1; i++) {
            if (array[i] > array[i + 1]) {
                // 要素を交換
                int temp = array[i];
                array[i] = array[i + 1];
                array[i + 1] = temp;
                swapped = 1; // 交換が発生したことを記録
            }
        }
    } while (swapped); // 交換が発生しなくなるまでループ
}
int main() {
    int data[] = {64, 34, 25, 12, 22, 11, 90};
    int size = sizeof(data) / sizeof(data[0]);
    bubbleSort(data, size);
    printf("ソート後の配列: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", data[i]);
    }
    return 0;
}

ソート後の配列: 11 12 22 25 34 64 90

このコードは、整数の配列を昇順にソートします。

bubbleSort関数は、配列とそのサイズを引数に取り、while文を用いてバブルソートを実行します。

swappedフラグを使用して、交換が発生しなくなるまでループを続けます。

コードの最適化ポイント

バブルソートはシンプルですが、効率的ではありません。

以下のポイントを考慮することで、若干の最適化が可能です。

• 早期終了: すでにソートされている場合、無駄な走査を避けるために、交換が発生しなかった場合はループを終了します。
• 走査範囲の縮小: 各走査の終わりに最大要素が確定するため、次の走査ではその要素を除外することができます。

これらの最適化により、バブルソートの実行時間を多少改善することができますが、計算量は依然としてO(n^2)であるため、大規模なデータセットには不向きです。

バブルソートの応用例

昇順と降順の切り替え

バブルソートは、比較条件を変更することで簡単に昇順と降順の切り替えが可能です。

以下にその方法を示します。

• 昇順ソート: if (array[i] > array[i + 1]) の条件で要素を交換します。
• 降順ソート: if (array[i] < array[i + 1]) の条件に変更することで、降順にソートできます。

このように、比較演算子を変更するだけで、ソートの順序を切り替えることができます。

数値以外のデータ型のソート

バブルソートは、数値以外のデータ型にも適用可能です。

例えば、文字列の配列をソートする場合、strcmp関数を用いて文字列を比較します。

#include <stdio.h>
#include <string.h>
void bubbleSortStrings(char *array[], int size) {
    int swapped;
    do {
        swapped = 0;
        for (int i = 0; i < size - 1; i++) {
            if (strcmp(array[i], array[i + 1]) > 0) {
                // 文字列を交換
                char *temp = array[i];
                array[i] = array[i + 1];
                array[i + 1] = temp;
                swapped = 1;
            }
        }
    } while (swapped);
}
int main() {
    char *data[] = {"banana", "apple", "orange", "grape"};
    int size = sizeof(data) / sizeof(data[0]);
    bubbleSortStrings(data, size);
    printf("ソート後の配列: ");
    for (int i = 0; i < size; i++) {
        printf("%s ", data[i]);
    }
    return 0;
}

このコードは、文字列の配列をアルファベット順にソートします。

strcmp関数を用いることで、文字列の大小を比較し、バブルソートを実現しています。

ソートの安定性を利用した応用

バブルソートは安定なソートアルゴリズムです。

つまり、同じ値の要素がある場合、元の順序が保持されます。

この特性を利用して、以下のような応用が可能です。

• 複数のキーでのソート: まず、第二キーでソートし、その後、第一キーでソートすることで、第一キーが同じ要素の順序を第二キーで決定できます。
• データの整列: 安定性を利用して、特定の条件下でデータを整列させることができます。

例えば、同じスコアの学生を名前順に並べるといったケースです。

このように、バブルソートの安定性を活用することで、特定の要件を満たすソートを実現することができます。

よくある質問

まとめ

バブルソートは、シンプルで理解しやすいソートアルゴリズムです。

小規模なデータセットや教育目的での使用に適しており、while文を用いることで柔軟なループ制御が可能です。

この記事を通じて、バブルソートの基本的な実装方法とその応用例を学びました。

これを機に、他のソートアルゴリズムにも挑戦し、プログラミングスキルをさらに向上させてください。