Please help with merge sort with threading!!!! Please use comments in your code,
ID: 3702062 • Letter: P
Question
Please help with merge sort with threading!!!! Please use comments in your code, thank you in advance.
These files are a simple implementation of a parallel merge sort using pthreads. The implementation of the merge sort is in par_merge.c, and the code to test it is in test_sort.c. Look at the Makefile. If you type ‘make’, the code will be compiled and tested.
Your job is to rewrite function pmerge_sort in file par_merge.c. Please do the following:
1. Read the code to understand how it works. If you do know how merge sort works, look online or in your algorithms book. It’s an elegant recursive sorting algorithm and suitable for a concurrent implementations.
2. Look at function pmerge_sort carefully. It creates two threads, each of which sorts half the data. Then the results from these two sorts are merged.
3. Function pmerge_sort creates two threads, but this is wasteful, because pmerge_sort could sort half the data itself, and create only one new thread to sort the other half.
I want you to modify function pmerge_sort so that it creates only one new thread, not two. Do not modify any code except for pmerge_sort! Also, do not modify the arguments or return type of pmerge_sort.
This code is simplistic in that it will create many threads if the input array is large. Don’t try running your code on very large inputs. A more realistic algorithm would use the number of available cores as a parameter, and not create more threads than the number of cores.
Here are the files you'll need:
par_merge.c:
/*
* A parallel merge sort using pthreads
*/
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
typedef struct sort_args_t {
float *x; // array to be sorted
int len; // length of array
} Sort_args;
// sort and return float array x, of length n
// using gnome sort
float *gsort(float *x, int n) {
int i = 0;
while (i < n) {
if (i == 0 || x[i] >= x[i-1]) {
i++;
} else {
// swap x[i] and x[i-1]
float temp = x[i];
x[i] = x[i-1];
x[i-1] = temp;
i--;
}
}
return x;
}
// return a new array obtained by merging arrays
// x and y, where m is the length of x and n
// is the length of y. The input arrays are
// assumed to be sorted. If they are, the output
// will be sorted.
float *merge(float *x, int m, float *y, int n) {
// x and y are merged into new array z
float *z = (float *)malloc((m + n)*(sizeof(float)));
int i = 0; // index into x
int j = 0; // index into y
int k = 0; // index into z
while (i < m || j < n) {
// pick the x element if there are no more y's, or
// if there are x's and y's and the x value is smaller
if (j == n || (i < m && x[i] < y[j])) {
z[k] = x[i];
i++;
} else {
z[k] = y[j];
j++;
}
k++;
}
return z;
}
// sort and return float array x, of length n
// using merge sort
void *pmerge_sort(void *args) {
// unpack arguments
Sort_args *sargs = (Sort_args *)args;
float *x = sargs->x;
int n = sargs->len;
// if n < k, the array is sorted directly
// using another sort algorithm
int k = 100;
if (n < k) {
return(gsort(x, n));
}
// create 2 threads; each sorts half the data
int m = ((float)n)/2.0;
// pack arguments to recursive call
Sort_args args1, args2;
args1.x = x;
args1.len = m;
args2.x = &x[m];
args2.len = n-m;
int rc;
pthread_t p1, p2;
rc = pthread_create(&p1, NULL, pmerge_sort, (void *)&args1); assert(rc == 0);
rc = pthread_create(&p2, NULL, pmerge_sort, (void *)&args2); assert(rc == 0);
// merge the results from the threads
float *x1, *x2;
pthread_join(p1, (void **) &x1);
pthread_join(p2, (void **) &x2);
float *y = merge(x1, m, x2, n-m);
// copy the result back to x and free y
memcpy((void *)x, (void *)y, n*sizeof(float));
free(y);
return (void *)x;
}
// sort array x
void merge_sort(float *x, int n) {
// call recursive helper function
Sort_args args;
args.x = x;
args.len = n;
pmerge_sort((void *)&args);
}
test_sort.c:
/*
* Test a sort algorithm for correctness
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include "merge_sort.h"
// test merge sort
int main() {
// size of test data array
int n = 10000;
// initialize input
float *x = (float *)malloc(n * sizeof(float));
int i;
for (i = 0; i < n; i++) {
x[i] = drand48();
}
merge_sort(x, n);
// check the output for correctness
float last = -1.0;
for (i = 0; i < n; i++) {
if (x[i] < last) {
printf("sort error at element %d ", i);
exit(1);
}
last = x[i];
}
printf("output was sorted correctly ");
return 0;
}
merge_sort.h:
void merge_sort(float *, int);
Makefile:
test: pmsort
./pmsort
pmsort: par_merge.c test_sort.c merge_sort.h
gcc -o pmsort test_sort.c par_merge.c -pthread -Wall
clean:
rm -f pmsort *~
Explanation / Answer
void pmerge_sort(int x[], int tmp[], int lpos, int rpos, int rend)
{
int i, lend, n, tmppos;
lend = rpos - 1;
tmppos = lpos;
n = rend - lpos + 1;
while(lpos <= lend && rpos <= rend)
{
if(x[lpos] <= x[rpos])
tmp[tmppos++] = x[lpos++];
else
tmp[tmppos++] = x[rpos++];
}
while(lpos <= lend)
tmp[tmppos++] = x[lpos++];
while(rpos <= rend)
tmp[tmppos++] = x[rpos++];
for(i = 0; i < n; i++, rend--)
x[rend] = tmp[rend];
}
Void sortc (int x[], int tmp[], int left, int right)
{
int center;
if(left < right)
{
center = (left + right) / 2;
MSort(x, tmp, left, center);
MSort(x, tmp, center + 1, right);
Merge(x, tmp, left, center + 1, right);
}
}
void pmerge_sort (int x[], int n)
{
int *tmpa;
tmpa = malloc(sizeof(int) * n);
MSort(x, tmpa, 0, n-1);
free(tmpa);
}
main()
{
int i, n, x[10];
printf("Enter the number of elements :: ");
scanf("%d",&n);
printf("Enter the elements :: ");
for(i = 0; i < n; i++)
{
scanf("%d",&x[i]);
}
pmerge_sort(x,n);
printf("The sorted elements are :: ");
for(i = 0; i < n; i++)
{
scanf("%d",&x[i]);
}
pmerge_sort (x,n);
printf("The sorted elements are :: ");
for(i = 0; i < n; i++)
printf("%d ",x[i]);
printf(" ");
}
void pmerge_sort(int x[], int tmp[], int lpos, int rpos, int rend)
{
int i, lend, n, tmppos;
lend = rpos - 1;
tmppos = lpos;
n = rend - lpos + 1;
while(lpos <= lend && rpos <= rend)
{
if(x[lpos] <= x[rpos])
tmp[tmppos++] = x[lpos++];
else
tmp[tmppos++] = x[rpos++];
}
while(lpos <= lend)
tmp[tmppos++] = x[lpos++];
while(rpos <= rend)
tmp[tmppos++] = x[rpos++];
for(i = 0; i < n; i++, rend--)
x[rend] = tmp[rend];
}
Void sortc (int x[], int tmp[], int left, int right)
{
int center;
if(left < right)
{
center = (left + right) / 2;
MSort(x, tmp, left, center);
MSort(x, tmp, center + 1, right);
Merge(x, tmp, left, center + 1, right);
}
}
void pmerge_sort (int x[], int n)
{
int *tmpa;
tmpa = malloc(sizeof(int) * n);
MSort(x, tmpa, 0, n-1);
free(tmpa);
}
main()
{
int i, n, x[10];
printf("Enter the number of elements :: ");
scanf("%d",&n);
printf("Enter the elements :: ");
for(i = 0; i < n; i++)
{
scanf("%d",&x[i]);
}
pmerge_sort(x,n);
printf("The sorted elements are :: ");
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.