【C言語】選択ソートとバブルソートの違いについて解説

2023-09-102024-07-22

この記事では、C言語を使って「選択ソート」と「バブルソート」という2つの基本的なソートアルゴリズムについて学びます。

これらのアルゴリズムの基本原理、実装方法、特徴、そしてそれぞれの違いについて詳しく解説します。

プログラミング初心者でも理解しやすいように、サンプルコードとその実行結果も含めて説明しますので、ぜひ最後まで読んでみてください。

目次から探す

選択ソート(Selection Sort)

選択ソートの基本原理

選択ソートは、配列の中から最小(または最大)の要素を選び、それを配列の先頭に移動させることを繰り返すことで、配列を整列させるアルゴリズムです。

具体的には、以下の手順で動作します。

配列の中から最小の要素を見つける。
その最小の要素を配列の先頭の要素と交換する。
次に、先頭の要素を除いた残りの配列から最小の要素を見つけ、再び先頭の要素と交換する。
この手順を配列の最後まで繰り返す。

選択ソートの実装方法

選択ソートの実装は比較的簡単で、二重のループを使用して行います。

外側のループは配列の各要素を順に処理し、内側のループはその要素以降の部分から最小の要素を見つけます。

C言語での選択ソートのコード例

以下に、C言語での選択ソートの実装例を示します。

#include <stdio.h>
// 選択ソート関数
void selectionSort(int arr[], int n) {
    int i, j, min_idx, temp;
    // 配列の各要素を順に処理
    for (i = 0; i < n-1; i++) {
        // 最小要素のインデックスを見つける
        min_idx = i;
        for (j = i+1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        // 最小要素を先頭の要素と交換
        temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;
    }
}
// 配列を表示する関数
void printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}
// メイン関数
int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr)/sizeof(arr[0]);
    printf("元の配列: \n");
    printArray(arr, n);
    selectionSort(arr, n);
    printf("ソート後の配列: \n");
    printArray(arr, n);
    return 0;
}

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

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

選択ソートの時間計算量

選択ソートの時間計算量は、最悪の場合でも平均の場合でも O(n^2) です。

これは、配列の各要素に対して、残りの要素全てと比較するためです。

具体的には、n個の要素に対して (n-1) + (n-2) + … + 1 回の比較が行われます。

選択ソートの特徴

メモリ使用量

選択ソートはインプレースソートアルゴリズムであり、追加のメモリをほとんど使用しません。

つまり、入力配列の外に追加の配列を作成する必要がないため、メモリ使用量は O(1) です。

安定性

選択ソートは安定なソートアルゴリズムではありません。

安定なソートとは、同じ値の要素が元の順序を保つソートのことを指します。

選択ソートでは、同じ値の要素が元の順序を保たない場合があります。

例えば、同じ値の要素が異なる位置に移動することがあるためです。

選択ソートはそのシンプルさと直感的な動作から、教育目的や小規模なデータセットのソートに適していますが、大規模なデータセットのソートには他の効率的なアルゴリズム(例えばクイックソートやマージソート)を使用することが推奨されます。

バブルソート(Bubble Sort)

バブルソートの基本原理

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

名前の由来は、リストの中で最も大きな要素が「泡」のように上昇していく様子から来ています。

具体的には、リストの先頭から末尾まで順に隣接する要素を比較し、大小関係が逆であれば交換します。

この操作をリスト全体に対して繰り返し行うことで、リストがソートされます。

バブルソートの実装方法

バブルソートの実装は非常にシンプルです。

以下に基本的な手順を示します。

リストの先頭から末尾まで順に隣接する要素を比較する。
比較した要素の大小関係が逆であれば交換する。
リスト全体に対してこの操作を繰り返す。
リストがソートされるまで繰り返す。

C言語でのバブルソートのコード例

以下に、C言語でのバブルソートの実装例を示します。

#include <stdio.h>
// バブルソート関数
void bubbleSort(int arr[], int n) {
    int i, j, temp;
    for (i = 0; i < n-1; i++) {
        for (j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                // 要素を交換する
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}
// 配列を表示する関数
void printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}
int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr)/sizeof(arr[0]);
    printf("ソート前の配列: \n");
    printArray(arr, n);
    bubbleSort(arr, n);
    printf("ソート後の配列: \n");
    printArray(arr, n);
    return 0;
}

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

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

バブルソートの時間計算量

バブルソートの時間計算量は、最悪の場合と平均の場合で O(n^2) です。

これは、リストの全ての要素を比較し、必要に応じて交換するためです。

最良の場合でも O(n) となりますが、これはリストが既にソートされている場合に限ります。

バブルソートの特徴

メモリ使用量

バブルソートはインプレースソートアルゴリズムであり、追加のメモリをほとんど使用しません。

これは、要素の交換がリスト内で行われるためです。

安定性

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

これは、同じ値を持つ要素の相対的な順序がソート後も保持されることを意味します。

例えば、同じ値を持つ要素が複数存在する場合、元の順序が維持されます。

バブルソートはそのシンプルさから教育目的でよく使用されますが、実際のアプリケーションでは効率が低いため、他のソートアルゴリズムが好まれることが多いです。

選択ソートとバブルソートの比較

アルゴリズムの違い

選択ソートとバブルソートはどちらも基本的なソートアルゴリズムですが、その動作原理には明確な違いがあります。

選択ソート

配列の中から最小(または最大)の要素を見つけ、それを先頭の要素と交換します。

次に、先頭の要素を除いた部分配列の中から再び最小の要素を見つけ、それを次の位置の要素と交換します。

この操作を配列の最後まで繰り返します。

バブルソート

隣接する要素を比較し、順序が逆であれば交換します。

配列の末尾までこの操作を繰り返し、1回のパスで最大(または最小)の要素が末尾に移動します。

次に、末尾の要素を除いた部分配列で同じ操作を繰り返します。

実行時間の比較

選択ソートとバブルソートの実行時間は、どちらも最悪の場合で O(n^2) です。

しかし、実際の動作速度には違いがあります。

選択ソート:
常に O(n^2) の時間がかかります。

なぜなら、各要素に対して最小の要素を見つけるために残りの要素全てを比較する必要があるからです。

バブルソート:
最悪の場合 O(n^2) ですが、配列がほぼ整列されている場合には早く終了することがあります。

これは、バブルソートが途中で配列が整列されていることを検出できるためです。

メモリ使用量の比較

どちらのアルゴリズムもインプレースソートであり、追加のメモリをほとんど使用しません。

選択ソート:
追加のメモリ使用量は O(1) です。

要素の交換に必要な一時的な変数のみを使用します。

バブルソート:
こちらも追加のメモリ使用量は O(1) です。

要素の交換に必要な一時的な変数のみを使用します。

安定性の比較

ソートアルゴリズムの安定性は、同じ値の要素が元の順序を保つかどうかを指します。

選択ソート:
安定ではありません。

なぜなら、最小の要素を見つけた際に、元の順序を無視して交換を行うためです。

バブルソート:
安定です。

隣接する要素のみを交換するため、同じ値の要素が元の順序を保ちます。

実用性の比較

実際のプログラムでどちらのソートを使用するかは、具体的な要件によります。

以下のアルゴリズムの情報を表にまとめました：

スクロールできます

アルゴリズム名	特徴	適用場面	メリット	デメリット
選択ソート	シンプルで理解しやすいアルゴリズム。小規模なデータセットに適する。	安定性が必要ない場合。メモリ使用量を最小限に抑えたい場合。	メモリ使用量が少ない。	安定性がない。
バブルソート	シンプルで理解しやすいアルゴリズム。小規模なデータセットに適する。	データがほぼ整列されている場合。安定性が必要な場合。	データがほぼ整列されている場合に早く終了する可能性がある。	時間効率が悪い（大規模データセットには不適）。