/*                     CSC145/290  Assignment 6.

		       Sorting with Threads.

 In the included program below is an implementation of the quicksort
algorithm (for arrays).  Also included are some routines to record the
running time of the algorithm (make sure you measure only the
algorithm, not IO time), as well as routines for generating random
numbers for an array.

 You are to modify it so that it uses threads to sort the two partitions
created by the "partition" function.  That is, you are to replace the
two recursive calls to quicksort with two "pthread_create"s.  Follow
the example done in class.

 Run experiments on arrays of different sizes.  Report on the performance
of the quicksort, for both the conventional verison and the threaded version.
*/


#include<stdio.h>
#include<stdlib.h>
#include <sys/time.h>

#define intRange 1000000.0
#define Len 80000     /*  size of array   */

/* sorting random arrays */

// returns elapsed time in milliseconds
int elapsedtime(struct timeval * t1, struct timeval * t2)
{  int dsec, dusec;
   dsec = t2->tv_sec - t1->tv_sec;
   dusec = t2->tv_usec - t1->tv_usec;
   return (dsec * 1000) + (dusec / 1000);
}

// generates random values for an array.
void genarray(int A[])
{  int i, temp;   // loop counter
   for(i=0;i<Len;i++)
        A[i] = 1+(int) (intRange * rand()/(RAND_MAX+1.0));
}

/* quicksort routines  */

// partitions array on pivot, returns end index of 1st partition.
int partition(int A[], int pivot, int begin, int end)
  { int counter, i, temp;
    counter = begin;
    for (i=begin;i<=end;i++)
     { if (A[i] <= pivot) 
         { temp = A[counter];
    	   A[counter] = A[i];
           A[i] = temp; 
           counter++; 
         }
     } 
    if (counter > begin) return counter-1; else return begin;
  }

// returns index of pivot, -1 if partition already sorted.
// In this version of quicksort, the pivot is the first number
// not in order, e.g., for 2 3 5 4 9 2, the pivot is the 4 (or rather
// its position in the array).
int findpivot(int A[], int begin, int end)
 { int i;
   i = begin;
   while ((i < end) && (A[i] <= A[i+1])) {i++;}
   if (i == end) return -1; else return (i+1);
 }

void quicksort(int A[], int begin, int end)
 { int pivoti;  // index of pivot for current partition
   int p;       // partition breakoff point
   pivoti = findpivot(A,begin,end);   // returns index, not pivot itself!
   if (pivoti >= 0)   // -1 means there's no pivot
    { p = partition(A,A[pivoti], begin, end);

          quicksort(A,begin,p);

      if (p<end) 
          quicksort(A,p+1,end);
    }
 }  // end qsort


int main()
{
   struct timeval startTime, endTime;
   int duration, qsortTime, i;
   int A[Len];
   gettimeofday(&startTime,NULL);
   srand(startTime.tv_usec % 10000);  // uses time to set random seed    
   
   genarray(A);   // creates random array

   gettimeofday(&startTime,NULL);
   quicksort(A,0,Len-1);
   gettimeofday(&endTime,NULL);

   duration = elapsedtime(&startTime,&endTime);

   for(i=0;i<Len;i++) printf("%d ",A[i]);

   printf("\nTime to sort ~== %dms\n", duration);
   exit(0);
}