#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>

#ifdef _WIN32
#  define PRTsize "Iu"
#else
#  define PRTsize "zu"
#endif

#define ARRAY_COUNT ((size_t) 10000000)
#define SINGLE_ARRAY_SIZE ((size_t) 6)

static void quick_sort(size_t, int *);
static void bubble_sort(size_t, int *);
static void opt_bubble_sort(size_t, int *);
static void insertion_sort(size_t, int *);
static void optimized_sort(size_t, int *);

#define ADD_TEST(func) { .name=#func, .sort_func=func, .time_total=0.0, .time_per_sort=0.0 }
typedef struct {
  const char *name;
  void (*sort_func)(size_t, int*);
  double time_total;
  double time_per_sort;
} test_run_t;

test_run_t test_runs[] = {
  ADD_TEST(quick_sort),
  ADD_TEST(bubble_sort),
  ADD_TEST(opt_bubble_sort),
  ADD_TEST(insertion_sort),
  ADD_TEST(optimized_sort)
};
const size_t test_run_count=sizeof test_runs / sizeof *test_runs;

void do_all_runs(void);
void show_runs_stats(void);

int main(void)
{
  printf("test %" PRTsize " loops on %" PRTsize " int arrays\n", ARRAY_COUNT, SINGLE_ARRAY_SIZE);
  do_all_runs();
  show_runs_stats();

  return 0;
}

void do_test_run(test_run_t *);
int *create_test_arrays(size_t array_count, size_t array_size);

void do_all_runs(void)
{
  for(size_t i=0; i<test_run_count; ++i)
    do_test_run(test_runs+i);
}

int compare_runs(const void *pa, const void *pb)
{
  return ((const test_run_t *)pa)->time_total - ((const test_run_t *)pb)->time_total;
}

void show_runs_stats(void)
{
  puts("\n---\n");
  printf("%-20s   %-9s   %-5s\n", "function", "time", "ratio");
  qsort(test_runs, test_run_count, sizeof *test_runs, compare_runs);
  for(size_t i=0; i<test_run_count; ++i)
    printf("%-20s %8.2lf ns   %.2lf\n", test_runs[i].name,
                                    test_runs[i].time_per_sort,
                                    test_runs[i].time_per_sort / test_runs[0].time_per_sort
          );
}

void do_test_run(test_run_t *test_run)
{
  int *test_array=create_test_arrays(ARRAY_COUNT, SINGLE_ARRAY_SIZE);
  test_run->time_total=0.0;
  for(size_t i=0; i<ARRAY_COUNT; ++i) {
    if (i % (ARRAY_COUNT/100) == 0) {
      printf("%-20s  %02d%%\r", test_run->name, (int) ((100.0*i) / ARRAY_COUNT) );
      fflush(stdout);
    }
    clock_t start=clock();
    test_run->sort_func(SINGLE_ARRAY_SIZE, test_array+SINGLE_ARRAY_SIZE*i);
    test_run->time_total += clock()-start;
  }
  free(test_array);
  test_run->time_per_sort = test_run->time_total / CLOCKS_PER_SEC / ARRAY_COUNT * 1E9;
  printf("%20s 100%% %.2lfs\n", test_run->name, test_run->time_total/CLOCKS_PER_SEC);
}

int *create_test_arrays(size_t array_count, size_t array_size)
{
  int *new=malloc(array_count*array_size*sizeof *new);
  if (new==NULL) {
    perror("malloc");
    exit(EXIT_FAILURE);
  }
  srand(0);
  for(size_t i=0; i<array_count*array_size; ++i) {
    if (i % (array_count*array_size/20) == 0) {
      printf("Initializing test arrays %02d%%\r", (int) ((100.0*i) / (array_count*array_size)));
      fflush(stdout);
    }
    new[i]=rand();
  }
  puts("test arrays initialized     ");
  return new;
}

static int compare_int(const void *pa, const void *pb);

static void quick_sort(size_t size, int *array)
{
  (void) size;
  qsort(array, SINGLE_ARRAY_SIZE, sizeof *array, compare_int);
}

static int compare_int(const void *pa, const void *pb)
{
  return (* (const int *) pa) - (* (const int *) pb);
}

static void bubble_sort(size_t size, int *array)
{
  (void) size;
  for(size_t i=SINGLE_ARRAY_SIZE-1; i>0; --i)
    for(size_t j=0; j<i; ++j)
      if (array[j+1]<array[j]) {
        int temp=array[j+1];
        array[j+1]=array[j];
        array[j]=temp;
      }
}

static void opt_bubble_sort(size_t size, int *array)
{
  (void) size;
  bool sorted;
  for(size_t i=SINGLE_ARRAY_SIZE-1; i>0; --i) {
    sorted=true;
    for(size_t j=0; j<i; ++j) {
      if (array[j+1]<array[j]) {
        int temp=array[j+1];
        array[j+1]=array[j];
        array[j]=temp;
        sorted=false;
      }
      if (sorted)
        return ;
    }
  }
}

static void insertion_sort(size_t size, int *array)
{
  for(size_t i=1; i<size; ++i) {
    int temp=array[i];
    size_t j=i;
    while ( (j>0) && (array[j-1]>temp) ) {
      array[j]=array[j-1];
      --j;
    }
    array[j]=temp;
  }
}

static inline void compare_and_swap(int *array, size_t first, size_t second);

static void optimized_sort(size_t size, int *array)
{
  (void) size;
  compare_and_swap(array, 1, 2);
  compare_and_swap(array, 4, 5);
  compare_and_swap(array, 0, 2);
  compare_and_swap(array, 3, 5);
  compare_and_swap(array, 0, 1);
  compare_and_swap(array, 3, 4);
  compare_and_swap(array, 1, 4);
  compare_and_swap(array, 0, 3);
  compare_and_swap(array, 2, 5);
  compare_and_swap(array, 1, 3);
  compare_and_swap(array, 2, 4);
  compare_and_swap(array, 2, 3);
}

static inline void compare_and_swap(int *array, size_t f, size_t s)
{
  static int temp;
  if (array[f]>array[s])
  {
    temp=array[f];
    array[f]=array[s];
    array[s]=temp;
  }
}