C言語でマージソートを使って配列をソートするプログラムの作成方法

配列（アレイ）とは、共通の名前を共有する関連性のあるデータ項目の集まりです。配列内の特定の値は、「添字（インデックス番号）」によって識別されます。

配列の宣言

配列を宣言するための構文は、次のとおりです。

datatype array_name [size];

たとえば、次のように宣言します。

float marks [50];

この宣言により、「marks」はfloat型の要素を50個格納できる配列として定義されます。

int number[10];

この宣言により、「number」は整数定数を最大10個まで格納できる配列として定義されます。

配列の各要素は「配列インデックス（添字）」を使って識別され、インデックスを指定するだけで目的の要素へ簡単にアクセスできます。

マージソートとは

マージソートは「分割統治法」と呼ばれる手法に基づくソートアルゴリズムです。配列を半分ずつ再帰的に分割していき、要素が1つになった状態から、整列しながら統合（マージ）していくことで、全体を昇順に並べ替えます。計算量はO(n log n)であり、バブルソートなどの単純なアルゴリズムと比べて、大量のデータに対しても効率的かつ安定した性能を発揮します。

マージソートのロジック

マージソートで使用するロジックは、次のとおりです。

void MergeSort(int *array, int left, int right){
    int middle = (left+right)/2;
    if(left<right){
        // 左側の部分をソート
        MergeSort(array, left, middle);
        // 右側の部分をソート
        MergeSort(array, middle + 1, right);
        // 2つの部分をマージ
        Merge(array, left, middle, right);
    }
}

マージ処理のロジック

分割されたすべての要素を統合するロジックは、次のとおりです。

void Merge(int *array, int left, int middle, int right){
    int tmp[right - left + 1];
    int pos = 0, leftposition = left, rightposition = middle + 1;
    while (leftposition <= middle && rightposition <= right){
        if (array[leftposition] < array[rightposition]){
            tmp[pos++] = array[leftposition++];
        }else{
            tmp[pos++] = array[rightposition++];
        }
    }
    while (leftposition <= middle)
        tmp[pos++] = array[leftposition++];
    while (rightposition <= right)
        tmp[pos++] = array[rightposition++];
    int i;
    for (i = 0; i < pos; i++){
        array[i + left] = tmp[i];
    }
    return;
}

プログラム全体

以下は、マージソートを実装したC言語の完全なプログラムです。

#include <stdio.h>
void Merge(int * , int , int , int );
void MergeSort(int *array, int left, int right){
    int middle = (left+right)/2;
    if(left<right){
        // 左側の部分をソート
        MergeSort(array, left, middle);
        // 右側の部分をソート
        MergeSort(array, middle + 1, right);
        // 2つの部分をマージ
        Merge(array, left, middle, right);
    }
}
void Merge(int *array, int left, int middle, int right){
    int tmp[right - left + 1];
    int pos = 0, leftposition = left, rightposition = middle + 1;
    while (leftposition <= middle && rightposition <= right){
        if (array[leftposition] < array[rightposition]){
            tmp[pos++] = array[leftposition++];
        }
        else{
            tmp[pos++] = array[rightposition++];
        }
    }
    while (leftposition <= middle)
        tmp[pos++] = array[leftposition++];
    while (rightposition <= right)
        tmp[pos++] = array[rightposition++];
    int i;
    for (i = 0; i < pos; i++){
        array[i + left] = tmp[i];
    }
    return;
}
int main(){
    int size;
    printf("\n enter size of array:");
    scanf("%d", &size);
    int array[size];
    int i, j, k;
    printf("\n enter the elements in an array:");
    for (i = 0; i < size; i++){
        scanf("%d", &array[i]);
    }
    MergeSort(array, 0, size - 1);// ソート関数の呼び出し
    for (i = 0; i< size; i++){
        printf("%d ", array[i]);
    }
    printf("\n");
    return 0;
}

実行結果

上記のプログラムをコンパイルして実行すると、次のような出力が得られます。

enter size of array:10
enter the elements in an array:
2
-10
34
-3
45
67
-89
34
23
67
-89 -10 -3 2 23 34 34 45 67 67

このように、負の値を含む入力された10個の整数が、昇順に正しく並べ替えられていることが確認できます。マージソートは再帰的な構造を理解する絶好の題材でもあるため、ぜひ自分の手でコードを動かしながら挙動を確かめてみてください。