#include <algorithm>  // Provides swap
#include <cstdlib>    // Provides EXIT_SUCCESS, size_t, srand(), rand()
#include <iostream>   // Provides cout and cin
#include <iomanip>    // Provides setw()
#include <ctime>      // Provides clock(), clock_t

using namespace std;

void selectionSort(int data[], size_t n);
void insertionSort(int data[], size_t n);
void bubbleSort(int data[], size_t n);
void mergeSort(int data[], size_t n);
void mergeSortHelp(int data[], int temp[], int left, int right);
void heapSort(int data[ ], size_t n);
void shellSort(int data[ ], size_t n);
//void quickSort(int data [ ], size_t n);
size_t parent(size_t k);
size_t left_child(size_t k);
size_t right_child(size_t k);
void make_heap(int data[ ], size_t n);
void reheapify_down(int data[ ], size_t n);
void shellSort(int data[], size_t n);
void insertionSort2(int data[], size_t n, int incr);
void fillBest(int data[], size_t n);
void fillAverage(int data[], size_t n);
void fillWorst(int data[], size_t n);
void print(int data[], char msg[], double time);
void trial(
  void sort(int*, size_t),
  void fill(int*, size_t),
  int*,
  size_t,
  char* );
void (*s[])(int*, size_t) = {
  selectionSort,
  insertionSort,
  bubbleSort,
  mergeSort,
  heapSort,
  shellSort
  //, quickSort
  };
void (*f[])(int*, size_t) = {
  fillBest,
  fillAverage,
  fillWorst };
const int SORTS = 6; // Change to 7 if quick sort is implemented
const int SENARIOS = 3;
char* msg[][SORTS] = {
  "Selection sort,    Best: ",
  "Insertion sort,    Best: ",
  "Bubble sort,       Best: ",
  "Merge sort,        Best: ",
  "Heap sort,         Best: ",
  "Shell sort,        Best: ",
  //"Quick sort,        Best: ",
  "Selection sort, Average: ",
  "Insertion sort, Average: ",
  "Bubble sort,    Average: ",
  "Merge sort,     Average: ",
  "Heap sort,      Average: ",
  "Shell sort,     Average: ",
  //"Quick sort,     Average: ",
  "Selection sort,   Worst: ",
  "Insertion sort,   Worst: ",
  "Bubble sort,      Worst: ",
  "Merge sort,       Worst: ",
  "Heap sort,        Worst: ",
  "Shell Sort,       Worst: "
  //, "Quick sort,       Worst: "
  };

int main() {
  const size_t SIZE = 20000;
  int data[SIZE];
                      
  for (int senario = 0; senario < SENARIOS; senario++) {
    for (int sort = 0; sort < SORTS; sort++)
      trial(s[sort], f[senario], data, SIZE, msg[senario][sort]);
    cout << endl; }
  return EXIT_SUCCESS;
}

void selectionSort(int data[], size_t n) {
  size_t i, j, index;
  int largest;

  if (n == 0)
    return;
  for (i = n - 1; i > 0; --i) {
    largest = data[0];
    index = 0;
    for (j = 1; j <= i; ++j) {
      if (data[j] > largest) {
        largest = data[j];
        index = j; }}
    swap(data[i], data[index]); }
}

void insertionSort(int data[], size_t n) {
  size_t i, j;
  
  for (i = 1; i < n; i++)
    for (j = i; (j > 0) && (data[j] < data[j - 1]); j--)
      swap(data[j], data[j - 1]);
}

void bubbleSort(int data[], size_t n) {
  size_t i, j;
  
  for (i = 0; i < (n - 1); i++)
    for (j = n - 1; j > i; j--)
      if (data[j] < data[j - 1])
        swap(data[j], data[j - 1]);
}

void mergeSort(int data[], size_t n) {
  int* temp = new int[n];
  
  mergeSortHelp(data, temp, 0, n - 1);
  delete[] temp;
}

void mergeSortHelp(int data[], int temp[], int left, int right) {
  int i, j, k, mid = (left + right)/2;
  
  if (left == right)
    return;
  mergeSortHelp(data, temp, left, mid);
  mergeSortHelp(data, temp, mid + 1, right);
  for (i = left; i <= mid; i++)
    temp[i] = data[i];
  for (j = 1; j <= right - mid; j++)
    temp[right - j + 1] = data[j + mid];
  for (i = left, j = right, k = left; k <= right; k++)
    if (temp[i] < temp[j])
      data[k] = temp[i++];
    else
      data[k] = temp[j--];
}

void heapSort(int data[ ], size_t n) {
  size_t unsorted;
  
  make_heap(data, n);
  unsorted = n;
  while (unsorted > 1) {
    --unsorted;
    swap(data[0], data[unsorted]);
    reheapify_down(data, unsorted); }
}

size_t parent(size_t k) {
  return (k - 1)/2;
}

size_t left_child(size_t k) {
  return 2*k + 1;
}

size_t right_child(size_t k) {
    return 2*k + 2;
}

void make_heap(int data[ ], size_t n) {
  size_t i;
  size_t k;
  
  for (i = 1; i < n; ++i) {
    k = i;
    while ((k > 0) && (data[k] > data[parent(k)])) {
      swap(data[k], data[parent(k)]);
      k = parent(k); }}
}

void reheapify_down(int data[ ], size_t n) {
  size_t current;
  size_t big_child_index;
  bool heap_ok = false;
  current = 0;
  
  while ((!heap_ok) && (left_child(current) < n)) {
    if (right_child(current) >= n)
      big_child_index = left_child(current);
    else if (data[left_child(current)] > data[right_child(current)])
      big_child_index = left_child(current);
    else
      big_child_index = right_child(current);
    if (data[current] < data[big_child_index]) {
      swap(data[current], data[big_child_index]);
      current = big_child_index; }
    else
      heap_ok = true; }
}

void shellSort(int data[], size_t n) {
  for (int i = n/3; i > 3; i /= 3)
    for (int j = 0; j < i; j++)
      insertionSort2(&data[j], n - j, i);
  insertionSort(data, n);
}

void insertionSort2(int data[], size_t n, int incr) {
  for (int i = incr; i < n; i += incr)
    for (int j = i; (j >= incr) && (data[j] < data[j - incr]); j -= incr)
      swap(data[j], data[j - incr]);
}

/*
void quickSort(int data[ ], size_t n) {
}
*/

void fillBest(int data[], size_t n) {
  for (size_t i = 0; i < n; i++)
    data[i] = i;
}

void fillAverage(int data[], size_t n) {
  srand(1);
  for (size_t i = 0; i < n; i++)
    data[i] = rand();
}

void fillWorst(int data[], size_t n) {
  for (size_t i = 0; i < n; i++)
    data[i] = n - i - 1;
}

void print(int data[], char msg[], double time) {
  cout.setf(ios::fixed);
  cout.precision(2);
  cout << msg << setw(5) << time << " seconds." << endl;
  if (strncmp(msg, "Quick sort", 10) == 0) {
    for (size_t i = 0; i <= 100; i++) { 
      cout << setw(10) << data[i]; 
      if (((i % 10) == 0)) 
        cout << endl; } }
}

void trial( void sort(int* , size_t),
            void fill(int* , size_t),
            int* data,
            size_t n,
            char* msg) {
  clock_t start, stop;
  fill(data, n);
  start = clock();
  sort(data, n);
  stop = clock();
  print(data, msg, (stop - start)/(double)CLOCKS_PER_SEC);
}