/* 整数型配列に対するクイックソートのプログラム */

#include <stdio.h>
#include <stdlib.h>

#define LEN 128

typedef struct {
  int number;
  char siten[20];
  char syuten[20];
  double kyori;
} kokudo;


void quick_sort (kokudo a[], int left, int right)
{
  int i, j;
  int pivot;
  kokudo x;

  if(left >= right) return;

  pivot = a[right].number;
  i = left; j = right-1;
  for(;;) {
    while(a[i].number < pivot) i++;
    while(i < j && pivot < a[j].number) j--;
    if (i < j) {
      x = a[i]; a[i] = a[j]; a[j] = x; 
    } else {
      break;
    }
  }
  x = a[i]; a[i] = a[right]; a[right] = x;

  quick_sort (a, left, i-1);
  quick_sort (a, i+1, right);
}

/* 動作テスト用の関数 */
int main(void)
{
  kokudo data[100];

  FILE *infp;
  FILE *outfp;
  char sline[LEN];
  int i = 0;
  int michi;

  infp = fopen("kokudo.txt", "r");
  if (infp == NULL) {
    printf("can not open input file\n");
    exit(1);
  } 

  while (fgets(sline, LEN, infp) != NULL) {
    sscanf(sline,"%d %s %s %lf\n", &data[i].number, data[i].siten, data[i].syuten, &data[i].kyori); 
    michi = i;
    i++;
  }

  fclose(infp);

  quick_sort(data, 0, michi);

  outfp = fopen("q2-1.txt", "w");
  if (outfp == NULL) {
    printf("can not open output file\n");
    exit(1);
  } 
  
  for (i = 0; i < michi; i++)
    fprintf(outfp,"%d %s %s %lf\n", data[i].number, data[i].siten, data[i].syuten, data[i].kyori);

  fclose(outfp);

  return 0;
}