C言語でのマージソート手法を説明する

並べ替えは、要素を昇順（または）降順で並べ替えるプロセスです。

並べ替えの種類

C言語には、次の5つの並べ替え手法があります-

• バブルソート（または）Exchangeソート
• 選択ソート
• 挿入ソート（または）線形ソート
• クイックソート（または）パーティション交換ソート
• マージソート（または）外部ソート

マージソート

マージソートは分割された征服方法です。配列を2つに分割し、再帰的に征服してマージ（結合）します。

以下に示す例を考えてみましょう-

ソートされていない配列を取得し、マージソート手法を適用して配列をソートします。

38、27、43、3、9、82、10

次に、以下に示すように並べ替えて配列を結合します-

例

以下は、マージソート手法を使用して要素をソートするCプログラムです-

#include <stdio.h>
#define max 10
int a[11] = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44, 0 };
int b[10];
void merging(int low, int mid, int high) {
   int l1, l2, i;
   for(l1 = low, l2 = mid + 1, i = low; l1 <= mid && l2 <= high; i++) {
      if(a[l1] <= a[l2])
         b[i] = a[l1++];
      else
         b[i] = a[l2++];
   }
   while(l1 <= mid)
      b[i++] = a[l1++];
   while(l2 <= high)
      b[i++] = a[l2++];
   for(i = low; i <= high; i++)
      a[i] = b[i];
   }
   void sort(int low, int high) {
      int mid;
      if(low < high) {
         mid = (low + high) / 2;
         sort(low, mid);
         sort(mid+1, high);
         merging(low, mid, high);
      } else {
      return;
   }
}
int main() {
   int i;
   printf("List before sorting\n");
   for(i = 0; i <= max; i++)
   printf("%d ", a[i]);
   sort(0, max);
   printf("\nList after sorting\n");
   for(i = 0; i <= max; i++)
   printf("%d ", a[i]);
}

出力

上記のプログラムを実行すると、次の出力が生成されます-

List before sorting
10 14 19 26 27 31 33 35 42 44 0
List after sorting
0 10 14 19 26 27 31 33 35 42 44