/*
    Robert Marmorstein and Nile Gentry
    Sort Timing Experiment
    Due Wednesday, March 15, 2000
*/
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <time.h>
#include <sys/timeb.h>
#include <math.h>
#define MAXRAND 20.0

int numElems;
int *array;
int *tempArray;
clock_t startTime;
int n;

void getRands(int *p);
void printRands(int *p);
void startTimer ( void );
void verify( void );
void msort( int array[], int array2[], int left, int right);

void qsort(int array[], int begin, int size);
int findpivot(int array[], int l, int r);
int partition(int array[], int l, int r, int pivot);
void removeMax( void );

void buildheap( void );
void siftdown( int pos);
bool isLeaf( int pos);
int leftchild( int pos);
clock_t stopTimer ( void );

//declare the Sort functions

void bubbleSort( void );
void selectionSort ( void );
void insertionSort ( void );
void quickSort( void );
void mergeSort ( void );
void heapSort ( void );
void radixSortOne ( void );
void radixSortTwo ( void );

//Declare an array of pointers to functions
void (*functions[8])();

typedef struct node{
   int value;
   node* next;
}node;


void main(int argc, char** argv){
   int i;
   functions[0]=bubbleSort;
   functions[1]=selectionSort;
   functions[2]=insertionSort;
   functions[3]=quickSort;
   functions[4]=heapSort;
   functions[5]=mergeSort;
   functions[6]=radixSortOne;
   functions[7]=radixSortTwo;

   int myTime;

   /* Check for valid command line*/
   if (argc != 2){
      printf("Format:  sorting <number of elements>\n"); 
      exit (-1);  
   }

   //Retrieve Array Size
   numElems=atoi(argv[1]);
   printf("\nNumber of items=%d\n-------------------------\n", numElems);
   array=(int *)calloc(sizeof(int),numElems);   
   tempArray = (int *)calloc(sizeof(int), numElems);

   srand( time ( NULL) );
   getRands(array);
   for (i=0; i<8; i++){
      memcpy(tempArray, array, numElems*sizeof(int));
      startTimer();
      functions[i]();
      myTime = (int)(((double)stopTimer())/CLOCKS_PER_SEC*1000);
      
      //verify();
      printf ("\t\t%d\n", myTime);
   }
   //printRands(array);
   printf("-------------------------\n");
   free(tempArray);
   free(array);
}

void getRands(int *array){
   int *p;
   for (p=array; p<array+numElems; p++){
      (*p)=(int)((rand()*MAXRAND)/RAND_MAX);
   }
}

void printRands(int *array){
   int *p;
   int i=0;
   printf("The Array\n");
   printf("---------\n");
   for (p=array; p<array+numElems; p++){
      printf("%d. %d\n", i, *p);
      i++;
   }
}

void startTimer( void ){
   startTime=clock();
}

clock_t stopTimer ( void ){
   return clock()-startTime;
}

void quickSort( void ){   
   qsort(tempArray, 0, numElems-1);
   printf("Quicksort             ");
}

void bubbleSort( void ){
   int i;
   int j;
   for (i=0; i<numElems; i++){
      for (j=i;j<numElems; j++){
         if (tempArray[j]<tempArray[i]){
            int temp=tempArray[j];
            tempArray[j]=tempArray[i];
            tempArray[i]=temp;
         }
      }
   }
   printf("Bubble Sort            ");
}

void selectionSort ( void ){
   printf("Selection Sort         ");
   int i;
   int j; 
   int smallest;
   int temp;
   for (i=0;i<numElems;i++){
      smallest=i;
      for (j=i; j<numElems;j++){
         if (tempArray[j]<tempArray[smallest]){
            smallest=j;
         }
      }
      temp = tempArray[i];
      tempArray[i]=tempArray[smallest];
      tempArray[smallest]=temp;
   }
}
void insertionSort ( void ){
   printf("Insertion Sort         ");
   int i,j;
   for(i=1; i<numElems; i++){
	for(j=i; (j>0) && (tempArray[j] < tempArray[j-1]); j--){
			int temp = tempArray[j];
			tempArray[j] = tempArray[j-1];
			tempArray[j-1] = temp;
	}
   }
}

void heapSort ( void ){
   int i;

   printf("Heap Sort           ");
   n=numElems;
   buildheap();
   n=numElems;
   for (i=0; i< numElems; i++)
      removeMax();
}

void mergeSort( void ){
      int *helpArray;
     
      printf("Merge Sort         ");
      helpArray = (int*)calloc(sizeof(int), numElems*2);
      msort(tempArray, helpArray, 0, numElems-1);
      free(helpArray);
}

void radixSortOne( void ){
   int i, j, rtok;
   double k;
   int count[10];
   int temp2Array[numElems];

   printf("Radix Sort One (Array)");

   k=log10(MAXRAND);

   for (i=0, rtok=1; i<k; i++, rtok*=10){
      for (j=0; j<10; j++) count[j]=0;
      for (j=0; j<numElems; j++) 
         count[(tempArray[j]/rtok)%10]++; 
      for (j=1; j<10; j++) count[j]=count[j-1]+count[j];

      for (j=numElems-1; j>=0; j--)
         temp2Array[--count[(tempArray[j]/rtok)%10]]= tempArray[j];

      for (j=0; j<numElems; j++)
         tempArray[j]=temp2Array[j];
    
   }
}

void radixSortTwo( void ){
   int i;
   int digit;
   int count;
   node* bins[10];
   node* ptr;
   node* k;
   node* last;

   printf("Radix Sort Two(List) ");
   for (digit = 0; digit<log10(MAXRAND); digit++){

      for (i = 0; i<10; i++){
         bins[i]=NULL;
      }

      for (i=0; i<numElems;i++){
         k = (node *)calloc(1, sizeof(node));
         k->value = tempArray[i];
         k->next = NULL;
         
         count = (int)(k->value/pow(10, digit));
         count = count % 10;
         ptr=bins[count];
         if (bins[count] == NULL)
   	    bins[count]=k;
         else{
            while (ptr->next !=NULL) ptr=ptr->next;
            ptr->next=k;
         }
         
      }
      count = 0;
      for (i=0; i<10;i++){
         last = NULL;
         for (ptr=bins[i]; ptr != NULL; ptr=ptr->next){
            if (last != NULL)
               free(last);
            last=ptr;
            tempArray[count]=ptr->value;
            count++;
         }
      }
   }
   
}

void verify ( void ){
   int i;
   for (i=0; i< numElems; i++)
      printf("%d ", tempArray[i]);
   printf("\n");
}

int median(int a1, int a2, int a3){
   if ((a1>a2 && a1<a3) || (a1<a2 && a1>a3) )
      return 1;
   else if ((a2>a1 && a2<a3) || (a2<a1 && a2>a3) )
      return 2;
   else if ((a3>a1 && a3<a2) || (a3<a1 && a3>a2) )
      return 3;
}

void swap (int a, int b){
  int temp;
  temp = tempArray[a];
  tempArray[a]=tempArray[b];
  tempArray[b]=temp;
}

void qsort( int array[], int i, int j){
   int pivotindex;
   int temp;

   pivotindex = findpivot( array, i, j);

   temp=array[pivotindex];   
   array[pivotindex]=array[j];
   array[j]=temp;
 
   int k = partition(array, i-1, j, array[j]);
   temp=array[k];
   array[k]=array[j];
   array[j]=temp;
   
   if ((k-i) > 1) qsort( array, i, k-1);
   if ((j-k) > 1) qsort( array, k+1, j);
}

int findpivot(int array[], int i, int j){
   return (i+j)/2;
}

int partition(int array[], int l, int r, int pivot){
  int temp;

  do {
    while (array[++l] < pivot);
    while ((r!=0) && (array[--r]>pivot));
    temp=array[l];
    array[l]=array[r];
    array[r]=temp;
  }while (l<r);
  temp=array[l];
  array[l]=array[r];
  array[r]=temp;
  return l;
}

void buildheap ( void ){
   int i;
 
   for (i=n/2-1; i>=0; i--){
      siftdown(i);
   }
}

void siftdown(int pos){
   int j, temp;  
 
   while (!isLeaf(pos)){
      j=leftchild(pos);
      if( ( j < (n-1) ) && (tempArray[j] < tempArray[j+1])) j++;
      if (tempArray[pos] >=tempArray[j]) return;
      temp = tempArray[pos];
      tempArray[pos]=tempArray[j];
      tempArray[j]=temp;
      pos = j;
   } 
}

bool isLeaf( int pos){
   return (pos >=n/2) && (pos < n); 
}

int leftchild(int pos){
   return (2*pos)+1;
}

void removeMax( void ){
   int temp;
   temp=tempArray[n-1];
   tempArray[n-1]=tempArray[0];
   tempArray[0]=temp;
   n--;
   if (n != 0)
      siftdown(0);
}

void msort( int tempArray[], int helpArray[],int left,int right ){
   int curr;
   int mid = (left + right)/2;
   if(left == right) return;
   msort(tempArray, helpArray, left, mid);
   msort(tempArray, helpArray, mid + 1, right);
   for(int i = left; i <= right; i++)
      helpArray[i] = tempArray[i];

  //Do the merge operation back to array
   int i1 = left; int i2= mid + 1;
   for(curr=left; curr<=right; curr++){
      if(i1 == mid +1)                    //Left sublist exhausted
    	tempArray[curr] = helpArray[i2++];
      else if (i2 > right)                    //Right sublist exhausted
        tempArray[curr] = helpArray[i1++];
      else if (helpArray[i1] < helpArray[i2])
  	tempArray[curr] = helpArray[i1++];
      else 
	tempArray[curr] = helpArray[i2++];
   }
}