#include <stdio.h>
#ifdef __OpenBSD__
#define ANSI
#endif
#ifdef linux
#define ANSI
#endif
#ifdef BSD44
#define ANSI
#endif
#ifdef __NetBSD__
#define ANSI
#endif
#ifdef BSD4_4
#define ANSI
#endif
#ifdef GCC
#define ANSI
#endif
#ifdef __SVR4
#define ANSI
#endif
#include <sys/types.h>
#include <time.h>
#ifdef ANSI
#include <stdlib.h>
#endif
#ifndef ANSI
typedef unsigned long ulong;
#endif

#ifdef ANSI
ulong ansort(int *a, int n) {
#else
ulong ansort(a, n)
int *a;
int n;
{
#endif
  ulong 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;
}

#ifdef ANSI
int main(void) {
#else
int main() {
#endif
  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);
#ifdef ANSI
  printf(
    "Predicting %2.2f operations for 10000 elements (affine),\n"
    "or %2.2f using simple extrapolation.\n",
#else
  printf(
  "Predicting %2.2f ops for 10K el (aff) / %2.2f using extrapol.\n",
#endif
    c + (c - d) / 17, c + c - e);
}