/***************************************
 * データ構造とアルゴリズム
 * レポート課題 1-1 
 * 選択ソート 時間測定プログラムのひな形
 ***************************************/
#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 の内容を昇順に整列させる．
   a: 対象の配列
   n: 配列の長さ
  ==============================================================*/
void selection_sort(int a[], int n)
{
  /* ------------------------
      この部分は自分で作ること
      ------------------------- */
}


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();
  selection_sort(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;
}