#10

city,temprature,precitipation
Sapporo,8.2,1129.6
Sendai,11.9,1204.5
Tokyo,15.6,1405.3
Kanazawa,14.1,2592.6
Oosaka,16.3,1318.0
Hiroshima,16.2,1511.8
Kouchi,16.4,2582.4
Fukuoka,16.2,1604.3
Naha,22.4,2036.8
// csv.h --- csv file read/write API.
struct csv { int num; char *cell[1]; };
typedef struct csv *csvp;
int csv_read(char *fname, int limit, csvp arr[]);
void csv_write(char *fname, int size, csvp arr[]);
// csv.c --- csv file read/write API impl.
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "csv.h"
#define MAXLINE 1000
static char *readline(FILE *f) {
  char buf[MAXLINE], *str;
  if(fgets(buf, MAXLINE, f) == NULL) { return NULL; }
  int len = strlen(buf);
  if(buf[len-1] == '\n') { buf[--len] = '\0'; }
  str = (char*)malloc(len+1); strcpy(str, buf); return str;
}
static csvp read1(FILE *f) {
  char *arr[100], *s = readline(f); if(s == NULL) { return NULL; }
  int i = 0;
  for(arr[i++] = s; *s != '\0'; ++s) {
    if(*s == ',') { *s = '\0'; arr[i++] = s+1; }
  }
  csvp r = (csvp)malloc(sizeof(struct csv) + i*sizeof(char*));
  r->num = i; 
  for(i = 0; i < r->num; ++i) { r->cell[i] = arr[i]; }
  return r;
}
int csv_read(char *fname, int limit, csvp arr[]) {
  int size = 0; csvp line;
  FILE *f = fopen(fname, "rb"); if(f == NULL) { return -1; }
  while((line = read1(f)) != NULL) {
    if(size+1 >= limit) { size = -2; break; }
    arr[size++] = line;
  }
  fclose(f); return size;
}
void csv_write(char *fname, int size, csvp arr[]) {
  FILE *f = fopen(fname, "wb"); if(f == NULL) { return; }
  for(int i = 0; i < size; ++i) {
    fprintf(f, "%s", arr[i]->cell[0]);
    for(int j = 1; j < arr[i]->num; ++j) { fprintf(f, ",%s", arr[i]->cell[j]); }
    fprintf(f, "\n");
  }
  fclose(f);
}
// csvdemo.c --- demonstration for csv_read.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "csv.h"

int main(int argc, char *argv[]) {
  csvp data[1000], p;
  int size = csv_read(argv[1], 1000, data);
  if(size <= 0) { return 0; }
//qsort(data+1, size-1, sizeof(csvp), cmp1); // **
  p = data[0];
  printf("%11s %11s %11s\n", p->cell[0], p->cell[1], p->cell[2]);
  for(int i = 1; i < size; ++i) {
    p = data[i];
    printf("%11s %11.3f %11.3f\n",
           p->cell[0], atof(p->cell[1]), atof(p->cell[2])/12.0);
  }
  return 0;
}
// csvdemo_1.c --- demonstration for csv_read w/ sorting.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "csv.h"

static int cmp1(const void *x, const void *y) { // comp-fn.
  csvp a = *(csvp*)x, b = *(csvp*)y;
  return strcmp(a->cell[0], b->cell[0]);
}
int main(int argc, char *argv[]) {
  csvp data[1000], p;
  int size = csv_read(argv[1], 1000, data);
  if(size <= 0) { return 0; }
  qsort(data+1, size-1, sizeof(csvp), cmp1); // **
  p = data[0];
  printf("%11s %11s %11s\n", p->cell[0], p->cell[1], p->cell[2]);
  for(int i = 1; i < size; ++i) {
    p = data[i];
    printf("%11s %11.3f %11.3f\n",
           p->cell[0], atof(p->cell[1]), atof(p->cell[2])/12.0);
  }
  return 0;
}
Nation,City,1,2,3,4,5,6,7,8,9,10,11,12,AVG
Austria,Vienna,0.3,1.5,5.7,10.7,15.7,18.7,20.8,20.2,15.4,10.2,5.1,1.1,10.4
Belgium,Brussels,3.3,3.7,6.8,9.8,13.6,16.2,18.4,18.0,14.9,11.1,6.8,3.9,10.5
Bulgaria,Sofia,-0.5,1.1,5.4,10.6,15.4,18.9,21.2,21.0,16.5,11.3,5.1,0.7,10.6
Croatia,Zagreb,0.3,2.3,6.4,10.7,15.8,18.8,20.6,20.1,15.9,10.5,5.0,1.4,10.7
Czech Republic,Prague,-1.4,-0.4,3.6,8.4,13.4,16.1,18.2,17.8,13.5,8.5,3.1,-0.3,8.4
Denmark,Copenhagen,0.6,0.5,2.5,6.1,11.1,14.8,16.9,16.7,13.1,9.1,4.9,2.1,8.2
Finland,Helsinki,-3.9,-4.7,-1.3,3.9,10.2,14.6,17.8,16.3,11.5,6.6,1.6,-2.0,5.9
Finland,Kuopio,-9.2,-9.2,-4.1,2.0,9.1,14.5,17.5,15.0,9.7,4.1,-2.0,-6.7,3.4
Finland,Oulu,-9.6,-9.3,-4.8,1.4,7.8,13.5,16.5,14.1,8.9,3.3,-2.8,-7.1,2.7
France,Marseille,8.4,8.9,11.6,13.8,17.9,21.3,24.5,24.1,20.7,16.9,11.8,9.3,15.8
France,Paris,4.9,5.6,8.8,11.4,15.1,18.2,20.4,20.2,16.9,12.9,8.1,5.4,12.3
Germany,Berlin,0.6,2.3,5.1,10.2,14.8,17.9,20.3,19.7,15.3,10.5,6.0,1.3,10.3
Germany,Frankfurt,1,2,6,8,13,16,18,18,15,10,5,2,10
Greece,Athens,9.8,10.1,12.2,16.0,21.0,25.9,28.7,28.4,24.1,19.2,14.7,11.1,18.4
Hungary,Budapest,0.4,2.3,6.1,12.0,16.6,19.7,21.5,21.2,16.9,11.8,5.4,1.8,11.3
Iceland,Reykjavik,-0.5,0.4,0.5,2.9,6.3,9.0,10.6,10.3,7.4,4.4,1.1,-0.2,4.3
Ireland,Dublin,5.3,5.3,6.8,8.3,10.9,13.6,15.6,15.3,13.4,10.5,7.4,5.6,9.8
Italy,Milan,2.5,4.7,9.0,12.2,17.0,20.8,23.6,23.0,19.2,13.4,7.2,3.3,13.0
Italy,Rome,7.5,8.2,10.2,12.6,17.2,21.1,24.1,24.5,20.8,16.4,11.4,8.4,15.2
Malta,Valletta,12.8,12.8,13.3,15.6,18.9,22.8,26.1,26.7,23.9,21.1,17.2,13.9,18.8
Netherlands,Amsterdam,3.4,3.5,6.1,9.1,12.9,15.4,17.6,17.5,14.7,11.0,7.1,4.0,10.2
Norway,Bergen,1.5,1.6,3.3,5.9,10.5,13.5,14.5,14.4,11.5,8.7,4.7,2.6,7.7
Norway,Oslo,-4.3,-4.0,-0.2,4.5,10.8,15.2,16.4,15.2,10.8,6.3,0.7,-3.1,5.7
Norway,Tromso,-3.8,-3.7,-2.3,0.7,5.1,9.2,11.8,10.9,6.9,3.2,-0.6,-2.7,2.9
Poland,Warsaw,-1.8,-0.6,2.8,8.7,14.2,17.0,19.2,18.3,13.5,8.5,3.3,-0.7,8.5
Portugal,Lisbon,11.6,12.7,14.9,15.9,18.0,21.2,23.1,23.5,22.1,18.8,15.0,12.4,17.5
Romania,Bucharest,-1.3,0.4,5.4,11.2,16.8,20.6,22.5,22.0,16.9,11.0,4.7,0.2,10.8
Russia,Arkhangelsk,-12.7,-11.4,-5.5,0.4,6.9,13.0,16.3,13.1,8.2,2.3,-5.1,-9.8,1.3
Russia,Moscow,-6.5,-6.7,-1.0,6.7,13.2,17.0,19.2,17.0,11.3,5.6,-1.2,-5.2,5.8
Russia,Murmansk,-10.1,-9.7,-5.5,-0.7,4.0,9.2,12.8,11.1,7.0,1.5,-4.8,-8.2,0.6
Russia,Rostov-on-Don,-3.0,-2.8,2.4,10.6,16.6,21.0,23.4,22.6,16.7,10.0,2.9,-1.6,9.9
Russia,Sochi,6.1,6.0,8.2,12.1,16.0,20.2,23.2,23.6,20.0,15.8,11.1,8.1,14.2
Serbia,Belgrade,1.4,3.1,7.6,12.9,18.1,21.0,23.0,22.7,18.0,12.9,7.1,2.7,12.5
Spain,Barcelona,11.8,12.4,14.2,15.8,19.3,23.0,25.7,26.1,23.0,19.5,14.9,12.3,18.2
Spain,Madrid,6.3,7.9,11.2,12.9,16.7,22.2,25.6,25.1,20.9,15.1,9.9,6.9,15.0
Sweden,Stockholm,-2.8,-3.0,0.1,4.6,10.7,15.6,17.2,16.2,11.9,7.5,2.6,-1.0,6.6
Switzerland,Zurich,0.3,1.3,5.3,8.8,13.3,16.4,18.6,18.0,14.1,9.9,4.4,1.4,9.3
Turkey,Istanbul,5.7,5.7,7.0,11.1,15.7,20.4,22.9,23.1,19.8,15.6,11.5,8.0,13.9
Ukraine,Kiev,-3.5,-3.0,1.8,9.3,15.5,18.5,20.5,19.7,14.2,8.4,1.9,-2.3,8.4
United Kingdom,Edinburgh,4.2,4.5,6.2,8.1,10.8,13.5,15.3,15.2,13.0,9.8,6.7,4.2,9.3
United Kingdom,London,4.3,4.5,6.9,8.7,12.1,15.1,17.3,17.0,14.3,10.9,7.2,4.7,10.3
static void iswap(int a[], int i, int j) {
  int x = a[i]; a[i] = a[j]; a[j] = x;
}
static int minrange(int a[], int i, int j) {
  int min = a[i], pos = i;
  for(int k = i+1; k <= j; ++k) {
    if(a[k] < min) { min = a[pos = k]; }
  }
  return pos;
}
void selectionsort(int n, int a[]) {
  for(int i = 0; i < n; ++i) { iswap(a, i, minrange(a, i, n-1)); }
}
static int shiftrange(int a[], int i) {
  int x = a[i];
  for( ; i > 0 && a[i-1] > x; --i) { a[i] = a[i-1]; }
  a[i] = x;
}
void insertionsort(int n, int a[]) {
  for(int i = 1; i < n; ++i) { shiftrange(a, i); }
}
static void iswap(int a[], int i, int j) {
  int x = a[i]; a[i] = a[j]; a[j] = x;
}
void bublesort(int n, int a[]) {
  bool done = false;
  while(!done) {
    done = true;
    for(int i = 1; i < n; ++i) {
      if(a[i-1] > a[i]) { iswap(a, i-1, i); done = false; }
    }
  }
}
static void iswap(int a[], int i, int j) {
  int x = a[i]; a[i] = a[j]; a[j] = x;
}
void combsort(int n, int a[]) {
  int d = n; bool done = false;
  while(d > 1 || !done) {
    done = true;
    for(int i = d; i < n; ++i) {
      if(a[i-d] > a[i]) { iswap(a, i-d, i); done = false; }
    }
    if(d > 1) { d = d * 10 / 13; }
  }
}
// test_sort.c --- unit test for sort algorithms.
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

static void iswap(int a[], int i, int j) {
  int x = a[i]; a[i] = a[j]; a[j] = x;
}
static int minrange(int a[], int i, int j) {
  int min = a[i], pos = i;
  for(int k = i+1; k <= j; ++k) {
    if(a[k] < min) { min = a[pos = k]; }
  }
  return pos;
}
void selectionsort(int n, int a[]) {
  for(int i = 0; i < n; ++i) { iswap(a, i, minrange(a, i, n-1)); }
}
static int shiftrange(int a[], int i) {
  int x = a[i];
  for( ; i > 0 && a[i-1] > x; --i) { a[i] = a[i-1]; }
  a[i] = x;
}
void insertionsort(int n, int a[]) {
  for(int i = 1; i < n; ++i) { shiftrange(a, i); }
}
void bubblesort(int n, int a[]) {
  bool done = false;
  while(!done) {
    done = true;
    for(int i = 1; i < n; ++i) {
      if(a[i-1] > a[i]) { iswap(a, i-1, i); done = false; }
    }
  }
}
void combsort(int n, int a[]) {
  int d = n; bool done = false;
  while(d > 1 || !done) {
    done = true;
    for(int i = d; i < n; ++i) {
      if(a[i-d] > a[i]) { iswap(a, i-d, i); done = false; }
    }
    if(d > 1) { d = d * 10 / 13; }
  }
}
void expect_sort_iarray(int n, void (*f)(int m, int *a), char *msg) {
  int c = 0, *a = (int*)malloc(n * sizeof(int));
  srand(time(NULL));
  for(int i = 0; i < n; ++i) { a[i] = rand()%10000; }
  struct timespec tm1, tm2;
  clock_gettime(CLOCK_REALTIME, &tm1);
  (*f)(n, a);
  clock_gettime(CLOCK_REALTIME, &tm2);
  for(int i = 1; i < n; ++i) {
    if(a[i-1] <= a[i]) { continue; } // correct order
    if(++c < 5) {
      printf("  wrong order at %d: %d > %d\n", i-1, a[i-1], a[i]);
    } else if(c == 5) {
      printf("  more wrong place omitted.\n");
    }
  }
  double dt = (tm2.tv_sec-tm1.tv_sec) + 1e-9*(tm2.tv_nsec-tm1.tv_nsec);
  printf("%s time=%.4f %s\n", c==0?"OK":"NG", dt, msg); free(a);
}
int main(int argc, char *argv[]) {
  int n = atoi(argv[1]);
  expect_sort_iarray(n, selectionsort, "selectionsort");
  expect_sort_iarray(n, insertionsort, "inserctionsort");
  expect_sort_iarray(n, bubblesort, "bubblesort");
  expect_sort_iarray(n, combsort, "combsort");
  return 0;
}