Java

In this program we will look at three variations of quicksort. We wil compare them on ten randomly generated lists of 1000 items. In addition, we will look at the algorithms' performance on both a sorted and reversc sorted (sorted highest to lowest) version of each list. 2. Random Pivot Point. The partition algorithm randomly pick an index value of the the array it is looking at. The array element at the location is the partition valuc. 3. Median-of-three Partitioning. Quicksort tends to work best when the partition value is one that is in the middle range of the values to be sorted. Middle-of-three partitioning tries to be a quick way to do this. How it work:s is that it looks at the elements at the first position, the last position, and the middle element of the array. Whichever of those three is the median (not the smallest, not the largest, but the middle value) is chosen as the partition value for the partition We will look at the behavior of three different versions of quicksort on randomly generated lists of size 1000. The three versions of quicksort are described below Randomly generate integers in the range 0-99 for your random numbers. You may choose your own random number generation technique. You must document the source of your random number generation in the code. Here is what your code should do: 1. Do this 10 times a. Generate a random list of 1000 items. b. Make a sorted version of the list. Use whatever sort you want to do this. You do not need to demonstrate, annotate, etc. this sort. c. Make a reverse-sorted (i.e. high to low) version of the list. Modify whatever sort you want to do this. You do not need to demonstrate, annotate, etc. this sort. d. Have each version of quicksort sort each of the three lists. e. Give the original list, the sorted list, and the number of comparisons done by each version of the algorithm. 2. At the end: a. For cach quicksort version and cach list type (random, pre-sorted, reverse sorted) give the average of the number of comparisons. Quicksort Versions Here are the three versions of quicksort to use. 1. Basic Quicksort