// 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);
}

// BEGIN-ALGORITHM
static int partition(int a[], int first, int last) {
  int pivot = a[first];
  int lastS1 = first;
  int firstUnknown = first + 1;
  while (firstUnknown <= last) {
    if (a[firstUnknown] < pivot) {
      lastS1++;
      std::swap(a[firstUnknown], a[lastS1]);
    }
    firstUnknown++;
  }
  std::swap(a[first], a[lastS1]);
  return lastS1;
}

static void quicksort(int a[], int first, int last) {
  if (first < last) {
    int pivotIndex = partition(a, first, last);
    quicksort(a, first, pivotIndex - 1);
    quicksort(a, pivotIndex + 1, last);
  }
}

static void quicksort(int a[], int aSize) {
  quicksort(a, 0, aSize - 1);
}
// END-ALGORITHM

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