【C言語】マージソートとは?プログラムの書き方や仕組みを解説

目次から探す

マージソートの概要

マージソートは、効率的なソートアルゴリズムの一つです。

データを分割し、それぞれをソートしてから結合することで、全体をソートします。

マージソートは、再帰的なアプローチを取るため、分割統治法と呼ばれる手法に基づいています。

マージソートの特徴

マージソートの特徴は以下の通りです。

  • 安定なソートアルゴリズムであるため、同じ値を持つ要素の順序が変わることはありません。
  • データの分割と結合の過程で、追加のメモリを必要とするため、ソート対象のデータ量が大きい場合にはメモリ使用量に注意が必要です。

マージソートの利点

マージソートの利点は以下の通りです。

  • データの分割と結合の過程で、比較回数が最小限に抑えられるため、効率的なソートが可能です。
  • データの分割が再帰的に行われるため、ソート対象のデータがソート済みであっても、効率的に処理することができます。

マージソートの欠点

マージソートの欠点は以下の通りです。

  • 追加のメモリを必要とするため、ソート対象のデータ量が大きい場合にはメモリ使用量に注意が必要です。
  • 分割と結合の過程で、データのコピーが発生するため、処理速度が遅くなる可能性があります。

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

マージソートの手順

マージソートの手順は以下の通りです。

  1. ソート対象のデータを分割します。

データの中央を基準に、左側と右側に分割します。

  1. 分割したデータそれぞれに対して、再帰的にマージソートを適用します。
  2. 分割されたデータを結合します。

結合する際には、比較しながら小さい順に結合していきます。

マージソートの実装例

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

#include <stdio.h>
void merge(int arr[], int left[], int leftSize, int right[], int rightSize) {
    int i = 0, j = 0, k = 0;
    while (i < leftSize && j < rightSize) {
        if (left[i] <= right[j]) {
            arr[k++] = left[i++];
        } else {
            arr[k++] = right[j++];
        }
    }
    while (i < leftSize) {
        arr[k++] = left[i++];
    }
    while (j < rightSize) {
        arr[k++] = right[j++];
    }
}
void mergeSort(int arr[], int size) {
    if (size < 2) {
        return;
    }
    int mid = size / 2;
    int left[mid];
    int right[size - mid];
    for (int i = 0; i < mid; i++) {
        left[i] = arr[i];
    }
    for (int i = mid; i < size; i++) {
        right[i - mid] = arr[i];
    }
    mergeSort(left, mid);
    mergeSort(right, size - mid);
    merge(arr, left, mid, right, size - mid);
}
int main() {
    int arr[] = {5, 2, 8, 3, 1};
    int size = sizeof(arr) / sizeof(arr[0]);
    mergeSort(arr, size);
    printf("Sorted array: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

上記のコードでは、merge関数で2つの配列をマージし、mergeSort関数で再帰的にマージソートを行っています。

最後に、ソートされた配列を出力しています。

Sorted array: 1 2 3 5 8 

目次から探す