JAVA, If an array has a lot of repeated values, it is possible to optimize quicksort to run significantly faster. The key idea is to partition the array into three regions instead of 2; thus well call this quicksort3way. The left-most region has all the values smaller than the partition value, the right-most region has all the values greater than the partition value, and the middle has all the entries larger than the partition value.

Im requiring you to use half-open ranges rather than the (IMO) off-by-one prone code that Sedgewick and Wayne use.

Well use p = a[lo] as the partition value. Here is what the array looks like during the partitioning phase (where P represents the partition value):

lo	i	J	k	hi
< p	= p	not checked	> p

Note that unlike the usual quicksort partitioning, where we leave a[lo] in place until the end, here were letting that value move through the array as needed.

We need to keep track of 3 indices, which Ive called i, j, and k. At any point in the partitioning process, we have the following ranges defined:

[ lo , i ) has all the values < P

[ i, j )has all the values = P

[ j, k) has all the values that have not been checked

[k , hi ) has all the values > P.

When the partitioning is done, the array will look like this:

lo	i	j,k	hi
< p	= p	> p

The only difference from the above is that the [ j , k) range is empty.

Ive provided the basic shell of the sort on the following page, and it will also be provided as a template in zyLabs. You should incorporate this code into the same StdSort.java file that you wrote for assignment 6. All you need to do is to fill in a few details (that is, replace all occurrences of ---- with real code).

Your quickSort3Way() method should be in a class called StdSort.

These questions should get you started (you dont need to answer them here, theyre just hints for getting the code written):

1. Initially, you want [ lo , i ), and [k , hi) to be empty, [ i . j) to have a single element (why?), while [ j ,k ) is the entire array except for the first element. This should tell you how to initialize i , j and k.

2.You want to quit when [ j, k) (the range of unchecked values) is empty. This should give you the criteria for exiting the loop. (You should find in (3) that with each loop iteration either j increases by one or k decreases by 1.)

3. Each time through the loop, youll be checking a[j] against the partition value p.

a. If a[j] < p, what range do we need to add a[j] to? What is the easiest way to get it there? What indices (i, j, or k), if any, need to be adjusted?

b.What if a[j] == p, or a[j] > p?

c. (Hint: Two of these 3 cases involve calling StdArray.swap(), and the other just needs to have one of the indices incremented.)

4. What are the two half-open ranges we still need to sort?

HERE IS MY PROGRAM , REMOVE " ----- " and enter your code !

public class StdSort {

public static > void quickSort3Way(T[] a, int lo, int hi) {

if ((hi - lo) <= 1)

return;

T p = a[lo];

int i = -----; // see hint 1

int j = -----;

int k = -----;

while (-----) { // see hint 2

int c = a[j].compareTo(p);

if (c < 0)

-----; // see hint 3

else if (c > 0)

-----;

else

-----;

}

quickSort3Way(a,-----,-----); // see hint 4

quickSort3Way(a,-----,-----);

}

public static > void quickSort3Way(T[] a) {

StdRandom.shuffle(a);

quickSort3Way(a, 0, a.length);

}

}