Implement in C++ please Using java multi-threaded programming to implement multi

Question

Implement in C++ please

Using java multi-threaded programming to implement multi-threaded sorting. Your program will randomly generate 200, 000 numbers. Then, develop two versions of selection sort. The first version is a single threaded program that sorts all the numbers using selection sort algorithm. Measure the time of your program. The second version is a two-threaded program in which each thread sorts half (100, 000) of the numbers and the main thread merges with results from each thread. Measure the time of your multithreaded program. Is there improvement in performance? Implement two versions of merge sort algorithm. One single threaded and one two-threaded. Compare the performance of all four programs.

Explanation / Answer

program import java.util.Random;
public class MergeThreaded
{
public static void final(int[] a, int[] b)
{
int[] result = new int[a.length + b.length];
int i=0;
int j=0;
int r=0;
while (i < a.length && j < b.length)
{
if (a[i] <= b[j]) {
result[r]=a[i];
i++;
r++;
}
else
{
result[r]=b[j];
j++;
r++;
}
if (i==a.length)
{
while (j<b.length)
{
result[r]=b[j];
r++;
j++;
}
}
if (j==b.length)
{
while (i<a.length)
{
result[r]=a[i];
r++;
i++;
}
}
}
}
public static void main(String[] args) throws InterruptedException
{
Random rand = new Random();
int[] original = new int[10000000];
for (int i=0; i<original.length; i++)
{
original[i] = rand.nextInt(1000);
}
long startTime = System.currentTimeMillis();
int[] subArr1 = new int[original.length/2];
int[] subArr2 = new int[original.length - original.length/2];
System.arraycopy(original, 0, subArr1, 0, original.length/2);
System.arraycopy(original, original.length/2, subArr2, 0, original.length - original.length/2);
Worker runner1 = new Worker(subArr1);
Worker runner2 = new Worker(subArr2);
runner1.start();
runner2.start();
runner1.join();
runner2.join();
finalMerge (runner1.getInternal(), runner2.getInternal());
long stopTime = System.currentTimeMillis();
long elapsedTime = stopTime - startTime;
System.out.println("2-thread MergeSort takes: " + (float)elapsedTime/1000 + " seconds");
}
}
class Worker extends Thread
{
private int[] internal;
public int[] getInternal()
{
return internal;
}
public void mergeSort(int[] array)
{
if (array.length > 1)
{
int[] left = leftHalf(array);
int[] right = rightHalf(array);
mergeSort(left);
mergeSort(right);
merge(array, left, right);
}
}
public int[] leftHalf(int[] array)
{
int size1 = array.length / 2;
int[] left = new int[size1];
for (int i = 0; i < size1; i++) {
left[i] = array[i];
}
return left;
}
public int[] rightHalf(int[] array)
{
int size1 = array.length / 2;
int size2 = array.length - size1;
int[] right = new int[size2];
for (int i = 0; i < size2; i++)
{
right[i] = array[i + size1];
}
return right;
}
public void merge(int[] result, int[] left, int[] right)
{
int i1 = 0;   
int i2 = 0;   
for (int i = 0; i < result.length; i++)
{
if (i2 >= right.length || (i1 < left.length && left[i1] <= right[i2]))
{
result[i] = left[i1];   
i1++;
}
else
{
result[i] = right[i2];   
i2++;
}
}
}
Worker(int[] arr)
{
internal = arr;
}
public void run()
{
mergeSort(internal);
}
}
package com.kayan.dsAlgo;
public class MergeSorter implements Runnable
{
private int[] arr;
private int Size;
private int left;
private int right;
private int[] resultArr ;
public MergeSorter(int[] arr, int i, int j)
{
this.arr = arr;
this.Size = arr.length;
this.left = i;
this.right = j;
}
public void run()
{
System.out.println("Starting new thread left :"+this.left+" right "+this.right);
sort();
}
public static void main(String[] args)
{
int arr[] ={3,6,4,2,1,10} ;
MergeSorter mr = new MergeSorter(arr,0,arr.length-1);
Thread t = new Thread(mr);
t.start();
try
{
t.join();
}
catch (InterruptedException e)
{
e.printStackTrace();
}
for (int i :mr.resultArr)
System.out.print(i+" ");
}
private void sort()
{
if(left==right && left >=0 )
{
this.resultArr = new int[]{arr[left]};
return;
}
if(left>right) return;
int rightLimit = this.left+(right-left)/2;
MergeSorter mleft = new MergeSorter(arr,left,rightLimit);
Thread t1 = new Thread(mleft);
t1.start();
int leftlimit = 1 + rightLimit;
MergeSorter mright= new MergeSorter(arr,leftlimit,right);
Thread t2 = new Thread(mright);
t2.start();
try
{
t1.join();
t2.join();
}
catch (InterruptedException e)
{
e.printStackTrace();
}
merge(mleft.resultArr,mright.resultArr);
}
private int[] merge(int[] left, int[] right)
{
resultArr = new int[left.length+right.length];
int r=0;
int i=0;
int j=0;
while(i<left.length && j <right.length )
{   
if( i<left.length && j<right.length && left[i] < right[j] )
resultArr[r++] = left[i++];
else
if( j<right.length && i<left.length && right[j] < left[i])
resultArr[r++] = right[j++];
}   
while(i<left.length)
{
resultArr[r++] = left[i++];
}
while(j<right.length)
{
resultArr[r++] = right[j++];
}
return resultArr;
}
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

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