CPSC 215 Lab 5: Sorting an Array Part II Due Thursday 10/28 The first part of the lab asks you to write a simple recursive method on the "cell" class in the manner of the several examples done in class. You are to define a method static cell doubles(cell L) that "doubles" all the elements in a list. That is, if L is 1 2 3 4 5, then doubles(L) should be 1 1 2 2 3 3 4 4 5 5. The second part of this lab asks you to complete the implementation of the qsort algorithm, which was described in class (also see text, page 385). It then asks you to compare the performance of qsort against the swapsort program you wrote in lab 1, and write a report, with charts, as you did in lab 1. All you have to do is to add the qsort methods and use "qsort" instead of "swapsort" in the tests. I've written a large part of the program for you (which you may modify if you find that you need to). Please read carefully the description of the "partition" method which I've supplied you with (see code section below). Essentially, you are to define two methods: 1. public void qsort(int begin, int end) qsort takes as arguments the first and last indicies of the partition (in the global array) to be sorted. Therefore, recursive calls to qsort will just be passed different partitions of the SAME array, instead of different arrays (this way we won't have to worry about merging different arrays). qsort should call findpivot, and the partition function I'm giving you below. 2. public int findpivot(int begin, int end) findpivot, given the boundaries of a partition, returns the INDEX of the pivot. For this version of sort, the pivot is the first element in the current partition that is less than the previous element in the partition. For example, the pivot in {2 4 7 3 8 1} is 3 because 3<7. If no element meets this criteria, then findpivot should return -1, and since -1 is not a valid array index, qsort will know from this that there is no pivot. The nice thing about this approach is that if there is no pivot, that means the current partition is already sorted! MAKE SURE findpivot RETURNS THE **INDEX** OF THE PIVOT ---- /* code */ import java.io.*; public class exp // a class for timing experiments { private int[] A; // Create Test Data File: public void make_data(int nums, String filename) { int i; RandomAccessFile outfile; try { // must encapsulate IO outfile = new RandomAccessFile(filename, "rw"); for (i=0;i pivot. It then returns the array index where the first partition ends (ie, index of last element of the first partition. This method is "destructive" in the sense that it changes the array (as opposed to building a new array) */ public int partition(int pivot, int begin, int end) { int counter, i, temp; counter = begin; for (i=begin;i<=end;i++) { if (A[i] <= pivot) { temp = A[counter]; A[counter] = A[i]; A[i] = temp; counter++; } } if (counter > begin) return counter-1; else return begin; } // you need to define the following for qsort: public void qsort(int begin, int end) public int findpivot(int begin, int end) // classic bubble sort algorithm: public void bubblesort() { int i, j, temp; for(i=0;i A[j+1]) { temp = A[j]; A[j] = A[j+1]; A[j+1] = temp; } } // end bubblesort public static void main(String[] args) { int i, j, max; long StartTime, ElapseTime, st2, et2; // not 'long' int nums = 1000; // **** change this to alter array size **** String file; // file name exp exp0; // the experiment object file = "nums" + nums; // file name is dependent on array size exp0 = new exp(); // create experiment object exp0.make_data(nums,file); // uncomment to make data file. exp0.read_data(nums,file); StartTime = System.currentTimeMillis(); exp0.bubblesort(); // should be replaced by swapsort // exp0.qsort(); // test either swapsort or bubblesort ElapseTime = System.currentTimeMillis() - StartTime; st2 = System.currentTimeMillis(); exp0.print(); // print the array et2 = System.currentTimeMillis() - st2; System.out.println("Approximate time for bubblesort = " + ElapseTime + " milliseconds."); System.out.println("Approximate time to print = " + et2 + " milliseconds."); try {System.in.read();} catch (IOException e) {} // needed for PC's } // end main } // end class exp (experiment) class cell // class for linked lists, for first part of lab { int head; cell tail; public cell(int h, cell t) { head = h; tail = t; } } /* For the lab writeup, run tests for swapsort and qsort on the same computer, but record and graph their data on *separate* charts (you'll find out why separate charts). Run tests on arrays of 1000, 3000, 5000, 7000, and 9000 randomly generated integers (you may run more if you want, of course). Answer the following questions: 1. What can you conclude from the shape of the graph of the running time of qsort. How's the graph different from that of swapsort (and bubblesort)? Is the difference between the algorithms constant? (i.e., is one always faster than the other by a constant amount?) Is the rate of slow-down constant? 2. Suppose you work for the IRS and you are asked to write a program that sorts the amounts of taxes paid by 200 million citizens (so they can find out who paid the least/most taxes, etc...) Using you graphs, estimate (seriously and quantitatively) how much time it will take swapsort to complete the task, and how much time it will take qsort to complete the task (assuming there's enough memory in your computer). Which algorithm would you recommend to the government? */