/* sort0.c
 * ソートプログラミング演習 雛型プログラム
 */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>/* time関数に必要 */

#define N 8             /* データ個数 */

/**************************************************************/
/*** ここから、各ソートアルゴリズムで使用している細かな関数 ***/

int display = 0;        /* 表示非表示 */
typedef struct {
  int value;            /* 評価値 */
  double dummy;         /* その他の要素 */
} DATA;

DATA data[N * 2 + 1];   /* 仮置き場確保のため 2倍の領域確保+入れ替え場所 */

int move_count = 0;     /* 移動回数の評価 */
int compare_count = 0;  /* 比較回数の評価 */
int num = 0;

/* データの移動 dest -> src */
void move_data(int dest, int src) {
  move_count++;
  data[dest] = data[src];
  data[src].value = -1;  /* 見せるためだけ, 普通は不要 */
}

/* データの交換  p1 <-> p2 */
void exchange_data(int p1, int p2) {
  move_data(2*N, p1);  /* [2*N] を入れ替えのための置き場にする */
  move_data(p1,  p2);
  move_data(p2, 2*N);
}

/* 比較 p1 <-> p2 */
int compare_data(int p1, int p2) {
  compare_count++;
  return data[p1].value - data[p2].value;
}

/* データの表示(確認用) */
void print_data(void) {
  int i;
  for (i = 0; i < 2 * N; i++) {
    if (i % N == 0)
      printf("|");
    if (data[i].value < 0)
      printf(" [] ");
    else
      printf(" %2d ", data[i].value);
  }
  printf("\n");
}

/*
 * 実験用規則的ランダムデータ生成
 * 0 から N-1 が１個ずつ入るように
 */
void make_random_data(void) {
  int i, j, r;
  for (i = 0; i < N * 2 + 1; i++)
    data[i].value = -1;  /* 見せるためだけ: -1 は空を意味する */

  j = rand() % (N / 2);
  for (i = 0; i < N; i++) {
    r = rand() % (N / 2) + 2;
    while (r > 0) {
      j=(j + 1) % N;
      if (data[j].value < 0)
        r--;
    }
    data[j].value = i;
  }
}

/*** ここまで、各ソートアルゴリズムで使用している細かな関数 ***/
/**************************************************************/

/************************************************/
/*** ここから、各ソートアルゴリズム関数の定義 ***/

/* バブルソート */
void sort0(void) {
  int i, j;
  int lo = 0, up = N-1;

  if (display)
    print_data();  /* display が０で無い場合 経過を表示 */
  while (up > lo) {
    j = lo;
    for (i = lo; i < up; i++) {
      if (compare_data(i, i + 1) > 0) {  /* 順序が正しくなければ */
        exchange_data(i, i + 1);  /* 交換 */
        j = i;
        if (display)
          print_data();
      }
    }
    up = j;
    if (display)
      puts("");
  }
}

/*** ここまで、各ソートアルゴリズム関数の定義 ***/
/************************************************/

/*****************************************************/
/***ここからは定義したソート関数を呼び出して使おう ***/

int main(void) {
  srand((unsigned) time(NULL));     /* 規則的な乱数？生成の準備 */
  display = 1;    /* ０だと表示せず */

  make_random_data();

  sort0();

  printf("compare: %d,  move: %d  (%d data×%d experiments)\n",
         compare_count, move_count, N, num);

  return 0;
}