#include <library.h>
#include <time.h>
#include <sys/resource.h>

const bool testing = true;

double see_cpu_time()
{ struct rusage ruse;
  getrusage(RUSAGE_SELF, &ruse);
  return ruse.ru_utime.tv_sec+ruse.ru_utime.tv_usec/1000000.0 +
         ruse.ru_stime.tv_sec+ruse.ru_stime.tv_usec/1000000.0; } 

void main()
{ int N;
  cout << "What is the data size? ";
  cin >> N;

  int a[100001];
  for (int i = 1; i <= N; i += 1)
    a[i] = random_in_range(1, 99);

  if (! testing)
  { for (int i = 1; i <= N; i += 1)
      cout << a[i] << " ";
    cout << "\n"; }

  int count_ifs = 0,
      count_swaps = 0,
      count_outer_init = 0,
      count_outer_while = 0,
      count_inner_init = 0,
      count_inner_while = 0,
      count_inc_first = 0,
      count_dec_end = 0;

  double t0 = see_cpu_time();

  count_outer_init += 1;
  int end = N - 1;
  while (count_outer_while += 1, end >= 1)
  { count_inner_init += 1;
    int first = 1;
    while (count_inner_while += 1, first <= end)
    { count_ifs += 1;
      if (a[first] > a[first+1])
      { count_swaps += 1;
        int temp = a[first];
        a[first] = a[first+1];
        a[first+1] = temp; }
      count_inc_first += 1;
      first += 1; }
    count_dec_end += 1;
    end -= 1; }

  double t1 = see_cpu_time();

  cout << "Operation counts:\n";
  cout << "   inner while condition " << count_inner_while << "\n"
       << "    inner loop increment " << count_inc_first << "\n"
       << "          if before swap " << count_ifs << "\n"
       << "                    swap " << count_swaps << "\n"
       << "   outer while condition " << count_outer_while << "\n"
       << "    outer loop decrement " << count_dec_end << "\n"
       << "         init inner loop " << count_inner_init << "\n"
       << "         init outer loop " << count_outer_init << "\n";

// this nasty formulation is what it takes to ensure we always see
// six digits of precision, e.g. 0.000450 instead of 4.5e-4.

  cout << "time = " << setiosflags(ios::fixed) << setprecision(6) << t1-t0 << " seconds\n\n\n";

  if (! testing)
  { for (int i = 1; i <= N; i += 1)
      cout << a[i] << " ";
    cout << "\n"; }
}