Tasks: 1. Modify the MergeSorter class to convert it into a parallelized MergeSo
ID: 3571401 • Letter: T
Question
Tasks:
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.*; // for Random
public class SortMergeSort {
private static final Random RAND = new Random(42); // random number generator
public static void main(String[] args) throws Throwable {
int LENGTH = 1000; // ini length for the array to sort
int RUNS = 16; // how many times to grow by 2?
for (int j = 1; j <= RUNS; j++) {
int[] p = createRandomArray(LENGTH);
// run the alg & time how long it takes
long startTime1 = System.currentTimeMillis();
parallelMergeSort(p);
long endTime1 = System.currentTimeMillis();
if (!isSorted(p)) {
throw new RuntimeException("not sorted afterward: " + Arrays.toString(p));
}
System.out.printf("%10d elements => %6d ms ", LENGTH, endTime1 - startTime1);
LENGTH *= 2; // double size of array for next time
}
}
public static void parallelMergeSort(int[] p) {
// int cores = Runtime.getRuntime().availableProcessors();
int cores = 8;
parallelMergeSort(p, cores);
}
public static void parallelMergeSort(int[] p, int threadCount) {
if (threadCount <= 1) {
mergeSort(p);
} else if (p.length >= 2) {
// split array in half
int[] left = Arrays.copyOfRange(p, 0, p.length / 2);
int[] right = Arrays.copyOfRange(p, p.length / 2, p.length);
// sort the halves
// mergeSort(left);
// mergeSort(right);
Thread lThread = new Thread(new Sorter(left, threadCount / 2));
Thread rThread = new Thread(new Sorter(right, threadCount /2));
lThread.start();
rThread.start();
try {
lThread.join();
rThread.join();
} catch (InterruptedException ie) {}
// together merge it back
merge(left, right, a);
}
}
// Arranges the elements for the given array into sorted order
// use the "merge sort" algorithm, which splits the array in half,
// recursively sorts the halves, then merges the sorted halves.
// It is O(N log N) for every input.
public static void mergeSort(int[] p) {
if (p.length >= 2) {
// split array in half
int[] left = Arrays.copyOfRange(p, 0, p.length / 2);
int[] right = Arrays.copyOfRange(p, p.length / 2, p.length);
// sort the halves
mergeSort(left);
mergeSort(right);
// merge them back together
merge(left, right, p);
}
}
// Combines the contents , left/right arrays into output array p.
//let Assumes that left.length + right.length == p.length.
public static void merge(int[] left, int[] right, int[] p) {
int j1 = 0;
int j2 = 0;
for (int j = 0; j < p.length; j++) {
if (j2 >= right.length || (j1 < left.length && left[j1] < right[j2])) {
p[j] = left[j1];
j1++;
} else {
p[j] = right[j2];
j2++;
}
}
}
// Swaps the values for 2 given indexes in the given array.
public static final void swap(int[] p, intj, inti) {
if (j != i) {
int temp = a[j];
p[j] = a[i];
p[i] = temp;
}
}
// Randomly arranges the elements for the given array.
public static void shuffle(int[] p) {
for (int j = 0; j < p.length; j++) {
// move element j to a random index in [j .. length-1]
int randomIndex = (int) (Math.random() * p.length - j);
swap(p, j, j + randomIndex);
}
}
// Returns value of true if the given array is in sorted ascending order.
public static boolean isSorted(int[] p) {
for (int j = 0; j < p.length - 1; j++) {
if (p[j] > p[j + 1]) {
return false;
}
}
return true;
}
//build an array for the given length and fills it with random
// non-negative integers and returns it.
public static int[] createRandomArray(int length) {
int[] p = new int[length];
for (int j = 0; j < p.length; j++) {
p[j] = RAND.nextInt(1000000);
// p[j] = RAND.nextInt(40);
}
return p;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.