Please do it using Java Demonstrate a multithreading sorting application Write a
ID: 3590688 • Letter: P
Question
Please do it using Java
Demonstrate a multithreading sorting application
Write a multithreaded sorting program that works as follows: a list of integers 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 or the one provided. The two sublists are merged by a third thread – a merging thread – which merges the two sublists into a single sorted list.
Because global data are shared across all threads, perhaps the easiest way to set up the data is to create a global arrays. Each sorting thread will work on one half of this array. A second global array of the same size as the unsorted integer data structure will also be established. The merging thread will then merge the two sublists into this second data structure.
1. Generate 20 random integers
2. Store the integers to an array (original)
3. Save the integers to arrays (list_a and list_b)
4. Use a thread to sort list_a
5. Use a thread to sort list_b
6. Merge the lists from each thread into a single sorted final list(merged)
7. Display the original, sublists and the final sorted list
Global data:
private final static int SIZE = 20;
public static Integer[] original = new Integer[SIZE];
public static Integer[] list_a = new Integer[SIZE/2];
public static Integer[] list_b = new Integer[SIZE/2];
public static Integer[] mergedResult = new Integer[SIZE];
Sorting method you can use:
/** Sorts the first n objects in an array into ascending order.
@param a An array of Integer.
@param n An integer > 0. */
public void selectionSort(Integer[] a, int n)
{
for (int index = 0; index < n - 1; index++)
{
int indexOfNextSmallest = getIndexOfSmallest(a, index, n - 1);
swap(a, index, indexOfNextSmallest);
} // end for
} // end selectionSort
/** Finds the index of the smallest value in a portion of an array a.
* Precondition: a.length > last >= first >= 0.
* Returns the index of the smallest value among
* a[first], a[first + 1], . . . , a[last].
*
*/
private int getIndexOfSmallest(Integer[] a, int first, int last)
{
Integer min = a[first];
int indexOfMin = first;
for (int index = first + 1; index <= last; index++)
{
if (a[index].compareTo(min) < 0)
{
min = a[index];
indexOfMin = index;
} // end if
} // end for
return indexOfMin;
} // end getIndexOfSmallest
// Swaps the array entries a[i] and a[j].
private void swap(Integer[] a, int i, int j)
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
} // end swap
Merging Algorithm:
int a = 0;
int b = 0;
for(int i = 0; i < mergedResult.length; i++)
{
// add a if less than b
if(a < list_a.length && b < list_b.length && list_a[a] < list_b[b])
{
mergedResult[i] = list_a[a];
a++;
}
// add b if less than a
else if(b < list_b.length && a < list_a.length && list_b[b] < list_a[a])
{
mergedResult[i] = list_b[b];
b++;
}
else if(a < list_a.length && b < list_b.length) // add both if they are equal
{
mergedResult[i] = list_a[a];
i++;
mergedResult[i] = list_b[b];
a++;
b++;
}
else // add the rest of either list when comparing is over
{
if(a < list_a.length)
{
mergedResult[i] = list_a[a];
a++;
}
else if(b < list_b.length)
{
mergedResult[i] = list_b[b];
b++;
}
}
}
SAMPLE OUTPUT:
Original list
56 36 0 61 96 71 8 87 91 95 86 47 99 8 96 64 64 3 69 23
list_a
56 36 0 61 96 71 8 87 91 95
list_b
86 47 99 8 96 64 64 3 69 23
list_a thread started in main
Sorted list_a :
0 8 36 56 61 71 87 91 95 96
list_b thread started in main
Sorted list_b :
3 8 23 47 64 64 69 86 96 99
Merged result :
0 3 8 8 23 36 47 56 61 64 64 69 71 86 87 91 95 96 96 99
Explanation / Answer
SOLUTION
Solution contains three classes:
import java.util.Random;
private final static int SIZE = 20;
public static Integer[] original = new Integer[SIZE];
public static Integer[] list_a = new Integer[SIZE/2];
public static Integer[] list_b = new Integer[SIZE/2];
public static Integer[] mergedResult = new Integer[SIZE];
public class sortingThreaded{
public static void main(String[] args) throws InterruptedException {
int i, n;
// initialize original array with random numbers
Random ran = new Random();
for(i=0;i<20;i++)
{
original[i] = ran.nextInt(1000); // Generate integers in the range of 0 to 1000
}
// split original array into two arrays
for(i=0;i<10;i++)
{
list_a[i] = original[i];
list_b[i] = original[19-i];
}
// Display original list and the two sub lists.
System.out.println(“Original list”);
for(i=0;i<20;i++){
System.out.print(original[i] + “ ”);
}
System.out.println(“list_a”);
for(i=0;i<10;i++){
System.out.print(list_a[i] + “ ”);
}
System.out.println(“list_b”);
for(i=0;i<10;i++){
System.out.print(list_b[i] + “ ”);
}
sortArray SA1 = new sortArray (list_a);
sortArray SA2 = new sortArray (list_b);
SA1.start();
System.out.println(“list_a thread started in main”);
SA2.start();
System.out.println(“list_b thread started in main”);
SA1.join();
System.out.println(“Sorted list_a :”);
for(i=0;i<10;i++){
System.out.print(list_a[i] + “ ”);
}
SA2.join();
System.out.println(“Sorted list_b :”);
for(i=0;i<10;i++){
System.out.print(list_b[i] + “ ”);
}
mergeArray MA = new mergeArray();
MA.start();
MA.join();
System.out.println(“Merged result :”);
for(i=0;i<20;i++){
System.out.print(mergedResult [i] + “ ”);
}
}
}
public class sortArray extends Thread{
int[] tempArray;
sortArray(int[] arr) {
tempArray = arr;
}
public void run() {
selectionSort(tempArray,10);
}
/** Sorts the first n objects in an array into ascending order.
@param a An array of Integer.
@param n An integer > 0. */
public void selectionSort(Integer[] a, int n)
{
for (int index = 0; index < n - 1; index++)
{
int indexOfNextSmallest = getIndexOfSmallest(a, index, n - 1);
swap(a, index, indexOfNextSmallest);
} // end for
} // end selectionSort
/** Finds the index of the smallest value in a portion of an array a.
* Precondition: a.length > last >= first >= 0.
* Returns the index of the smallest value among
* a[first], a[first + 1], . . . , a[last].
*
*/
private int getIndexOfSmallest(Integer[] a, int first, int last)
{
Integer min = a[first];
int indexOfMin = first;
for (int index = first + 1; index <= last; index++)
{
if (a[index].compareTo(min) < 0)
{
min = a[index];
indexOfMin = index;
} // end if
} // end for
return indexOfMin;
} // end getIndexOfSmallest
// Swaps the array entries a[i] and a[j].
private void swap(Integer[] a, int i, int j)
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
} // end swap
}
public class mergeArray extends Thread {
int a = 0;
int b = 0;
public void run() {
merge();
}
public void merge() {
for(int i = 0; i < mergedResult.length; i++)
{
// add a if less than b
if(a < list_a.length && b < list_b.length && list_a[a] < list_b[b])
{
mergedResult[i] = list_a[a];
a++;
}
// add b if less than a
else if(b < list_b.length && a < list_a.length && list_b[b] < list_a[a])
{
mergedResult[i] = list_b[b];
b++;
}
else if(a < list_a.length && b < list_b.length) // add both if they are equal
{
mergedResult[i] = list_a[a];
i++;
mergedResult[i] = list_b[b];
a++;
b++;
}
else // add the rest of either list when comparing is over
{
if(a < list_a.length)
{
mergedResult[i] = list_a[a];
a++;
}
else if(b < list_b.length)
{
mergedResult[i] = list_b[b];
b++;
}
}
}
}
}