Alright so I asked this question and chegg answered it but it was completely wro
ID: 3571829 • Letter: A
Question
Alright so I asked this question and chegg answered it but it was completely wrong. They made it one giant class which is not right. And they called classes that did not exist. Please help.
1. Modify the MergeSorter class to convert it into a parallelized MergeSort that uses multiple threads to perform the sorting task. The maximum number of threads to be used should be passed as an argument to the sorting method. Your program should not create more threads than the allowed maximum. Call the modified class ParallelMergeSorter.
2. Modify the SortTester class provided to run some simulations using the parallelized ParallelMergeSorter,to assess the possible speedup from using multiple threads, as opposed to a single thread. Call the modified class ParallellSortTester. Each experiment should time the sorting speed wiht different sizes of random number arryas, starting from an array of size 1000 and doubling the size of the arrya at each round, for 15 rounds (last round arrya size should be 16384000). Run the experiment wiht different number of threads starting form one thread and doubling the number of threads, up to the number of CPU cores available in your system. The number cores available in your computer can be obtained from Java using the following statement:
Runtime.getRuntime().availableProcessors();
Copy the output results and paste them into a text file. Submit your output together with your code. Here are examples of output from my computer:
1 threads:
1000 elements => 5 ms
2000 elements => 6 ms
4000 elements => 13 ms
8000 elements => 26 ms
16000 elements => 5 ms
32000 elements => 10 ms
64000 elements => 14 ms
128000 elements => 23 ms
256000 elements => 0 ms
512000 elements => 107 ms
1024000 elements => 245 ms
2048000 elements => 541 ms
4096000 elements => 1243 ms
8192000 elements => 2848 ms
16384000 elements => 6425 ms
MergeSorter code given:
import java.util.*;
public class MergeSorter{
public static <E> void sort(E[] a, Comparator<? super E> comp){
mergeSort(a, 0, a.length - 1, comp);
}
private static <E> void mergeSort(E[] a, int from, int to, Comparator<? super E> comp) {
if (from == to) {
return;
}
int mid = (from + to) / 2;
// Sort the first and the second half
mergeSort(a, from, mid, comp);
mergeSort(a, mid + 1, to, comp);
merge(a, from, mid, to, comp);
}
@SuppressWarnings("unchecked")
private static <E> void merge(E[] a, int from, int mid, int to, Comparator <? super E> comp) {
int n = to - from + 1;
Object[] b = new Object[n];
int i1 = from;
int i2 = mid + 1;
int j = 0;
while (i1 <= mid && i2 <= to) {
if (comp.compare(a[i1], a[i2]) < 0) {
b[j] = a[i1];
i1++;
} else {
b[j] = a[i2];
i2++;
}
j++;
}
while (i1 <= mid) {
b[j] = a[i1];
i1++;
j++;
}
while (i2 <= to) {
b[j] = a[i2];
i2++;
j++;
}
for (j = ; j < n; j++) {
a[from + j] = (E) b[j];
}
}
}
SortTester code given:
import java.util.Arrays;
import java.util.Comparator;
import java.util.Random;
public class SortTester {
public static void main(String[] args) {
runSortTester();
}
public static void runSortTester() {
int LENGTH = 10000;
Integer[] a = createRandomArray(LENGTH);
Comparator<Integer> comp = new Comparator<Integer>() {
public int compare(Integer d1, Integer d2) {
return d1.compareTo(d2);
}
}
long startTime = System.currentTimeMillis();
MergeSorter.sort(a, comp);
long endTime = System.currentTimeMillis();
if (!isSorted(a, comp)) {
throw new RuntimeExcepetion("not sorted afterward: " + Arrays.toString(a));
}
System.out.printf("%10d elements => %6d ms ", LENGTH, endTime - startTime);
}
public static <E> boolean isSorted(E[] a, Comparator<? super E> comp) {
for (int i = 0; i < a.length - 1; i++) {
if (comp.compare(a[1], a[i+1]) > 0) {
System.out.println(a[i] + " > " + a[i+1]);
return false;
}
}
return true;
}
public static <E> void shuffle(E[] a) {
for (int i = 0; i < a.length; i++) {
int randomIndex = (int)(math.random() * a.length - i);
swap(a, i, i + randomIndex);
}
}
public static final <E> void swap(E[] a, int i, int j) {
if (i != j) {
E temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
public static Integer [] createRandomArray(int length) {
Integer [] a = new Integer[length];
Random rand = new Random(System.currentTimeMillis());
for ( int i = 0; i < a.length; i++) {
a[i] = rand.nextInt(1000000);
}
return a;
}
}
Explanation / Answer
import java.util.*;
public class MergeSorter{
public static <E> void sort(E[] a, Comparator<? super E> comp){
mergeSort(a, 0, a.length - 1, comp);
}
private static <E> void mergeSort(E[] a, int from, int to, Comparator<? super E> comp) {
if (from == to) {
return;
}
int mid = (from + to) / 2;
// Sort the first and the second half
mergeSort(a, from, mid, comp);
mergeSort(a, mid + 1, to, comp);
merge(a, from, mid, to, comp);
}
@SuppressWarnings("unchecked")
private static <E> void merge(E[] a, int from, int mid, int to, Comparator <? super E> comp) {
int n = to - from + 1;
Object[] b = new Object[n];
int i1 = from;
int i2 = mid + 1;
int j = 0;
while (i1 <= mid && i2 <= to) {
if (comp.compare(a[i1], a[i2]) < 0) {
b[j] = a[i1];
i1++;
} else {
b[j] = a[i2];
i2++;
}
j++;
}
while (i1 <= mid) {
b[j] = a[i1];
i1++;
j++;
}
while (i2 <= to) {
b[j] = a[i2];
i2++;
j++;
}
for (j = ; j < n; j++) {
a[from + j] = (E) b[j];
}
}
}
SortTester code given:
import java.util.Arrays;
import java.util.Comparator;
import java.util.Random;
public class SortTester {
public static void main(String[] args) {
runSortTester();
}
public static void runSortTester() {
int LENGTH = 10000;
Integer[] a = createRandomArray(LENGTH);
Comparator<Integer> comp = new Comparator<Integer>() {
public int compare(Integer d1, Integer d2) {
return d1.compareTo(d2);
}
}
long startTime = System.currentTimeMillis();
MergeSorter.sort(a, comp);
long endTime = System.currentTimeMillis();
if (!isSorted(a, comp)) {
throw new RuntimeExcepetion("not sorted afterward: " + Arrays.toString(a));
}
System.out.printf("%10d elements => %6d ms ", LENGTH, endTime - startTime);
}
public static <E> boolean isSorted(E[] a, Comparator<? super E> comp) {
for (int i = 0; i < a.length - 1; i++) {
if (comp.compare(a[1], a[i+1]) > 0) {
System.out.println(a[i] + " > " + a[i+1]);
return false;
}
}
return true;
}
public static <E> void shuffle(E[] a) {
for (int i = 0; i < a.length; i++) {
int randomIndex = (int)(math.random() * a.length - i);
swap(a, i, i + randomIndex);
}
}
public static final <E> void swap(E[] a, int i, int j) {
if (i != j) {
E temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
public static Integer [] createRandomArray(int length) {
Integer [] a = new Integer[length];
Random rand = new Random(System.currentTimeMillis());
for ( int i = 0; i < a.length; i++) {
a[i] = rand.nextInt(1000000);
}
return a;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.