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

1. 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?

2. 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?

3. 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 menu, the on-line reference manual for the Java compiler.