【C言語】マージソートによる配列データの整列

ある程度プログラミングに慣れた人向けの練習問題の一つとして、整列アルゴリズム（ソート）の実装があります。

この記事では、マージソートを用いた配列データの整列をプログラムに実装する方法について解説しています。

マージソートの概要

プログラムを作成する前に、マージソートについての簡単な説明を行います。

マージソートとは、配列データの要素を整列させる整列アルゴリズム（ソート）の一つです。

アルゴリズム

マージソートでは、「整列の対象となる配列を限界まで分割し、整列させながら統合する」という操作を行います。

再帰的な表現を用いることで簡単にプログラムが作成することが可能です。

計算量

マージソートの計算量は、どのような配列データが対象であってもO記法でO(NlogN)以下となります。

ただし、対象の配列データに比例した作業領域を別途用意する必要があるため、領域計算量はO(N)です。

実際にプログラムを作成してみる

前述のアルゴリズムに従ってプログラムを作成します。

プログラム作成の手順

プログラム作成の手順は以下の通りです。

実装例

上記の手順に従ってプログラムを作成します。使用する言語はC言語です。

#include <stdio.h>

void merge_sort(int data[], int start, int end){

  int i, j, k, mid;
  int maxv = 10000;  /* 充分に大きな値 */
  int temp_a[end+1], temp_b[end+1];

  if(start >= end){
    return;
  }
  mid = (start + end) / 2;
  merge_sort(data, start, mid);
  merge_sort(data, mid+1, end);

  j = 0;
  for(i=start; i<=mid; i++){
    temp_a[j] = data[i];
    j += 1;
  }
  temp_a[j] = maxv;
  j = 0;
  for(i=mid+1; i<=end; i++){
    temp_b[j] = data[i];
    j += 1;
  }
  temp_b[j] = maxv;

  i = 0;
  j = 0;
  k = start;
  while(temp_a[i]!=maxv || temp_b[j]!=maxv){
    if(temp_a[i] <= temp_b[j]){
      data[k] = temp_a[i];
      i += 1;
    }else{
      data[k] = temp_b[j];
      j += 1;
    }
    k += 1;
  }
}

int main(void){

  int data[] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
  int n;

  /* 整列前のデータを表示する */
  printf("---merge sort---\nBefore : ");
  for(n=0; data[n]!='\0'; n++){
    printf("%d ", data[n]);
  }

  /* マージソートを用いてデータを整列する */
  merge_sort(data, 0, n);

  /* 整列後のデータを表示する */
  printf("\nAfter  : ");
  for(n=0; data[n]!='\0'; n++){
    printf("%d ", data[n]);
  }

  return 0;
}

このプログラムを実行すると以下の出力結果が得られます。

---merge sort---
Before : 9 8 7 6 5 4 3 2 1 
After  : 1 2 3 4 5 6 7 8 9 

この出力結果から無事にマージソートが実装できていることがわかります。

おすすめの記事

本記事を読まれた方には、以下の記事もおすすめします。

【中・上級者への道！】C言語の次に勉強するべきプログラミング言語は何？【オススメは○○】