// 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 int newGap(int gap) {
  gap = (gap * 10) / 13;
  if (gap == 9 || gap == 10)
    gap = 11;
  if (gap < 1)
    gap = 1;
  return gap;
}

static void combsort(int a[], int aSize) {
  int gap = aSize;
  for (;;) {
    gap = newGap(gap);
    bool swapped = false;
    for (int i = 0; i < aSize - gap; i++) {
      int j = i + gap;
      if (a[i] > a[j]) {
        std::swap(a[i], a[j]);
        swapped = true;
      }
    }
    if (gap == 1 && !swapped)
      break;
  }
}
// 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();
      combsort(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;
}