We are expected to do the following in C language via a linux terminal.

Your final lab assignment is to implement psort.c. This program takes as input a file containing a list of integers and outputs their sorted order. The caveat to this seemingly-simple assignment is that your program will run not one but three sorting algorithms simultaneously and only report the result from the first one to terminate. Once one algorithm terminates, it should cancel the others to avoid unnecessary wastage of precious CPU cycles. Your program should also report the algorithm that finishes first. See below for an example.

The code for reading the input file as well as other bits of skeleton code is provided. You should provide implementations for the three sorting functions (selection sort, merge sort, and quick sort). As were sure youve written these algorithms before, feel free to re-implement them yourself or find an existing implementation somewhere. However, be sure to provide a source if you opt for the latter option. But if you also want to add some more sorting algorithms to the mix, feel free!

The bulk of the work will be in setting up the threads, orchestrating the cancellations, etc. Feel free to modify the structure given to you. However, you must use threads and cancellations to perform the task outlined here.

Here is the C file that we have to implement, please use threads and cancelations:

#include #include #include

/* Prints an array in a nicey-nice way */

void printarr(int* arr, int n) {

int i;

for(i = 0; i < n; i++) {

printf("%d", arr[i]);

if(i != n-1) printf(", ");

}

printf(" ");

}

/* Returns 1 if array is sorted, 0 otherwise */

int is_sorted(int* arr, int n) {

int i;

for(i = 1; i < n; i++)

if(arr[i-1] > arr[i])

return 0;

return 1;

}

/* Feel free to modify this struct! */

typedef struct {

int tid; /* thread ID */

pthread_t* thrds; /* array of threads */

int num_threads; /* length of threads array */

int* arr; /* array to be sorted */

int n; /* length of array to be sorted */

int* (*sort)(int*,int); /* sorting algorithm */

} psortarg;

int* selection_sort(int* arr, int n) {

/* TODO implement me! */

return NULL;

}

int* merge_sort(int* arr, int n) {

/* TODO implement me! */

return NULL;

}

int* quick_sort(int* arr, int n) {

/* TODO implement me! */

return NULL;

}

void* parallel_sort(void* _arg) {

psortarg* arg = (psortarg*)_arg;

/* Get local copy of arguments */

int tid = arg->tid;

pthread_t* thrds = arg->thrds;

int num_threads = arg->num_threads;

int* arr = arg->arr;

int n = arg->n;

/* Run sorting algorithm given to this thread */

/* Ensure that the first algorithm to finish cancels all the others! */

/* TODO implement me! */

/* Done! */

pthread_exit(NULL);

}

int main(int argc, char* argv[]) {

FILE* infile;

int n, i;

int* arr;

int fastestalg = -1;

/* Verify we have enough arguments */

if(argc != 2) {

printf("usage: ./psort ");

exit(0);

}

/* Read array from file */

infile = fopen(argv[1], "r");

fscanf(infile, "%d", &n);

arr = (int*)malloc(n * sizeof(int));

if(!arr) {

printf("error: failed to malloc array ");

exit(10);

}

for(i = 0; i < n; i++)

fscanf(infile, "%d", arr+i);

fclose(infile);

/* Setup threads to run each sorting algorithm in parallel */

/* Remember to ensure that the first algorithm to finish cancels all the others! */

/* TODO implement me! */

/* Output final result */

printf(" finished first! ");

printf("in : ");

printarr(arr, n);

printf("out: ");

printarr(arr, n);

printf("sorting worked? %s ", (is_sorted(arr,n) ? "yes" : "no"));

/* Clean up! */

free(arr);

return 0;

}