Question

The following submission rules apply:

·    For those questions requiring programs, the solutions must be implemented using JavaScript or Java.

o Appropriate self-documenting comments in the source code are mandatory, consistent with good programming practices.

o Solutions must be provided in plain text so that formatting is not lost.

·    All answers must be provided in this document.

·    Sources must be given accurate and complete citations sufficient for the instructor to find and confirm them.

Design a version of QuickSort that uses a threshold. Do empirical testing to determine a good threshold value.

Answer 1

Quicksort is one of the fastest sorting algorithms for sorting data.

The implementation of a simple sequential Quicksort algorithm follows that we choose for our needs is: 1.Select a pivot element.

2. Iterate through the sorting area, place all numbers smaller then the pivot element to left, and place all other numbers to right. Done by swapping elements.

3. The pivot element is now in its sorted position and continue with the divide-and conquer strategy, applying the same algorithm on the part of left and right of pivot.

By using a threshold, sequential sorting alogorithms saves the computational cost.

With parallel algorithm, we have to remember that the cost of creating, monitoring and managing of the parallel tasks is added to the total computational cost. Assume that the average case of quicksort with computational time O(nlogn).

When using parallel computing, the computational cost consists of these values:

1. pick the pivot – O(1)

2. move the elements to the left and right side of pivot - O(n)

3. create new tasks to sort the left and right part of the pivot - O(1)

For each leaf node of the tree, perform a sequential quicksort, the size of the leaf node depends upon the threshold T.

Using Threshold quicksort can be implemented in efficient way as below:

1. void thresholdquicksort(int * var, int p, int q)
2. {
3.    int r;
4.    while(p < q)
5.    {
6.       r = partition(var, p, r);
7.       if(r - l < q - r) //recurse into the smaller half
8.       {
9.          quicksort(var, p, r - 1);
10.          l = r + 1;
11.       } else
12.       {
13.          quicksort(var, r + 1, q);
14.          q = r - 1;
15.       }
16.    }
17. }