In this lab you will write a program that uses C. A. R. Hoare's recursive quicksort algorithm.

- Copy the shell program
`quiktest.java`

. Run it on an apvector of 20 randomly generated integers and quicksort them. To get a rough idea of the algorithm's running time, modify the program to declare a variable`qcount`

that keeps track of how many times during program execution an array element is compared to the pivot, splitVal, in calls to`Split(..)`

. Use proper labeling to display the array before and after sorting along with qcount, its running time measure. What did you get for`qcount`

? - Fill in the code for the selection and insertion sort functions
and uncomment the two portions of blocked out code that run the
sorting functions on ascending-ordered and descending-ordered
arrays. Compare the running times of the three sorts on
arrays of 1000 elements where the data is randomly or already
ordered ascending or descending. Calculate
`qcount`

, the quicksort's running time measure defined above, along with`scount`

and`icount`

, the number of comparisons between array elements in the selection and insertion sort algorithms. Be sure to comment out the print calls when you change the size of the arrays. Try each of the three sorts for each of the three pre-orderings.For what kinds of data is quicksort really "quicker"? Why?

When is the insertion sort "quicker" Why?

- Comment out the selection and insertion sort portions of the
program. The quicksort algorithm you've been using selects the
first element as the pivot element, splitval. Explore how the choice
of quicksort's pivot element affects the running time.
Modify the split(..) function to pivot about the middle element.
Modify the split(..) function to swap the first element with an
element of the subarray chosen randomly before proceeding with
the splitting. Record the running time measure, qcount, for each
pivot strategy on each pre-ordering of 1000 element arrays.
Which pivot value gives the best running time performance over all?

Bonus! Use `qsort(..)`

, the quicksort function supplied by
the Java compiler. To find out how to access it, type
`qsort`

, then place the cursor on the word and press

. This accesses the