Question

Please give a output Linux/Ubuntu and how to run it (compile) this program ,my assigment is below : :

Merge Sort algorithm using 2 processes

a.)

Define an integer array of 100 integers. Populate this array with random numbers. You can use

int rand(void);

function. Do not forget to initialize this function.

You will sort the numbers in the array using merge-sort algorithm. In merge sort algorithm the half of the array will be sorted by one process and second half will be sorted by another process.

Use

pid_t fork(void);

system call to create a child process. Then

send the second half of the array to the child process using a pipe. The parent process and child process sort their arrays concurrently. Then child process send its sorted array to the parent process using a pipe. The parent process merges the sorted arrays and prints it to the screen.

to create a pipe you can use

int pipe(int pipefd[2]);

system call.

b.) use message queue to pass arrays between two processes in the example above. To create a message queue you can use

int msgget(key_t key, int msgflg);

system call. To send/receive messages use

 int msgsnd(int msqid, const void *msgp, size_t msgsz, int msgflg);
 ssize_t msgrcv(int msqid, void *msgp, size_t msgsz, long msgtyp, int msgflg);

hint: use 2 message queues.

You are going to submit 2 programs, the first one with pipes and the second one with message queues.

You should not waste your time on merge-sort algorithm. Use the merge sort algorithm given below

void mergesort(int a[],int i,int j)

{

int mid;

if(i<j)

{

mid=(i+j)/2;

mergesort(a,i,mid); //left recursion

mergesort(a,mid+1,j); //right recursion

merge(a,i,mid,mid+1,j); //merging of two sorted sub-arrays

}

}

void merge(int a[],int i1,int j1,int i2,int j2)

{

int temp[50]; //array used for merging

int i,j,k;

i=i1; //beginning of the first list

j=i2; //beginning of the second list

k=0;

while(i<=j1 && j<=j2) //while elements in both lists

{

if(a[i]<a[j])

temp[k++]=a[i++];

else

temp[k++]=a[j++];

}

while(i<=j1) //copy remaining elements of the first list

temp[k++]=a[i++];

while(j<=j2) //copy remaining elements of the second list

temp[k++]=a[j++];

//Transfer elements from temp[] back to a[]

for(i=i1,j=0;i<=j2;i++,j++)

a[i]=temp[j];

}

Answer 1

#include<iostream>
using namespace std;
public class Merge
{

int arr[10][10];
int rand(void);

void mergesort(int a[],int i,int j)

{

int mid;

if(i<j)

{

mid=(i+j)/2;

mergesort(a,i,mid); //left recursion

mergesort(a,mid+1,j); //right recursion

merge(a,i,mid,mid+1,j); //merging of two sorted sub-arrays

}

}

void merge(int a[],int i1,int j1,int i2,int j2)

{

int temp[50]; //array used for merging

int i,j,k;

i=i1; //beginning of the first list

j=i2; //beginning of the second list

k=0;

while(i<=j1 && j<=j2) //while elements in both lists

{

if(a[i]<a[j])

temp[k++]=a[i++];

else

temp[k++]=a[j++];

}

while(i<=j1) //copy remaining elements of the first list

temp[k++]=a[i++];

while(j<=j2) //copy remaining elements of the second list

temp[k++]=a[j++];

//Transfer elements from temp[] back to a[]

for(i=i1,j=0;i<=j2;i++,j++)

a[i]=temp[j];

}
}

2.ans:

int main()

{

int rand(void);

pid_t fork(void);

int pipe(int pipefd[2]);

int msgget(key_t key, int msgflg);

int msgsnd(int msqid, const void *msgp, size_t msgsz, int msgflg);
ssize_t msgrcv(int msqid, void *msgp, size_t msgsz, long msgtyp, int msgflg);
}

int rand(void)

{

int temp[50]; //array used for merging

int i,j,k;

i=i1; //beginning of the first list

j=i2; //beginning of the second list

k=0;

while(i<=j1 && j<=j2) //while elements in both lists

{

if(a[i]<a[j])

temp[k++]=a[i++];

else

temp[k++]=a[j++];

}

while(i<=j1) //copy remaining elements of the first list

temp[k++]=a[i++];

while(j<=j2) //copy remaining elements of the second list

temp[k++]=a[j++];

//Transfer elements from temp[] back to a[]

for(i=i1,j=0;i<=j2;i++,j++)

a[i]=temp[j];

)