/* Implementation and testing of various sorting algorithms:
 * sort an array a[0..size-1] in ascending order.
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

/* Useful macro to swap 2 elements */
#define SWAP(A,B) \
do{ int tmp = A; A = B; B = tmp; } while(0)

/* Type for the sorting functions */
typedef void (*sort_f)(int *, int);

/* The different implementations */
void selection_sort(int *, int);
void bubble_sort(int *, int);
void insertion_sort(int *, int);
void merge_sort(int *, int);
void quick_sort(int *, int);
void heap_sort(int *, int);

#define MAX 6

const char *NAMES[MAX]= {
  "selection", "bubble", "insertion", "merge", "quick", "heap"
};

sort_f SORT[MAX]={
  selection_sort, bubble_sort, insertion_sort,
  merge_sort, quick_sort, heap_sort
};


/* Print the elements of an array */
void print_array(int *a, int size) {
  printf("[ ");
  while(size--) printf("%d ", *a++);
  printf("] ");
}


/* Implementations: TODO! */

void selection_sort(int *a, int size) {

}

void bubble_sort(int *a, int size) {

}

void insertion_sort(int *a, int size) {

}

void merge_sort(int *a, int size) {

}

void quick_sort(int *a, int size) {

}

void heap_sort(int *a, int size) {

}


/* Testing of the output */
void check_sort(int *a, int size) {
  int errors = 0;
  printf("Checking set...");
  fflush(stdout);
  if (size < 30) print_array(a, size);
  while(size > 1) {
    /* check that a[i-1] <= a[i] */
    if (a[0] > a[1]) errors++;
    a++;
    size--;
  }
  if (errors) printf("%d errors!\n", errors);
  else printf("correct!\n");
}

/* Random generation, but always the same for
 * a given size for fair comparison. */
void generate(int *a, int size) {
  int i = size;
  srand(size);
  printf("Generating set...");
  fflush(stdout);
  /* %size is used to generate some identical elements */
  while(i--) *a++ = rand()%size;
  printf("done!\n");
}


int main(int argc, char *argv[]) {
  if (argc < 3) {
    int i;
    fprintf(stderr, "Usage: %s type size, where the types are\n", argv[0]);
    for(i = 0; i < MAX; i++)
      printf(" %d: %s-sort\n",i , NAMES[i]);
    return 1;
  } else {
    int type = atoi(argv[1]);
    int size = atoi(argv[2]);
    if (size < 1) {
      fprintf(stderr, "Minimum size 1!\n");
      return 1;
    }
    if (type < MAX) {
      int *a = (int*) malloc(size*sizeof(int));
      generate(a, size);
      printf("Sorting with %s-sort...", NAMES[type]);
      fflush(stdout);
      SORT[type](a, size);
      printf("done!\n");
      check_sort(a, size);
      free(a);
      return 0;
    } else {
      fprintf(stderr, "Supported types: 0..%d\n", MAX-1);
      return 1;
    }
  }
}