Lab Exercise 05.1

Merge-Sort

Problem Description:

The problem to be solved is the building of a merge- sort program using recursion. Advantages of this approach to the problem are:

The sorting process is very time-efficient

The algorithm is straightforward; all the work is done in the merge portion of the program.

The use of recursion in this algorithm makes the logic quite simple. The array to be sorted is split in half, each half is sorted and the sorted halves are merged. The function that divides the array in half calls itself twice, passing each half of the array in turn. After the second half has been returned, sorted, the two halves are merged and the result is the entire array, sorted.

This subdividing continues until the elements to be sorted number 1 or 2. They are then put into order and the process of returning and merging begins.

EMBED Visio.Drawing.11

EMBED Visio.Drawing.11

The important point to understand is that when the sort routine Returns to caller, it is returning, except for the first call (from main), to a previous instantiation of itself. You may visualize the calling of the sort function as the automatic creation of a separate copy of the sort function which performs its action, separating the array, calling yet another copy of itself for each half and merging the result, and then returning.

Your exercise will involve creating a main program to create the array, call the sort function and display the sorted results. The array will contain 10000 elements and will be filled with double values from a random number generator. Random doubles may be generated by the repeated calling of the random function from the Java Math library, as follows:

// fill an existing array with random doubles

for (int i = 0; i < 10000; ++i)

{

ArrayToBeSorted[i] = Math.random( );

}

This will fill an array named with 10000 random doubles, values between 0.0 and 0.99999999 (1.0 wont be used).

Testing:

There is no good reason to display 10,000 numbers since no human would be able to see if an out-of-order situation exists. So the final part of the main program will contain a loop that will compare each element to the one immediately after it in the sorted array and display a message if they are out of order.

Testing will consist of running the program. Since the elements are random and it checks itself for correct sorting, no further testing is necessary.

======================================================================

Lab Exercise 05.2

Multithreaded quick-sort

Problem Description:

The problem to be solved is the building of a quick- sort program using recursion. Advantages of this approach to the problem are:

The sorting process is very time-efficient

It can operate in-place, that is, in the original array.

The use of recursion in this algorithm makes the logic quite simple. The array to be sorted is split in two sections, each section is sorted and the sorted sections are put together. The function that divides the array does so by picking one element in the array and using it as a so-called pivot. The array is separated into two portions such that every element in one portion is less than the pivot-element and every element in the other portion is greater than or equal to the pivot-element. The algorithm then calls itself on each portion; this process continues until the portion to be sorted contains 1 or 2 elements. After the second portion has been returned, sorted, the two portions are already in-place and the result is the entire array, sorted.

The special wrinkle to this lab is that you will use multithreading in an attempt to speed-up the algorithm. If your CPU is hyper-threaded and/or you have a multi-core processor, speedup should be detectable.

The key to doing this is to assign the first array-split to two threads. The thing that will slow everything to a crawl is if you assign every split to two more threads. A large sort would then have hundreds or even thousands of threads and the processing will be dominated by the time necessary to create, destroy, start, stop etc. the threads. Using two threads with two processors should give you a speed increase of 20% or more.

EMBED Visio.Drawing.11

The important point to understand is that when the sort routine Returns to caller, it is returning, except for the first call (from main), to a previous instantiation of itself. You may visualize the calling of the sort function as the automatic creation of a separate copy of the sort function which performs its action, separating the array, calling yet another copy of itself for each half and merging the result, and then returning.

Your exercise will involve creating a main program to create the array, call the sort function and display the sorted results. The array will contain 10000 elements and will be filled with double values from a random number generator. Random doubles may be generated by the repeated calling of the random function from the Java Math library, as follows:

// fill an existing array with random doubles

for (int i = 0; i < 10000; ++i)

{

ArrayToBeSorted[i] = Math.random( );

}

This will fill an array named with 10000 random doubles, values between 0.0 and 0.99999999 (1.0 wont be used).

Testing:

There is no good reason to display 10,000 numbers since no human would be able to see if an out-of-order situation exists. So the final part of the main program will contain a loop that will compare each element to the one immediately after it in the sorted array and display a message if they are out of order.

Testing will consist of running the program. Since the elements are random and it checks itself for correct sorting, no further testing is necessary.