【C言語】乱数の配列をバブルソートする方法を解説

2023-09-102024-07-24

この記事では、C言語を使って乱数の配列を作成し、それをバブルソートという方法で並べ替える方法を学びます。

バブルソートの基本的な考え方やアルゴリズム、乱数の生成方法についても詳しく解説しますので、プログラミング初心者の方でも理解しやすい内容になっています。

これを通じて、ソートアルゴリズムの基本やC言語の使い方を身につけることができます。

目次から探す

バブルソートとは

バブルソートは、配列やリストの要素を並べ替えるためのシンプルなソートアルゴリズムの一つです。

このアルゴリズムは、隣接する要素を比較し、順序が逆であれば交換することを繰り返すことで、最終的に整列された配列を得ることができます。

バブルソートはその名の通り、要素が「泡」のように浮かび上がる様子から名付けられました。

バブルソートの基本概念

バブルソートの基本的な考え方は、配列の中の隣接する要素を比較し、必要に応じて交換することです。

この操作を配列の全ての要素に対して繰り返すことで、最も大きな要素が配列の末尾に移動し、次第に整列されていきます。

具体的には、以下のような手順で進行します。

配列の最初の要素から始め、隣接する2つの要素を比較します。
もし前の要素が後の要素より大きければ、2つの要素を交換します。
次の要素に移動し、再び隣接する要素を比較します。
配列の最後までこの操作を繰り返します。
1回のパスが終わったら、再度最初から繰り返します。

この操作を配列が整列されるまで続けます。

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

バブルソートのアルゴリズムは、以下のように表現できます。

配列の長さを取得します。
外側のループを配列の長さ-1回繰り返します。
内側のループを配列の長さ-1回繰り返し、隣接する要素を比較します。
比較した要素が逆順であれば、交換します。
内側のループが終わったら、外側のループに戻ります。

このアルゴリズムは非常に直感的で理解しやすいですが、効率的ではありません。

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

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

これは、nが配列の要素数であることを意味します。

最良の場合(すでに整列されている場合)でもO(n)となりますが、一般的にはO(n^2)と考えられます。

このため、バブルソートは小規模なデータセットには適していますが、大規模なデータセットには他の効率的なソートアルゴリズム(例えば、クイックソートやマージソート)を使用することが推奨されます。

C言語における乱数の生成

C言語では、乱数を生成するために標準ライブラリの <stdlib.h> を使用します。

このライブラリには、乱数を生成するための関数が含まれており、プログラム内で簡単に乱数を扱うことができます。

乱数生成のためのライブラリ

乱数を生成するためには、まず <stdlib.h> ヘッダファイルをインクルードする必要があります。

このライブラリには、乱数生成に必要な関数が含まれています。

特に、rand()関数と srand()関数がよく使用されます。

rand(): 0からRAND_MAX(通常は32767)までの整数の乱数を生成します。
srand(unsigned int seed): 乱数生成の初期化を行います。

引数に与えた値をシードとして使用し、同じシードを与えると同じ乱数列が生成されます。

乱数の生成方法

乱数を生成する基本的な流れは以下の通りです。

srand() を使ってシードを設定します。

通常、現在の時刻をシードとして使用することが一般的です。

rand() を呼び出して乱数を生成します。

以下は、乱数を生成する簡単な例です。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main() {
    // 現在の時刻をシードとして設定
    srand((unsigned int)time(NULL));
    // 乱数を生成して表示
    for (int i = 0; i < 5; i++) {
        int random_number = rand();
        printf("乱数 %d: %d\n", i + 1, random_number);
    }
    return 0;
}

このプログラムを実行すると、毎回異なる乱数が生成されます。

乱数の範囲設定

rand()関数は、0からRAND_MAXまでの整数を生成しますが、特定の範囲の乱数が必要な場合は、生成した乱数を適切に変換する必要があります。

例えば、1から100までの乱数を生成したい場合、次のようにします。

int lower = 1; // 下限
int upper = 100; // 上限
int random_number = (rand() % (upper - lower + 1)) + lower;

この式では、rand() % (upper - lower + 1) によって、0から (upper – lower) までの乱数を生成し、最後に lower を加えることで、1から100の範囲に調整しています。

このようにして、C言語では簡単に乱数を生成し、必要な範囲に設定することができます。

次に、生成した乱数を用いて配列を作成し、バブルソートを実行する方法について解説します。

乱数の配列を作成する

乱数を用いた配列を作成することは、プログラミングにおいて非常に重要なスキルです。

ここでは、C言語を使って乱数の配列を作成する方法を詳しく解説します。

配列の宣言と初期化

まず、配列を使用するためには、その配列を宣言し、必要に応じて初期化する必要があります。

C言語では、配列の宣言は次のように行います。

#include <stdio.h>
#define SIZE 10  // 配列のサイズを定義
int main() {
    int array[SIZE];  // 整数型の配列を宣言
    // 配列の初期化は後で行います
    return 0;
}

上記のコードでは、SIZEというマクロを使って配列のサイズを10に設定しています。

これにより、arrayという名前の整数型配列を宣言しました。

乱数を用いた配列の生成

次に、乱数を生成して配列に格納します。

C言語では、stdlib.hライブラリを使用して乱数を生成します。

以下のコードでは、乱数を生成し、配列に格納する方法を示します。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 10  // 配列のサイズを定義
int main() {
    int array[SIZE];  // 整数型の配列を宣言
    // 乱数の種を初期化
    srand(time(NULL));
    // 乱数を生成して配列に格納
    for (int i = 0; i < SIZE; i++) {
        array[i] = rand() % 100;  // 0から99の乱数を生成
    }
    return 0;
}

このコードでは、srand(time(NULL));を使って乱数の種を初期化しています。

これにより、プログラムを実行するたびに異なる乱数が生成されます。

rand() % 100は、0から99の範囲の乱数を生成する方法です。

配列の内容の表示

最後に、生成した乱数の配列の内容を表示します。

以下のコードを追加することで、配列の内容をコンソールに出力できます。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 10  // 配列のサイズを定義
int main() {
    int array[SIZE];  // 整数型の配列を宣言
    // 乱数の種を初期化
    srand(time(NULL));
    // 乱数を生成して配列に格納
    for (int i = 0; i < SIZE; i++) {
        array[i] = rand() % 100;  // 0から99の乱数を生成
    }
    // 配列の内容を表示
    printf("生成された乱数の配列:\n");
    for (int i = 0; i < SIZE; i++) {
        printf("%d ", array[i]);  // 各要素を表示
    }
    printf("\n");  // 改行
    return 0;
}

このコードを実行すると、生成された乱数の配列がコンソールに表示されます。

例えば、次のような出力が得られるかもしれません。

生成された乱数の配列:
23 45 67 12 89 34 56 78 90 11

これで、乱数の配列を作成し、その内容を表示する方法が理解できたと思います。

次のステップでは、この乱数の配列をバブルソートでソートする方法を学びます。

バブルソートの実装

バブルソートは、隣接する要素を比較し、順序が逆であれば交換することを繰り返すことで、配列をソートするシンプルなアルゴリズムです。

ここでは、C言語を用いてバブルソートを実装する方法を解説します。

バブルソート関数の定義

まず、バブルソートを実行するための関数を定義します。

この関数は、整数型の配列とそのサイズを引数として受け取ります。

以下のコードは、バブルソート関数の基本的な定義です。

#include <stdio.h>
// バブルソート関数の定義
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            // 隣接する要素を比較し、順序が逆であれば交換
            if (arr[j] > arr[j + 1]) {
                // 要素の交換
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

この関数では、外側のループが全体のパスを管理し、内側のループが隣接する要素を比較して交換します。

これにより、最も大きな要素が配列の最後に「バブルアップ」します。

ソート処理の実装

次に、実際に乱数の配列を生成し、先ほど定義したバブルソート関数を呼び出してソートを行います。

以下のコードは、乱数の配列を生成し、バブルソートを実行する全体のプログラムです。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// バブルソート関数の定義
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}
// 配列の内容を表示する関数
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}
int main() {
    int n = 10; // 配列のサイズ
    int arr[n];
    // 乱数の初期化
    srand(time(0));
    // 乱数を用いた配列の生成
    for (int i = 0; i < n; i++) {
        arr[i] = rand() % 100; // 0から99の乱数
    }
    printf("ソート前の配列: ");
    printArray(arr, n);
    // バブルソートの実行
    bubbleSort(arr, n);
    printf("ソート後の配列: ");
    printArray(arr, n);
    return 0;
}

このプログラムでは、まず乱数を生成して配列に格納し、ソート前の配列を表示します。

その後、bubbleSort関数を呼び出して配列をソートし、ソート後の配列を表示します。

ソート結果の表示

プログラムを実行すると、ソート前とソート後の配列が表示されます。

例えば、以下のような出力が得られるでしょう。

ソート前の配列: 34 7 23 32 5 62 32 12 45 78 
ソート後の配列: 5 7 12 23 32 32 34 45 62 78

このように、バブルソートを用いることで、乱数の配列を簡単にソートすることができます。

バブルソートはシンプルで理解しやすいアルゴリズムですが、大規模なデータセットに対しては効率が悪いため、他のソートアルゴリズムと比較して使用することが重要です。

実際のコード例

完全なプログラムのコード

以下に、乱数の配列を生成し、バブルソートを用いてソートするC言語の完全なプログラムを示します。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 10  // 配列のサイズを定義
// バブルソート関数の宣言
void bubbleSort(int arr[], int n);
// 配列の内容を表示する関数の宣言
void printArray(int arr[], int n);
int main() {
    int arr[SIZE];  // 整数型の配列を宣言
    srand(time(NULL));  // 乱数の初期化
    // 乱数を用いて配列を生成
    for (int i = 0; i < SIZE; i++) {
        arr[i] = rand() % 100;  // 0から99の乱数を生成
    }
    printf("ソート前の配列:\n");
    printArray(arr, SIZE);  // ソート前の配列を表示
    bubbleSort(arr, SIZE);  // バブルソートを実行
    printf("ソート後の配列:\n");
    printArray(arr, SIZE);  // ソート後の配列を表示
    return 0;
}
// バブルソートの実装
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // 要素の入れ替え
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}
// 配列の内容を表示する関数
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

コードの解説

このプログラムは、乱数を生成して配列に格納し、その配列をバブルソートでソートするものです。

以下に各部分の解説を行います。

ライブラリのインクルード:

#include <stdio.h>: 標準入出力ライブラリをインクルードします。

これにより、printfやscanfなどの関数が使用可能になります。

#include <stdlib.h>: 標準ライブラリをインクルードします。

乱数生成に必要なrandやsrand関数が含まれています。

#include <time.h>: 時間に関する関数を使用するためのライブラリです。

乱数の初期化に現在の時間を利用します。

定数の定義:

#define SIZE 10: 配列のサイズを10に設定しています。

この値を変更することで、生成する配列のサイズを簡単に変更できます。

関数の宣言:

void bubbleSort(int arr[], int n): バブルソートを実行する関数の宣言です。
void printArray(int arr[], int n): 配列の内容を表示するための関数の宣言です。

main関数:

srand(time(NULL));: 乱数の初期化を行います。

これにより、プログラムを実行するたびに異なる乱数が生成されます。

ループを使って、0から99の範囲の乱数を生成し、配列に格納します。
printArray関数を呼び出して、ソート前の配列を表示します。
bubbleSort関数を呼び出して、配列をソートします。
再度printArray関数を呼び出して、ソート後の配列を表示します。

バブルソート関数:

2重ループを使用して、隣接する要素を比較し、必要に応じて入れ替えを行います。

これを繰り返すことで、配列がソートされます。

配列表示関数:

ループを使って配列の各要素を表示します。

このプログラムを実行すると、乱数で生成された配列がソートされる様子を確認できます。

バブルソートの改善点

バブルソートはシンプルで理解しやすいアルゴリズムですが、効率が悪いため、特に大きなデータセットに対しては改善が必要です。

ここでは、バブルソートの最適化手法と他のソートアルゴリズムとの比較について解説します。

最適化の手法

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

以下に代表的なものを紹介します。

フラグを用いた最適化

バブルソートでは、配列の最後までスワップが行われると、すでにソートされていることがわかります。

このため、スワップが行われなかった場合は、ソートが完了したと判断し、ループを終了することができます。

これにより、無駄な比較を減らすことができます。

void optimizedBubbleSort(int arr[], int n) {
       int i, j, temp;
       int swapped;
       for (i = 0; i < n - 1; i++) {
           swapped = 0; // スワップフラグの初期化
           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;
                   swapped = 1; // スワップが行われた
               }
           }
           // スワップが行われなければ、ソート完了
           if (swapped == 0) {
               break;
           }
       }
   }