Lab
QuickSort

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.

Continue to:  Unit 3  / Prev  / Next