Project 3

Objective: 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

Submit the .java file(s) in assignment area. Your submission should have documentation and must include output that has demonstrated the programs completely.

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