#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <time.h>

/* UNIX: cc -O cisc320-hw3-no4.c -o cisc320-hw3-no4 ; /usr/bin/timex cisc320-hw3-no4 */
/* Linux: gcc -O2 cisc320-hw3-no4.c -o cisc320-hw3-no4 ; /usr/bin/time cisc320-hw3-no4 */
/* VMS: cc cisc320-hw3-no4.c
 *      link/exec=cisc320-hw3-no4 cisc320-hw3-no4.obj
 *      show proc/acc
 *      run cisc320-hw3-no4
 *      show proc/acc */

unsigned long ansort(a, n)
int *a, n;
{
  unsigned long c;
  int i, j, v;

  c = 0;
  for(i = 1 ; i < n ; ++i) {
    v = a[i];
    for(++c, j = i - 1 ; j >= 0 && a[j] > v ; --j, ++c)
      a[j + 1] = a[j];
    a[j + 1] = v;
  }
  return c;
}

int main() {
  int *a, i, k, n, m;
  double t, c, d, e;

  srand((unsigned int) time(NULL));
  d = 250102.85; /* delta-c */
  a = (int *) malloc(sizeof(int) * 9500);
  for(n = 12 ; n < 18 ; ++n) {
    m = 1000 + 500 * n; /* size of a */
    t = 0.0; /* ansort retval accumulator */
    for(k = 0 ; k < 20 ; ++k) {
      for(i = 0 ; i < m ; ++i)
        a[i] = rand(); /* randomize a */
      t += ansort(a, m);
    }
    printf("%d elements, %2.2f operations\n", m, c = 0.05 * t);
    if(!n)
      d = c;
    else if(16 == n)
      e = c;
  }
  free(a);
  printf("Predicting %2.2f operations for 10000 elements (affine),\n"
    "or %2.2f using simple extrapolation.\n",
    c + (c - d) / 17, c + c - e);
  return 0;
}