parent-child cooperation and parallel merge sort

[rutwvu]

I was asked to write a program, based on parent-child cooperation, which uses a “parallel” merge sort to a sequence of 800 numbers from a text file.I have to read the sequence of 800 integers, which I store in an array, and then pass half of them to a child, and the other half to the second child of the parent class. I have to do this until only 100 numbers are left in each child. When I have reached this the numbers must be sorted, which I am doing using a bubble sort.Once these are sorted the must be returned to the parent processes and merged creating one sequence of sorted numbers. The final sequence must be stored in a file. The splitting of the parent must be done using fork(). I have no idea how to manipulate the parent and child relationship to do splitting and then once again merging. I am not looking for an answer but help on how to do this anything would be great.

[Adak]

First, welcome to the forum, Rutwvu! ;)

If you need to do a merge sort, why entertain the idea of using a bubble sort? Please don't do that! USE MERGE SORT!

Bubble Sort is fine for < 100 things, but for anything else, it's just for entertainment unless the data is nearly in sorted order - then it's good (but Insertion sort is just as good, and considerably more capable, and Shell sort - which is Insertion sort using gaps, absolutely ROCKS, compared to either one).

There are four sorting algorithms that are TOP tier, for a large quantity of thing to be sorted**:

1) Quicksort - can be easily optimized with a call to Insertion sort for the small sub-arrays! VERY fast!

2) Merge Sort Uses more memory, but also very fast, and can be optimized extensively.

3) Heap Sort
4) Optimized Shell Sort

Not listed are variants like Intra Sort, which use both Quicksort and Heap Sort

Radix Sort might be added to the list, but it hasn't impressed me on the newer PC hardware. Might be just me.

** I mean ROCK the house sorting. If you don't use Quicksort or Merge Sort, you should have a good reason why you didn't.

I didn't fully understand your "100 numbers are left in each child..." part of the description, but in any case, it's up to YOU to get this assignment started - we wont' do that for you. (common on programming help forums).

Post your code, and ask specific questions. We will try to help. Use code tags, for your code.

[aspire1]

Looks like you are learning the hard way parallel programming. MPI has all the tools to do this relatively painlessly.

Doing it the hard way I guess: create original array containing all the data and two other arrays half the size, create your two sub processes, each subprocess sorts one of the smaller arrays. Parent process waits for the two subprocesses to finish and then merges the two smaller arrays back into the bigger one.

[rutwvu]

So far this is my code when dealing with the parents and children I don't think this is even close to right but for the assignment we have to break it down into 8 different arrays containing 100 numbers each sort them and go back through and merge all the numbers together. The print statements are also required for each move we make we must print out the current pid and the parent pid. Currently this won't even compile with errors of undefined reference to getppid and fork.

child_pid=fork();
if (child_pid<0)
{ printf("Failed to fork\n"); exit(-1); }


printf("Current Process PID: %ld, Parent PID:%ld \n",
(long)getpid(), (long)getppid());
readFile(file_name);
printf("%ld 800 numbers stored\n", (long)getpid());
printf("%ld Creating Child processes", (long)getpid());


child_pid=fork();
if (child_pid<0)
{ printf("Failed to fork\n"); exit(-1); }


for (i=0; i<1; i++){
if (child_pid=fork() <= 0)
break;


printf("Current ProcessID: %ld, Parent ID:%ld \n",
(long)getpid(), (long)getppid());
printf("%ld 400 numbers stored\n", (long)getpid());
printf("%ld Creating Child processes",(long)getpid());
}//end for

[Adak]

Show your include headers, main() etc.

AND USE CODE TAGS around your code, or lots of people will not read through your code

[rutwvu]

well this is what i have come up with so far. This is the first step of the process separating my main array into two separate arrays this must be done two more times to ultimately get to 8 arrays of 100 numbers. When the program comes back around to the parents the information must be merged together. If this is correct and someone could provide a little help how to proceed down the layers.

for(i = 0; i < 2; i++){// creating two children from the parents
    if(child_pid=fork()<=0)
        break;

    if (child_pid==0 && n ==0)// first child
    {
        printf("Current Process PID: %ld, Parent PID:%ld \n",
          (long)getpid(), (long)getppid());
        for(i = 0; i <400; i ++)
        {
            array1[i] =  main_array[i];
        }//end for
        printf("%ld: 400 numbers stored\n", (long)getpid());
        n = 1;
    }//end if
    else if(child_pid == 0 && n == 1)//second child
    {
        int array12[400];
        printf("Current Process PID: %ld, Parent PID:%ld \n",
          (long)getpid(), (long)getppid());
        for(i = 400; i <800; i ++)
        {
            array12[i] =  main_array[i];
        }
        printf("%ld: 400 numbers stored\n", (long)getpid());
    }//end else if
    else //parent
    {
        wait(NULL);

    }//end else
    }// end for

[jayster419]

well this is what i have come up with so far. This is the first step of the process separating my main array into two separate arrays this must be done two more times to ultimately get to 8 arrays of 100 numbers. When the program comes back around to the parents the information must be merged together. If this is correct and someone could provide a little help how to proceed down the layers.

for(i = 0; i < 2; i++){// creating two children from the parents
if(child_pid=fork()<=0)
break;

if (child_pid==0 && n ==0)// first child
{
printf("Current Process PID: %ld, Parent PID:%ld \n",
(long)getpid(), (long)getppid());
for(i = 0; i <400; i ++)
{
array1[i] = main_array[i];
}//end for
printf("%ld: 400 numbers stored\n", (long)getpid());
n = 1;
}//end if
else if(child_pid == 0 && n == 1)//second child
{
int array12[400];
printf("Current Process PID: %ld, Parent PID:%ld \n",
(long)getpid(), (long)getppid());
for(i = 400; i <800; i ++)
{
array12[i] = main_array[i];
}
printf("%ld: 400 numbers stored\n", (long)getpid());
}//end else if
else //parent
{
wait(NULL);

}//end else
}// end for

[rutwvu]

Thanks for the help and the warning have no idea what code tags are