Quick Sort program DrJava.....Need help!!!! I was disappointed to see that the Q

Question

Quick Sort program DrJava.....Need help!!!!

I was disappointed to see that the QuickSort program that I wrote was significantly slower than the built-in Arrays.sort algorithm available in the java.util library. In this assignment, Im counting on you to help to find an algorithm that is as fast as Arrays.sort.

Using the QuickSort class that we developed in class as a starting point, you should modify the class code as needed to implement and test three possible variations to improve average run-time of the algorithm.

First, one mathematician has suggested that using the median value of the first, last, and middle elements as a pivot will improve performance. you should implement and TEST this approach. I already provided a method in the QuickSort class to return the index of the median of the three array elements passed in as parameters.

Second, another mathematician suggested that you should select the pivot as a RANDOM element in the array. This can be implemented and tested by creating a Random object as a class variable and choosing a random element of each sub-array rather than the middle element.

Third, another suggestion is that performance can be improved if we switch to insertion sort for small sub-arrays. This last variation should recursively use QuickSort while the sub-arrays have a length of greater than 15, but will switch to InsertionSort when the array length falls below that threshold. Ive included my InsertionSort program for you to use with your program.

Finally, give me a recommendation, supported by your test results. Your testing should use an approach similar to the one I used in TestSorts2.java, determine the average sort time for the modified QuickSorts and compare the three new approaches to the original. My test program only makes 100 test runs, but your testing should use 10,000 iterations.

_________________________________________________________________

Quicksort Code:

___________________________________________________________

Here is the Test Program:

Explanation / Answer

/* QuickSort: This sort can be done in different ways .......... I have taken Pivot as middle element. you can take any element as Pivot. */ class SortQuick { public static void main(String[]args) { int i; int array[] = {12,9,4,99,1}; System.out.println("Elements Before Sort: "); for(i = 0; i

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.