/***************************************
 * データ構造とアルゴリズム
 * レポート課題 1-2 
 * マージソートのサンプルプログラム
 ***************************************/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>


/*========================================
  データを自動生成する
   a : 対象の配列
   x : データの種類（0: 逆順，1: ランダム）
   n : 配列の長さ
 =========================================*/
void set_data(int a[], int x, int n)
{
  int i;

  if ( x == 0 ){
    /* 最悪ケースとして逆順に並んでいるデータを生成する */
    for ( i = 0; i < n; i++ ){
      a[i] = n - i;
    }
  }
  else{
    /* 乱数を使ってランダムなデータを生成する */
    srand(time(NULL));
    for ( i = 0; i < n; i++ ){
      a[i] = rand();
    }
  }
}


/*==============================================================
  配列 a の内容が昇順に並んでいるかチェックする．
   a: 対象の配列
   n: 配列の長さ
   戻り値： 昇順に並んでいれば 1，そうでなければ 0
  ==============================================================*/
int check(int a[], int n)
{
  int i;

  for ( i = 0; i < n-1; i++ ){
    if ( a[i] > a[i+1] ){
      return 0;
    }
  }

  return 1;
}


/*========================================
  マージソートを実行する
    a : ソート対象の配列
    n : 配列の長さ
 ==========================================*/
void Msort(int a[], int n)
{
  int i, j, k, swap;
  int* part1 = calloc(n/2, sizeof(int));      /* 配列の前半部分用 */
  int* part2 = calloc(n-(n/2), sizeof(int));  /* 配列の後半部分用 */

  /* データが 1 個しかない場合 : そのまま終了 */
  if ( n == 1 ){
    return;
  }

  /* データが 2 個しかない場合: 直接比較して交換し，終了 */
  if ( n == 2 ){
    if ( a[0] > a[1] ){
      swap = a[0];
      a[0] = a[1];
      a[1] = swap;
    }
    return;
  }

  /* データが 3 個以上ある場合： */
  /* 前半部分と後半部分を切出して再帰呼出しを行う */
  for ( i = 0; i < n/2; i++ ){
    part1[i] = a[i];
  }
  for ( i = n/2; i < n; i++ ){
    part2[i-(n/2)] = a[i];
  }
  
  Msort(part1,n/2);
  Msort(part2,n-(n/2));

  /* 再帰呼出しによってソートされた 2 つの小配列を統合する */
  i = j = 0;
  for ( k = 0; k < n; k++ ){
    if ( i == n/2 ){
      a[k] = part2[j++];
    }
    else if ( j == n-(n/2) ){
      a[k] = part1[i++];
    }
    else if ( part1[i] < part2[j] ){
      a[k] = part1[i++];
    }
    else{
      a[k] = part2[j++];
    }
  }

  /* 再帰呼出しが終われば part1, part2 は不要なのでメモリを解放 */
  free(part1);
  free(part2);
}


int main(void)
{
  int n, x;
  int* a;
  clock_t start, end;

  /* 長さ n の配列 a を用意する */
  do{
    printf("データの個数を指定してください > ");
    scanf("%d", &n);
    a = calloc(n, sizeof(int));
    if ( a == NULL ){
      printf("配列のメモリ確保に失敗しました\n");
      printf("再設定をお願いします\n");
    }
  }
  while ( a == NULL );

  /* 最悪データまたはランダムデータを自動生成する */
  do{
    printf("自動生成するデータの種類を選択してください\n");
    printf("（0: 最悪データ，1:ランダムデータ）> ");
    scanf("%d", &x);
  }
  while ( x != 0 && x != 1 );
  set_data(a, x, n);
  
  /* 以上の設定を表示する */
  printf("データ数 = %d", n);
  if ( x == 0 ){
    printf(" (逆順データ)\n");
  }
  else{
    printf(" (ランダムデータ)\n");
  }

  printf("\n実行中 ... ");
  fflush(stdout);
  /* マージソートを実行し，ソーティングにかかる時間を測定する */
  start = clock();
  Msort(a, n);
  end = clock();

  /* ソーティング結果をチェック */
  if ( check(a, n) ){
    printf("OK: データは昇順に並んでいます\n");
  }
  else{
    printf("エラー: データは昇順に並んでいません！\n");
  }

  /* 時間を表示する */
  printf("\n実行時間 = %7.3f [秒]\n", (float)(end - start) / CLOCKS_PER_SEC);

  free(a);

  return 0;
}