Show transcribed image text

Expert Answer

• 
  Karan Bagoria answered this

  Was this answer helpful?

  7 answers

  Here we are implementing the quicksort algorithm using the cucurrency in C with Pthreads.
  The quicksort algorithm sorts the list by dividing the complete list into two sublists
  Afterwards in one sublist are smaller numbers are placed and in other half of the sublist the
  larger numbers are placed.
  So here is the code for Quicksort Using Pthread which will help you in the first part of the question.
  (All the information regarding the code has been provided along with the code)
  ::::::CODE::::::
  #include <pthread.h>
  #include <stdlib.h>
  #include <stdio.h>
  #include <stdbool.h>
  #include <time.h>
  #include <sys/time.h>

  double ReadTimerFunction() {
  static bool initialized = false;
  static struct timeval start;
  struct timeval end;
  if( !initialized )
  {
  gettimeofday( &start, NULL );
  initialized = true;
  }
  gettimeofday( &end, NULL );
  return (end.tv_sec - start.tv_sec) + 1.0e-6 * (end.tv_usec - start.tv_usec);
  }
  double StartingTime, EndTime; //Crreating variables which will store the start and the end time

  typedef struct QuickSortStart //We are defining a structure
  {
  int *array;
  int Lower;
  int Higher;
  int DepthThreadCreate;
  } quickSort_parameters;

  void swapping(int* a, int* b) //This is the function for swapping the values it will be used further many times
  {
     int t = *a;
     *a = *b;
     *b = t;
  }
  int partition (int *array, int Lower, int Higher, int pivot)
  {
     int ValueOfPivot = array[pivot];
  swapping(&array[pivot],&array[Higher]); // pivot
     int s = Lower; // It is the Index of smaller element
     for (int i = Lower; i <Higher; i++)
     {   // If current element is smaller than or equal to pivot then we will apply the condition given beLower
        
         if (array[i] <= ValueOfPivot)
         {
             swapping(&array[i], &array[s]);
  s++; // Here wee are incrementing index of smaller element
         }
     }
     swapping(&array[s], &array[Higher]);
     return s;
  }
  void quickSort(int *array, int Lower, int Higher)
  {
     if (Lower < Higher)
     {
  int PositionOfPivotition = Lower+ (Higher-Lower)/2;
  PositionOfPivotition= partition(array, Lower, Higher, PositionOfPivotition);
         quickSort(array, Lower, PositionOfPivotition - 1);
         quickSort(array, PositionOfPivotition + 1, Higher);
     }
  }
  void ConcurrentQuickS(int *array, int Lower, int Higher, int DepthThreadCreate);
  void* WorkerQuickS(void * Initial_Value){
  quickSort_parameters* parameters = Initial_Value;
  ConcurrentQuickS(parameters->array, parameters->Lower, parameters->Higher,parameters->DepthThreadCreate);
  return NULL;
  }
  void ConcurrentQuickS(int *array, int Lower, int Higher, int DepthThreadCreate){
  if (Lower < Higher){

  int PositionOfPivot = Lower + (Higher - Lower)/2;
  PositionOfPivot = partition(array, Lower, Higher, PositionOfPivot);
  pthread_t thread;

  if (DepthThreadCreate > 0){
  quickSort_parameters ThreadParameter = {array, Lower, PositionOfPivot-1, DepthThreadCreate};
  int result;
  //Here we will now creat the thread using CreatePthread
  result = CreatePthread(&thread, NULL, WorkerQuickS, &ThreadParameter);
  //Now we are recursively calling for 2nd time in the right part
  ConcurrentQuickS(array, PositionOfPivot+1, Higher, DepthThreadCreate);
  pthreadJoining(thread, NULL);
  } else{
  quickSort(array, Lower, PositionOfPivot-1);
  quickSort(array, PositionOfPivot+1, Higher);
  }
  }
  }
  //Now we will make a main function to implement all the functions defined earlier
  int main(int arg1, char **arg2){
  int DepthThreadCreate = 0;
  if (arg1 > 1){
  DepthThreadCreate = strtol(arg2[1], NULL, 10);
  }
  int size = 8;
  if (arg1 > 2){
  size = strtol(arg2[2], NULL, 10);
  }
  int *ElementsInarrayay = malloc(size* sizeof(long));
  for (int i=0 ; i<size ; i++){
  ElementsInarrayay[i] = rand()%999;
  }
  printf("Unsorted Elements\n");
  for(int i=0; i<sizeof(ElementsInarrayay)-1; i++){
  printf(" %d ", ElementsInarrayay[i]);
  }
  StartingTime = ReadTimerFunction();
  ConcurrentQuickS(ElementsInarrayay, 0, size-1, DepthThreadCreate);
  EndTime = ReadTimerFunction();
  printf("\n");
  printf("Elements are Sorted\n");
  for(int i=0; i<sizeof(ElementsInarrayay)-1; i++){
  printf("%d ", ElementsInarrayay[i]);
  }
  printf("\n");
  printf("Execution time: %lf secs\n", EndTime - StartingTime);
  free(ElementsInarrayay);
  return 0;
  }

  // CODE ENDS HERE

  SO THIS IS HOW WE IMPLEMENT QUICKSORT USING PTHREAD