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, in-order 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.

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).

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:

Testing will consist of a comparison between the quicksort without multithreading and quicksort with multithreading. You can use the following code to time your run, once (or more than once and calculate an average) in standard form, before you add the multithreading modification and the time after modification.

long time1 = System.nanoTime();

// here is the place where you place the code

// or the call to code to be timed.

long elapsed = System.nanoTime() - time1;

The resulting time will be in nanoseconds so divide by 1,000,000 to get milliseconds or by 1,000,000,000 to get seconds.

Since the elements to be sorted are random and the program checks itself for correct sorting, no further testing is necessary. So do not display the 10000 values.

Lab Exercise 05.2

Binary-sort tree

Problem Description:

The problem to be solved is the building of a binary tree in RAM using methods that recursively call themselves to construct the tree. If the values are stored correctly, they can be retrieved in numeric order by merely traversing the tree and checking the values for numeric order. It is not the worlds best sort algorithm but it has two points in its favor: (a) it can be used to insert values that occur leisurely but that can be retrieved in numeric order at a moments notice, and (b) it will give you some practice using recursion.

The program will have 3 classes; (1) the class containing the main method, (2) a class named treeSort and (3) a class named node. Objects of the node class will be used as nodes in the sort-tree while an object of the treeSort class will receive long integer numeric values and create nodes to contain them in the tree. You can think of the tree as a two-dimensional linked-list and like any linked list, it exists in RAM but is built dynamically. The main method will generate the random values and send them to the sortTree by calling a method.

SortTree will then have at least four methods:

public boolean insert(long value)

This method will be called by main and will insert the value into the tree. If the value to be inserted is a duplicate of one already in the tree, the insertion will be terminated without any node being created and the value true will be returned to the caller. Otherwise insert will return the value false.

public long [] retrieve( )

This method will create an array of type long and will fill it with the values in sorted order from the tree. Since the insert method can count the number of values currently in the tree, creating the array should be able to use this value to size the array exactly.

public boolean isPresent(long value)

This method will search the tree for the argument value and if found, will return true If the value is not found, false will be returned.

public int getCount( )

This method will return the number of values currently in the tree. It will count only the actual values, not the duplicates for which insert returned false.

Lab Exercise 05.3

Hierarchical data tree search

Problem Description:

The problem to be solved is the building of tree in RAM and then provide the capability to search the tree and retrieve values. The data to be converted into tree form is a text file containing hierarchically-structured information. Here is an example, formatted to show the hierarchy:

Bob Dylan

USA

Columbia

10.90

1985

Bonnie Tyler

UK

CBS Records

9.90

1988

Dolly Parton

USA

RCA

9.90

1982

The CATALOG contains multiple CDs and each CD contains 6 values, TITLE, ARTIST, COUNTRY, COMPANY, PRICE and YEAR. Each entity (CATALOG, CD, TITLE etc.) is formed by enclosing a value or other entity between two tags, each formed by placing the angle-brackets (< and >) around the name of the entity. The leading tag contains the name and the ending tag contains the name, preceded by a forward-slash ( / ). Thus the TITLE entity is a text string that looks like this:

The resulting tree will contain nodes containing the entities. A tree containing the information in the sample above could resemble the following diagram:

The directed lines connecting the diagram elements represent reference-variable values or pointers. The lowest-level nodes (TITLE, ARTIST etc.) will contain class-level String variables containing the values (Empire Burlesque, and Bob Dylan etc.) The rest of the tree exists merely to record the structure of the data.

There are two files associated with this exercise, one contains a more extensive catalog of CDs and the other contains a list of domestic garden plants. You can demonstrate your program on either of these files.

Your program should have a class, containing the main method and a separate class, named XML_Data which contains the tree-building and the tree-searching methods. A 3^rd class will define the nodes. As usual in these cases, the tree will exist in RAM only, not in the code. The code will have the reference to the root node and the remainder of the structure will exist in RAM only.

When the program starts, the main will instantiate the XML_Data class and it will immediately read the indicated text file and build the tree. When that task has been completed, main will communicate with the user to perform searches and retrievals of information.

Each leaf-node (lowest-level node containing a value) has an associated path. For example, in the plant catalog file, the path CATALOG.PLANT[3].PRICE will find the element $9.90 . The subscript [3] is needed because merely specifying PLANT in the path would not allow the user to distinguish between the 36 sub-elements of CATALOG.

There should be a method to search the data file and return the number of sub-elements at the location described by the path. For example, the path CATALOG will return the number 36 because there are 36 sub-elements named PLANT at that point. The path CATALOG.PLANT[12] will return the number 6 because there are 6 sub-elements of PLANT at that point. The path CATALOG.PLANT[2].COMMON will return the number 0 because COMMON at that location has no sub-elements.

There should be a second method to search the data file, find the designated element and return a String containing it and its sub-elements. For example, the path CATALOG.PLANT[3] will return a String containing the following:

Cowslip

Caltha palustris

4

Mostly Shady

$9.90

030699

The path CATALOG.PLANT[3].ZONE will return a String containing the following:

4

Your requests should be case-insensitive.