C言語のソート手法を徹底解説！バブルソートの仕組みと実装例

問題

C言語にはどのようなソート手法があるのか？また、そのうち1つを選んで具体例とともに説明しなさい。

解答

C言語では、主に以下の5つのソート手法が用いられます。

• バブルソート（交換ソート）
• 選択ソート
• 挿入ソート（線形ソート）
• クイックソート（分割交換ソート）
• マージソート（外部ソート）

バブルソートとは

バブルソートは最もシンプルなソート手法であり、「交換ソート」とも呼ばれます。隣接する要素同士（または基準要素と他の要素）を比較し、順序が正しくなければ入れ替えることを繰り返すことで、リスト全体を昇順に並べ替えます。

基本の手順

• 先頭の要素を残りのすべての要素と比較し、順序が正しくなければ交換（スワップ）します。
• この操作を2番目以降の要素に対しても繰り返し、すべての要素が整列されるまで続けます。

ソートの流れ（例）

次の5つの要素を昇順に並べ替えてみましょう。

30 50 40 10 20

第1パス：先頭要素との比較

a[0] を残りの要素と順番に比較します。

• a[0] > a[1] → 30 > 50（偽）→ 交換なし
• a[0] > a[2] → 30 > 40（偽）→ 交換なし
• a[0] > a[3] → 30 > 10（真）→ 交換
• a[0] > a[4] → 10 > 20（偽）→ 交換なし

このパスが終わった時点での配列の状態：

10 50 40 30 20

第2パス：2番目の要素との比較

次に a[1] を残りの要素と比較します。

• a[1] > a[2] → 50 > 40（真）→ 交換
• a[1] > a[3] → 40 > 30（真）→ 交換
• a[1] > a[4] → 30 > 20（真）→ 交換

10 20 50 40 30

第3パス：3番目の要素との比較

a[2] を残りの要素と比較します。

• a[2] > a[3] → 50 > 40（真）→ 交換
• a[2] > a[4] → 40 > 30（真）→ 交換

10 20 30 50 40

第4パス：4番目の要素との比較

最後に a[3] を残りの要素と比較します。

• a[3] > a[4] → 50 > 40（真）→ 交換

10 20 30 40 50

これですべての要素が昇順に整列されました。

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

バブルソートは、二重ループを使って次のように記述できます。

for (i=0; i<n-1; i++){
    for (j=i+1; j<n; j++){
        if (a[i] > a[j]){
            t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    }
}

外側のループで基準位置を移動させ、内側のループで基準要素より後ろの要素すべてと比較しています。a[i] の方が大きければ、一時変数 t を介して値を入れ替えます。

C言語によるサンプルプログラム

以下は、バブルソートを実装した完全なCプログラムです。

#include<stdio.h>
int main(){
    int a[50], i, j, n, t;
    printf("enter the No: of elements in the list:\n");
    scanf("%d", &n);
    printf("enter the elements:\n");
    for(i=0; i<n; i++){
        scanf("%d", &a[i]);
    }
    printf("Before bubble sorting the elements are:\n");
    for(i=0; i<n; i++)
        printf("%d \t\n", a[i]);
    for (i=0; i<n-1; i++){
        for (j=i+1; j<n; j++){
            if (a[i] > a[j]){
                t = a[i];
                a[i] = a[j];
                a[j] = t;
            }
        }
    }
    printf("after bubble sorting the elements are:\n");
    for (i=0; i<n; i++)
        printf("%d\t", a[i]);
    return 0;
}

実行結果

上記のプログラムを実行すると、次のような出力が得られます。

enter the No: of elements in the list:
5
enter the elements:
12 11 45 26 67
Before bubble sorting the elements are:
12
11
45
26
67
after bubble sorting the elements are:
11 12 26 45 67

まとめ

バブルソートは理解しやすい反面、計算量は O(n²) となるため、大量のデータを扱う場合にはクイックソートやマージソートなど、より効率的な手法が適しています。まずはこのシンプルなアルゴリズムでソートの基本概念をしっかり押さえましょう。