【C言語】第3章第14回：配列のソート方法（バブルソートなど）

配列のソートは、データを扱うプログラムで基本的な操作の1つです。この章では、バブルソートを中心に、配列をソートする方法を学びます。

1. ソートアルゴリズムとは？

ソートアルゴリズムは、配列やリストなどのデータを昇順または降順に並び替えるための手法です。

一般的なソートアルゴリズム：

• バブルソート
• 選択ソート
• 挿入ソート
• クイックソート

ここでは、初心者向けのバブルソートを中心に解説します。

2. バブルソートの基本概念

バブルソートは、隣接する要素を比較し、必要に応じて入れ替えることで配列をソートするアルゴリズムです。

アルゴリズムの概要：

1. 配列を順番に走査します。
2. 隣接する2つの要素を比較し、順序が正しくない場合に入れ替えます。
3. これを配列全体で繰り返します。

3. バブルソートの実装例

例：昇順にソートするバブルソート

#include <stdio.h>

void bubbleSort(int arr[], int size) {
    for (int i = 0; i < size - 1; i++) {
        for (int j = 0; j < size - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // 値を交換
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

int main() {
    int numbers[] = {64, 34, 25, 12, 22, 11, 90};
    int size = sizeof(numbers) / sizeof(numbers[0]);

    bubbleSort(numbers, size);

    printf("Sorted array: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", numbers[i]);
    }
    printf("\n");

    return 0;
}

解説：

• 内側のループで隣接する要素を比較し、大小関係が逆の場合に交換します。
• 外側のループが終わるごとに、最大値が配列の末尾に固定されます。

4. 最適化されたバブルソート

通常のバブルソートは非効率ですが、途中で交換が発生しない場合に終了するよう最適化できます。

例：最適化されたバブルソート

#include <stdio.h>

void optimizedBubbleSort(int arr[], int size) {
    int swapped;
    for (int i = 0; i < size - 1; i++) {
        swapped = 0;
        for (int j = 0; j < size - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = 1;
            }
        }
        if (!swapped) {
            break; // 交換がなければソート完了
        }
    }
}

int main() {
    int numbers[] = {64, 34, 25, 12, 22, 11, 90};
    int size = sizeof(numbers) / sizeof(numbers[0]);

    optimizedBubbleSort(numbers, size);

    printf("Optimized sorted array: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", numbers[i]);
    }
    printf("\n");

    return 0;
}

解説：

• swappedフラグを追加し、交換が発生しない場合に早期終了します。
• これにより、ソートが早く完了する場合のパフォーマンスが向上します。

5. 練習問題

以下の課題に挑戦し、バブルソートの理解を深めましょう。

1. 配列を降順にソートするバブルソートを実装してください。
2. バブルソートを使用して、配列の偶数要素だけを昇順に並び替えるプログラムを作成してください。
3. ユーザーが入力した配列をバブルソートでソートするプログラムを作成してください。

6. 練習問題の解答と解説

問1の解答

#include <stdio.h>

void bubbleSortDescending(int arr[], int size) {
    for (int i = 0; i < size - 1; i++) {
        for (int j = 0; j < size - i - 1; j++) {
            if (arr[j] < arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

int main() {
    int numbers[] = {64, 34, 25, 12, 22, 11, 90};
    int size = sizeof(numbers) / sizeof(numbers[0]);

    bubbleSortDescending(numbers, size);

    printf("Descending sorted array: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", numbers[i]);
    }
    printf("\n");

    return 0;
}

7. まとめ

バブルソートは、シンプルで理解しやすいソートアルゴリズムです。最適化や他のソートアルゴリズムと比較して、用途に応じて使い分けることを学びましょう。