CPSC 220
Fall 2007
HW 4: Quicksort

1. Read the section on Quicksort in the text (p. 351). Now consider the array a of integers below:

   5  9  2  3  5  4  7  3  1  8  6  5  
   

   Assuming you have called quickSort(a, 0, 11), using the quickSort method as written on page 352, show the following:
   • A trace of the first call to findPartition. Show the values of partitionelement, left, right, data[left] and data[right] as you proceed through the while loop and its two inner loops.

   • The partitioned array when findPartition returns.

   • The value of indexofpartition when findPartition returns.

   • The parameters that are passed to the first top-level recursive call to quickSort.

   • The parameters that are passed to the second top-level recursive call to quickSort.

2. Write a Java program to implement Quicksort. You may refer to the code in L&C (it's all there) or any of your own old code, but you may not use significant portions of anyone else's code. Your program should have the following behaviors:
   • If your program is called MySort, its usage should be java MySort infile outfile, where:
     • infile contains the integer data to be sorted. You should assume that the first line of infile contains an integer that indicates how many data items are in the file. The data then appears one item per line with an end-of-line character between the last data item and the EOF character. For example, if the EOF character were visible a valid data file might look like this:

       4 
       2 
       9 
       1 
       3456
       EOF
       

     • The program writes the sorted integer data to outfile, one item per line.

     If the format of the data file is invalid or the program cannot open either the input or output file, it should terminate and print an appropriate message to the standard output.

   • If your program runs successfully it should print just two things to the standard output:
     • The number of items sorted.
     • The time required for the sort in milliseconds. (Remember that method System.currentTimeMillis() gives the current system time in milliseconds). IMPORTANT: This time must not include any input or output.

   Your program should be self-contained, that is, it should not rely on any other classes that are not in the standard Java library. E-mail your source code to me before class.