Write a multithreaded sorting program that works as follows: A list of integers

Question

Write a multithreaded sorting program that works as follows: A list of integers is divided into two smaller lists of equal size. Two separate threads (which we will term sorting threads) sort each sublist using a sorting algorithm of your choice. The two sublists are then merged by a third thread—a merging thread —which merges the two sublists into a single sorted list.

Because global data are shared cross all threads, perhaps the easiest way to set up the data is to create a global array. Each sorting thread will work on one half of this array. A second global array of the same size as the unsorted integer array will also be established. The merging thread will then merge the two sublists into this second array. Graphically, this program is structured according to Figure 4.20.

This programming project will require passing parameters to each of the sorting threads. In particular, it will be necessary to identify the starting index from which each thread is to begin sorting. Refer to the instructions in Project 1 for details on passing parameters to a thread.

The parent thread will output the sorted array once all sorting threads have exited.

Write a program in Java

Explanation / Answer

public class MultithreadedSorting implements Runnable{

private int[] array;

private int length;

private int leftsubarray;

private int rightsubarray;

private int[] resultedArray ;

//constructor

public MultithreadedSorting(int[] array, int i, int j) {

this.array = array;

this.length = array.length;

//this.resultedArray = new int[j-i+1];

this.leftsubarray = i;

this.rightsubarray = j;

}

//run method for threads

@Override

public void run() {

//System.out.println("Starting new thread leftsubarray :"+this.leftsubarray+" rightsubarray "+this.rightsubarray);

sort();

}

//driver programme

public static void main(String[] args) {

//initial array

int array[] ={3,6,4,2,1,10} ;

for(int i:array){

System.out.print(i+" ");

}

System.out.println();

MultithreadedSorting mr = new MultithreadedSorting(array,0,array.length-1);

Thread t = new Thread(mr);

t.start();

//mr.run();

try {

t.join();

} catch (InterruptedException e) {

// TODO Auto-generated catch block

e.printStackTrace();

}

for (int i :mr.resultedArray)

System.out.print(i+" ");

//int res[]= mr.sort(0,array.length-1);

}

//sort method

private void sort() {

if(leftsubarray==rightsubarray && leftsubarray >=0 )

{

this.resultedArray = new int[]{array[leftsubarray]};

return;

}

if(leftsubarray>rightsubarray) return;

int rightsubarrayLimit = this.leftsubarray+(rightsubarray-leftsubarray)/2;

//int leftsubarrayArr[] = sort( leftsubarray,rightsubarrayLimit );

MultithreadedSorting mleftsubarray = new MultithreadedSorting(array,leftsubarray,rightsubarrayLimit);

Thread sortingThread = new Thread(mleftsubarray);

sortingThread.start();

int leftsubarraylimit = 1 + rightsubarrayLimit;   

//int rightsubarrayArr[] = sort(leftsubarraylimit , rightsubarray);

MultithreadedSorting mrightsubarray= new MultithreadedSorting(array,leftsubarraylimit,rightsubarray);

Thread mergingThread = new Thread(mrightsubarray);

mergingThread.start();

try {

sortingThread.join();

mergingThread.join();

} catch (InterruptedException e) {

// TODO Auto-generated catch block

e.printStackTrace();

}

merge(mleftsubarray.resultedArray,mrightsubarray.resultedArray);

}

private int[] merge(int[] leftsubarray, int[] rightsubarray) {

resultedArray = new int[leftsubarray.length+rightsubarray.length];

int r=0;

int i=0;

int j=0;

while(i<leftsubarray.length && j <rightsubarray.length )

{

if( i<leftsubarray.length && j<rightsubarray.length && leftsubarray[i] < rightsubarray[j] )

resultedArray[r++] = leftsubarray[i++];

else if( j<rightsubarray.length && i<leftsubarray.length && rightsubarray[j] < leftsubarray[i])

resultedArray[r++] = rightsubarray[j++];

}

while(i<leftsubarray.length)

{

resultedArray[r++] = leftsubarray[i++];

}   

while(j<rightsubarray.length)

{

resultedArray[r++] = rightsubarray[j++];

}   

//System.out.println("resultedArray "+resultedArray);

return resultedArray;

}

}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.