Write a multithreaded sorting program that works as follows: A list of integers
ID: 3916804 • Letter: W
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.
Note: Solve it using merge sort in java
Explanation / Answer
// Defines a class MergeSort derived from Runnable interface
public class MergeSort implements Runnable
{
// Data member to store data
private int[] originalData;
// Data member to store size
private int dataSize;
// Data member to store left position
private int leftPos;
// Data member to store right position
private int rightPos;
// Data member to store sorted data
private int[] sortedData ;
// Default constructor definition
public MergeSort(int[] data, int l, int r)
{
originalData = data;
dataSize = data.length;
leftPos = l;
rightPos = r;
}// End of default constructor
@Override
// Overrides the runs method
public void run()
{
System.out.println("Thread left position: " + this.leftPos + " right position: " + this.rightPos);
// Calls the method to sort the data
sortData();
}// End of method
// Method to sort the data
private void sortData()
{
// Checks if left position is equals to right position and right position is greater than or equals to zero
if(leftPos == rightPos && leftPos >= 0 )
{
// Assigns the array original data left position to sorted data array
this.sortedData = new int[]{ originalData[leftPos] };
return;
}// End of if condition
// Checks if left position is greater than right position then return from the function
if(leftPos > rightPos)
return;
// Calculates the right limit for split
int rightLimit = this.leftPos + (rightPos - leftPos) / 2;
// Creates an object of the class MergeSort for left side using parameterized constructor
MergeSort msLeft = new MergeSort(originalData, leftPos, rightLimit);
// Creates a thread for merge sort left
Thread thOne = new Thread(msLeft);
// Calls the start method
thOne.start();
// Calculates the left limit for split
int leftlimit = 1 + rightLimit;
// Creates an object of the class MergeSort for left side using parameterized constructor
MergeSort msRight= new MergeSort(originalData, leftlimit, rightPos);
// Creates a thread for merge sort right
Thread thTwo = new Thread(msRight);
// Calls the start method
thTwo.start();
// try block begins
try
{
// Calls the join method for both the threads
thOne.join();
thTwo.join();
}// End of try block
// Catch block to handle InterruptedException
catch (InterruptedException ie)
{
ie.printStackTrace();
}// End of catch block
// Calls the method to merge the left and right array
mergeData(msLeft.sortedData, msRight.sortedData);
}// End of method
// Method to merge two array and return the merged array
private int[] mergeData(int[] leftData, int[] rightData)
{
// Dynamically allocates memory to the array with left and right array size
sortedData = new int[leftData.length + rightData.length];
// Initializes counter to zero
int counterSortData = 0;
int counterOne = 0;
int counterTwo = 0;
// Loops till counter one value is less than left array length
// and counter two value is less than right array length
while(counterOne < leftData.length && counterTwo < rightData.length )
{
if(counterOne < leftData.length && counterTwo < rightData.length && leftData[counterOne] < rightData[counterTwo] )
// Stores the current index position (counterOne) of left array data in current index position (counterSortData) of sortyedData array
// Increase both counter by one
sortedData[counterSortData++] = leftData[counterOne++];
else if(counterTwo < rightData.length && counterOne < leftData.length && rightData[counterTwo] < leftData[counterOne])
// Stores the current index position (counterTwo) of left array data in current index position (counterSortData) of sortyedData array
// Increase both counter by one
sortedData[counterSortData++] = rightData[counterTwo++];
}// End of while loop
// Loops till counter one value is less than the length of the left array data
while(counterOne < leftData.length)
{
// Stores the current index position (counterOne) of left array data in current index position (counterSortData) of sortyedData array
// Increase both counter by one
sortedData[counterSortData++] = leftData[counterOne++];
}// End of while loop
// Loops till counter two value is less than the length of the right array data
while(counterTwo < rightData.length)
{
// Stores the current index position (counterTwo) of right array data in current index position (counterSortData) of sortyedData array
// Increase both counter by one
sortedData[counterSortData++] = rightData[counterTwo++];
}// End of while loop
// Returns the sorted array
return sortedData;
}// End of method
// main method definition
public static void main(String[] args)
{
// Creates an array and stores data
int data[] = {3, 6, 4, 2, 1, 10, 41, 45, 9, 62} ;
MergeSort ms = new MergeSort(data, 0, data.length - 1);
// Creates a thread
Thread t = new Thread(ms);
// Calls the start method
t.start();
// try block begins
try
{
// Calls the join method
t.join();
}// End of try block
// Catch block to handle InterruptedException
catch (InterruptedException e)
{
e.printStackTrace();
}// End of catch block
// Loops till the length of the sorted data to display
for (int value : ms.sortedData)
System.out.print(value + " ");
}// End of main method
}// End of class
Sample Output:
Thread left position: 0 right position: 9
Thread left position: 5 right position: 9
Thread left position: 0 right position: 4
Thread left position: 5 right position: 7
Thread left position: 8 right position: 9
Thread left position: 3 right position: 4
Thread left position: 0 right position: 2
Thread left position: 7 right position: 7
Thread left position: 5 right position: 6
Thread left position: 9 right position: 9
Thread left position: 8 right position: 8
Thread left position: 3 right position: 3
Thread left position: 4 right position: 4
Thread left position: 0 right position: 1
Thread left position: 6 right position: 6
Thread left position: 2 right position: 2
Thread left position: 1 right position: 1
Thread left position: 0 right position: 0
Thread left position: 5 right position: 5
1 2 3 4 6 9 10 41 45 62
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.