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

int i, size;
int *table;
char c;

/* basic functions */
int swap(int*, int, int);

int insertionSort (int *, int);
int selectionSort (int *, int);

/* functions required for heapsort */
int buildHeap (int*, int);
int heapSort (int*, int);
int sink (int*, int, int);

int checkSorted (int *, int);


int
main ()
{
  while (1)
    {
      printf ("Select a number:\n");
      printf ("1) Randomly fill the table\n");
      printf ("2) Print the table\n");
      printf ("3) Selectionsort\n");
      printf ("4) Insertionsort\n");
      printf ("5) Heapsort\n");
      printf ("6) Check the table is sorted\n");
      printf ("7) Exit\n");

      do
	{
	  fprintf (stdout, "Make your selection: ");
	  while ((c = getchar ()) == '\n');
	}
      while (!strchr ("1234567", c));

      switch (c)
	{

	case '1':
	  srand (1);
	  printf ("please enter the size of the table:");
	  scanf ("%d", &size);
	  fflush (stdin);
	  table = malloc (size * sizeof (int));
	  for (i = 0; i < size; i++)
	    table[i] = random () % 1024;
	  break;

	case '2':
	  printf ("\n\nThe table:[");
	  for (i = 0; i < size - 1; i++)
	    printf ("%d,", table[i]);
	  printf ("%d]\n\n", table[i]);
	  break;

	case '3':
	  selectionSort (table, size);
	  break;

	case '4':
	  insertionSort (table, size);
	  break;

        case '5':
          heapSort (table, size);
          break;

	case '6':
	  checkSorted (table, size);
	  break;

	case '7':
	  return (1);
	  break;
	}

    }
  return (1);
}


int
selectionSort (int array[], int size)
{
  int i, j;
  int min, temp;

  for (i = 0; i < size - 1; i++)
    {
      min = i;
      for (j = i + 1; j < size; j++)
	{
	  if (table[j] < array[min])
	    min = j;
	}
      temp = array[i];
      array[i] = array[min];
      array[min] = temp;
    }
  return (1);
}

int
insertionSort (int a[], int size)
{
  int i, j, val;
  for (i = 0; i < size; i++)
    {
      val = a[i];
      j = i - 1;
      while (j >= 0 && a[j] > val)
	{
	  a[j + 1] = a[j];
	  j--;
	}
      a[j + 1] = val;

    }
  return (1);
}

int
checkSorted (int array[], int size)
{
  int i, unsorted = 0;
  for (i = 1; i < size; i += 1)
    {
      if (array[i - 1] > array[i])
	{
	  printf ("The array is not in sorted order at position %d\n", i - 1);
	  if (!unsorted)
	    unsorted++;
	}
    }
  if (!unsorted)
    printf ("\nThe table is already sorted !\n");
  return (1);
}

/* heapSort(table, size)
 * Uses the heapsort algorithm to sort the given array
 *  table: arbitrary array
 *  size: length of the given array
 */
int heapSort(int* table, int size){
 int i;
 /* convert table into a heap */
 buildHeap(table, size);

 /* sink all inner nodes, except the root */
 for (i=size - 1; i >= 0 ; i--)
  {
  /* move largest element to the end */
  swap(table, 0, i);
  /* sink new root */
  sink(table, 0, i);
  }
 return 1;
}


/* buildHeap(table, size)
 * Establishes the heap property using a bottom-up approach.
 *  table: array to be converted into a heap
 *  size: length of the given array
 */
int buildHeap(int* table, int size){
 int i;
 /* sink all inner nodes */
 for (i = (size - 1) / 2; i >= 0; i--)
  sink(table, i, size);
 return 1;
}

/* sink(table, index, until)
 *  Sinks the element at position index into the heap, until at most 
 *  position until.
 *   table: array, assumd to satisfy the heap property between index+1 and until
 *   index: position of the element to be sunk into the array
 *   until: first position to be ignored in the array
 */
int sink(int* table, int index, int until){
 int child1, child2, max;
 child1 = 2 * index + 1; /* positions of children */
 child2 = 2 * index + 2; 
 /* if heap property not satisfied */
 if ( (child1 < until) && (table[child1] > table[index]))
  /* consider both children? */
  if ( (child2 < until) && (table[child2] > table[index]))
    { 
     /* get maximum of children */
     if (table[child1] > table[child2])
      max = child1;
     else
      max = child2;
     /* swap and sink further */
    swap(table, index, max);
    sink(table, max, until);
    }
  /* consider only left child */
  else
    {
    swap(table, index, child1);
    sink(table, child1, until);
    }
 /* consider only right child */
 else if ( (child2 < until) && (table[child2] > table[index]))
  {
   swap(table, index, child2);
   sink(table, child2, until);
  }
 return 1;
}

/* swap exchenges two elements in an array
 *  table: array
 *  i, j: positions to be exchanged
 */
int swap(int* table, int i, int j){
 if (i >= 0 && j >= 0)
  {
   int temp = table[i];
   table[i] = table[j];
   table[j] = temp;
   return 0;
  }
 else
  return 1; 
}