MENU
  1. ホーム
  2. C言語
  3. C言語でのマージソートを徹底解説：実装方法から応用例まで

C言語でのマージソートを徹底解説：実装方法から応用例まで

C言語

C言語のマージソートは、効率的で安定したソートアルゴリズムとして広く使われています。本記事では、マージソートの基本概念から始め、実装方法をステップバイステップで解説します。さらに、応用例や演習問題を通じて、マージソートの理解を深めることを目指します。プログラミング初心者から中級者まで、C言語でのソートアルゴリズムの知識を強化したい方に最適な内容です。

目次

マージソートとは何か

マージソートは、分割統治法を用いたソートアルゴリズムの一つで、安定ソートに分類されます。このアルゴリズムは、データを再帰的に分割し、小さな部分に分けた後、それらを整列させながら結合することで全体をソートします。特に、大規模なデータセットに対して効率的で、時間計算量がO(n log n)と安定している点が特徴です。

マージソートのアルゴリズム

マージソートのアルゴリズムは、以下のステップで構成されます：

分割

配列を半分に分割し、分割されたそれぞれの部分を再帰的に分割します。これを、配列が一つの要素になるまで繰り返します。

統治

分割された小さな配列をそれぞれソートします。最終的には、分割されたすべての小さな配列がソートされた状態になります。

結合

ソートされた小さな配列を順に結合し、一つの大きなソートされた配列にします。結合の過程で、各要素を比較しながら正しい順序で配置していきます。

このプロセスを視覚化すると、次のようになります：

  1. 初期配列：[8, 3, 1, 7, 0, 10, 2]
  2. 分割：
    • [8, 3, 1, 7] と [0, 10, 2]
    • [8, 3] と [1, 7] と [0, 10] と [2]
    • [8] と [3] と [1] と [7] と [0] と [10] と [2]
  3. 統治：
    • [3, 8] と [1, 7] と [0, 10] と [2]
  4. 結合：
    • [1, 3, 7, 8] と [0, 2, 10]
    • [0, 1, 2, 3, 7, 8, 10]

このようにして、元の配列がソートされます。

マージソートの実装方法

C言語でのマージソートの実装方法を以下に示します。実装は主に分割、統治、結合の3つの部分から構成されます。

コード例

以下は、C言語でのマージソートの実装例です。

#include <stdio.h>
#include <stdlib.h>

// 配列をマージする関数
void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    int* L = (int*)malloc(n1 * sizeof(int));
    int* R = (int*)malloc(n2 * sizeof(int));

    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }

    free(L);
    free(R);
}

// マージソートのメイン関数
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        merge(arr, left, mid, right);
    }
}

// 配列を表示する関数
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int arr_size = sizeof(arr) / sizeof(arr[0]);

    printf("Given array is \n");
    printArray(arr, arr_size);

    mergeSort(arr, 0, arr_size - 1);

    printf("\nSorted array is \n");
    printArray(arr, arr_size);
    return 0;
}

説明

このプログラムでは、mergeSort関数が再帰的に配列を分割し、merge関数が分割された配列をソートしながら結合します。main関数では、ソート対象の配列を定義し、mergeSort関数を呼び出してソートを実行します。結果として、ソートされた配列が出力されます。

マージソートの再帰的な実装

再帰を用いたマージソートの実装方法について詳しく説明します。再帰的なマージソートは、配列を再帰的に分割し、結合しながらソートを行うアルゴリズムです。

再帰的な分割と統治

再帰的なマージソートは以下の手順で動作します：

  1. 配列を半分に分割する。
  2. 左半分と右半分それぞれに対して再帰的にマージソートを適用する。
  3. ソートされた左半分と右半分をマージして一つのソートされた配列にする。

再帰的な分割と統治の流れを具体的にコードで見てみましょう。

再帰的なマージソートのコード例

以下のコードは、再帰的なマージソートの実装を示しています。

#include <stdio.h>
#include <stdlib.h>

// 配列をマージする関数
void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    int* L = (int*)malloc(n1 * sizeof(int));
    int* R = (int*)malloc(n2 * sizeof(int));

    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }

    free(L);
    free(R);
}

// 再帰的なマージソートのメイン関数
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        merge(arr, left, mid, right);
    }
}

// 配列を表示する関数
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int arr_size = sizeof(arr) / sizeof(arr[0]);

    printf("Given array is \n");
    printArray(arr, arr_size);

    mergeSort(arr, 0, arr_size - 1);

    printf("\nSorted array is \n");
    printArray(arr, arr_size);
    return 0;
}

コードの詳細

  1. mergeSort関数は、配列を分割し、再帰的に自身を呼び出してソートを行います。
  2. merge関数は、分割された配列をマージしてソートされた配列を生成します。
  3. main関数で、ソート対象の配列を定義し、mergeSort関数を呼び出してソートを実行します。

この再帰的な実装により、マージソートは効率的かつ簡潔に実現されます。

マージソートの非再帰的な実装

非再帰的なマージソートは、再帰を使わずにループを用いてソートを行う方法です。この方法は、スタックオーバーフローのリスクを軽減し、再帰呼び出しのオーバーヘッドを回避することができます。

非再帰的な分割と統治

非再帰的なマージソートは、一定のサイズで部分配列をソートし、次第に大きなサイズで部分配列をマージしていく方法です。

  1. 最初は、各部分配列のサイズを1に設定します。
  2. 部分配列のサイズを2倍にしながら、部分配列を順にマージしていきます。
  3. 配列全体がソートされるまでこの過程を繰り返します。

非再帰的なマージソートのコード例

以下は、非再帰的なマージソートの実装例です。

#include <stdio.h>
#include <stdlib.h>

// 配列をマージする関数
void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    int* L = (int*)malloc(n1 * sizeof(int));
    int* R = (int*)malloc(n2 * sizeof(int));

    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }

    free(L);
    free(R);
}

// 非再帰的なマージソートのメイン関数
void iterativeMergeSort(int arr[], int n) {
    int curr_size; // 現在のサブ配列サイズ
    int left_start; // サブ配列の左端

    for (curr_size = 1; curr_size <= n - 1; curr_size = 2 * curr_size) {
        for (left_start = 0; left_start < n - 1; left_start += 2 * curr_size) {
            int mid = left_start + curr_size - 1;
            int right_end = (left_start + 2 * curr_size - 1 < n - 1) ? (left_start + 2 * curr_size - 1) : (n - 1);

            merge(arr, left_start, mid, right_end);
        }
    }
}

// 配列を表示する関数
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int arr_size = sizeof(arr) / sizeof(arr[0]);

    printf("Given array is \n");
    printArray(arr, arr_size);

    iterativeMergeSort(arr, arr_size);

    printf("\nSorted array is \n");
    printArray(arr, arr_size);
    return 0;
}

コードの詳細

  1. iterativeMergeSort関数は、非再帰的な方法でマージソートを実装します。サブ配列のサイズを1から始め、2倍に増やしながらソートを進めます。
  2. merge関数は、再帰的な実装と同様に部分配列をマージします。
  3. main関数で、ソート対象の配列を定義し、iterativeMergeSort関数を呼び出してソートを実行します。

この非再帰的な実装により、再帰呼び出しのオーバーヘッドを回避し、効率的なマージソートを実現できます。

マージソートの効率性

マージソートは、多くのソートアルゴリズムと比較して効率的で安定したソート方法です。その効率性について、時間計算量と空間計算量の観点から詳しく見ていきます。

時間計算量

マージソートの時間計算量は、常にO(n log n)です。この計算量は、すべてのケース（最良、最悪、平均）において一定です。これは、配列を再帰的に分割していく回数がlog n回であり、各分割ごとに要素を比較してマージする操作がn回行われるためです。

ケース時間計算量
最良O(n log n)
最悪O(n log n)
平均O(n log n)

空間計算量

マージソートの空間計算量はO(n)です。これは、ソートする配列とは別に、同じサイズの補助配列を必要とするためです。この点で、マージソートはインプレースソート（追加のメモリをほとんど必要としないソート）ではありません。

ケース空間計算量
すべてのケースO(n)

他のソートアルゴリズムとの比較

マージソートは、特に大規模なデータセットに対して効率的であり、クイックソートやバブルソート、挿入ソートなどと比較しても優れたパフォーマンスを発揮します。

  • クイックソート: 平均的にはO(n log n)の時間計算量を持ちますが、最悪の場合はO(n^2)となる可能性があります。マージソートはこの点でより安定しています。
  • バブルソート: 時間計算量がO(n^2)であり、大規模なデータセットには向いていません。
  • 挿入ソート: 小規模なデータセットには効率的ですが、時間計算量がO(n^2)であるため、大規模なデータには不向きです。

このように、マージソートはその安定性と効率性から、多くの場面で有用なソートアルゴリズムとして採用されています。

マージソートの応用例

マージソートはその効率性と安定性から、様々な分野で応用されています。以下にいくつかの具体的な応用例を紹介します。

大規模データのソート

マージソートは、大規模なデータセットを効率的にソートするのに適しています。例えば、データベースのクエリ結果のソートや、ログファイルの整列などに使用されます。時間計算量がO(n log n)で安定しているため、他のソートアルゴリズムよりも予測可能なパフォーマンスを発揮します。

分散システムでのソート

マージソートは、分割統治法を用いているため、分散システムでのソートに適しています。各ノードで部分的にソートを行い、最後にマージすることで全体をソートします。これは、MapReduceフレームワークなどで利用されており、大規模データの処理において重要な役割を果たします。

外部ソート

メインメモリに収まりきらない大規模なデータをソートする外部ソートアルゴリズムでも、マージソートはよく使われます。データを小さな部分に分割してディスクに保存し、これをソートしてからマージしていく方法です。この手法により、メモリ制約を超える大規模なデータセットのソートが可能になります。

ファイルのマージ操作

複数のソート済みファイルを一つのソートされたファイルに統合する際にも、マージソートの手法が使われます。例えば、ログファイルやリストを統合する場合などに利用されます。この操作は、各ファイルから最小の要素を選択してマージしていくため、効率的に行うことができます。

テキスト処理

テキストファイルの行をソートする場合や、辞書順に単語を並べ替える場合など、文字列データのソートにもマージソートは利用されます。これにより、辞書やインデックスの生成が効率的に行われます。

これらの応用例からもわかるように、マージソートはその効率性と汎用性から、さまざまな場面で重要な役割を果たしています。

マージソートの演習問題

マージソートの理解を深めるために、以下の演習問題を試してみてください。これらの問題を解くことで、マージソートの実装とその応用についての知識を強化することができます。

演習問題1: 基本的なマージソートの実装

与えられた整数配列をマージソートを用いてソートするプログラムを実装してください。以下の配列を使用してください：

int arr[] = {38, 27, 43, 3, 9, 82, 10};

この配列をソートし、結果を出力するプログラムを作成してください。

演習問題2: 非再帰的なマージソート

非再帰的なマージソートのアルゴリズムを実装してください。以下の配列を使用してソートを行ってください：

int arr[] = {15, 3, 2, 1, 9, 5, 7, 8, 6};

非再帰的な方法でソートを行い、結果を出力するプログラムを作成してください。

演習問題3: 部分配列のソート

以下の配列の一部（インデックス2からインデックス6まで）をマージソートを使用してソートしてください：

int arr[] = {10, 7, 8, 5, 6, 9, 2, 3};

部分配列をソートし、結果を出力するプログラムを作成してください。

演習問題4: 大規模データのソート

ランダムに生成された1000個の整数を含む配列をマージソートを用いてソートしてください。ソート前後の配列を出力するプログラムを作成してください。

#include <stdlib.h>
#include <time.h>

int arr[1000];
srand(time(0));
for (int i = 0; i < 1000; i++) {
    arr[i] = rand() % 10000;
}

演習問題5: ファイルから読み込んだデータのソート

テキストファイルから整数を読み込み、それをマージソートを用いてソートするプログラムを作成してください。ソート後の結果を別のファイルに書き出してください。

#include <stdio.h>

FILE *inputFile = fopen("input.txt", "r");
FILE *outputFile = fopen("output.txt", "w");

これらの演習問題を解くことで、マージソートの理論だけでなく、実践的なスキルも身につけることができます。各問題に対して、自分なりのソリューションを考え、実装してみてください。

まとめ

マージソートは、分割統治法を用いた効率的で安定したソートアルゴリズムです。C言語による実装方法を通じて、その基本的な仕組みから再帰的および非再帰的な実装、応用例、効率性について詳しく学びました。特に、大規模データのソートや分散システムでの利用に適しており、実践的な応用例や演習問題を通じて理解を深めることができました。マージソートの特性と実装方法をマスターすることで、さまざまな場面で効率的なデータ処理が可能となります。

C言語
プログラミング C言語 ソートアルゴリズム マージソート 学習

コメント

コメントする

目次