// quicksort.cpp

#include <algorithm> 
#include <assert.h>
#include <iostream>
#include <math.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>

static int random(int ceiling) {
  return static_cast<int>((static_cast<float>(rand()) / RAND_MAX) * ceiling);
}

static void scramble(int a[], int aSize) {
  for (int i = 0; i < aSize; i++)
    std::swap(a[i], a[random(aSize)]);
}

static void makeScrambledArray(int a[], int size) {
  for (int i = 0; i < size; i++)
    a[i] = i;
  scramble (a, size);
}

static bool isSorted(int a[], int aSize) {
  for (int i = 0; i < aSize; i++)
    if (a[i] != i)
      return false;
  return true;
}

// BEGIN-ALGORITHM
static void bubblesort(int a[], int aSize) {
  for (;;) {
    bool swapped = false;
    for (int i = 0; i < aSize - 1; i++) {
      int j = i + 1;
      if (a[i] > a[j]) {
        std::swap(a[i], a[j]);
        swapped = true;
      }
    }
    if (!swapped)
      break;
  }
}
// END-ALGORITHM

int main() {
  const int trials = 1;
  double totalTime = 0;
  for (int i = 0; i < trials; i++) 
    {
      const int aSize = 10000;
      int a [aSize];
      makeScrambledArray(a, aSize);
      clock_t startTime = clock();
      bubblesort(a, aSize);
      clock_t endTime = clock();
      double seconds = 
        static_cast<double>(endTime - startTime) / CLOCKS_PER_SEC;
      totalTime += seconds;
      assert(isSorted(a, aSize));
    }
  cout << totalTime / trials << endl;
}