CS 215 - Fundamentals of Programming IISpring 2010 - Project 325 pointsOut: February 15, 2010Due: February 24, 2010Reminder: Programming Projects (as opposed to Homework problems) are to be your own work. See syllabus for definitions of acceptable assistance from others.For this project, we will reuse the Rational class from Project 1, work with vectors, and consider several different sorting algorithms by writing a program that actually counts the number of lines executed by each one. The algorithms we will look at are: ● Selection Sort (Chapter 3-1, pages 116-119) ● Bubble Sort (Chapter 3, Written Exercise 3-17 on page 174) ● Insertion Sort (Chapter 4-4, pages 203-205) The assignment is to write template functions to sort vectors using the algorithms named above and named SelectionSort, BubbleSort, and InsertionSort, respectively. Each function will have exactly one vector reference parameter. In addition, you must write two template functions: ● ReadVector that reads data from an input stream until the stream fails as demonstrated in lecture. The function should clear the vector so that it is contains only the values from the input stream.● WriteVector that writes a vector to any output stream.. This function is like the one on page 196 (Chapter 4-3), but has an added ostream parameter that is the stream to write the output to (rather than always to the screen). The code for these template functions should be put in a separate header file named sort.h (put ReadVector and WriteVector first) that is included in your main program. Don't forget the compiler guards. The guards should be put around all of the code in the file. Write a (main) program in file testsort.cpp that takes three command line arguments, an input file name and two output file names. For example, the command line might look like:$ ./testsort inputfile.dat sortedfile.dat countfile.datThis program should read Rationals (from Project 1 - see note below) from the input file into a vector using ReadVector. The program should then call the functions implementing each of the sorting algorithms above. and write out the sorted vector into the first output file in the following format:Selection Sort<list of sorted Rationals separated by a newline><blank line>Bubble Sort<list of sorted Rationals separated by a newline><blank line>02/14/2010 Page 1 of 3Insertion Sort<list of sorted Rationals separated by a newline>Of course, if the algorithms are implemented correctly, the list of sorted Rationals should be the same for each algorithm. Note that each sorting algorithm should be run on the original list of Rationals, so you will need to keep a copy of the original vector and reinitialize the vector to be sorted for each algorithm. (Fortunately, unlike arrays, the vector type implements assignment, so you can just assign one vector to another and a copy is made.) Make sure each of your sorting algorithms works correctly at this point before continuing on to the rest of the project. (One way to determine if your sorting function is working correctly is to write out the vector being sorted to the screen using WriteVector (v,cout) after every pass of the sorting algorithm on a small file.To count the number of lines executed, instrument each function to increment appropriately a counter whenever a line of the algorithm is executed (i.e., do not count the instrumentation code) as demonstrated in lecture. In particular, a for-statement header counts as one line, as does a function call. You should use global counter variables for each algorithm declared at the top of sort.h; otherwise you would have to change each function to pass a counter variable by reference. Since we are exploring the behavior of O(n2) algorithms at relatively large n, these counters should be declared as unsigned integers, so that we can count to 232-1 (around 4 billion). The output from this program written to the second output file should be the size of the input (i.e., the number of integers read in), and the instruction counts for each of the algorithms. E.g., your output might be:Input size: 100Selection Sort instructions: 10000Bubble Sort instructions: 20000Insertion Sort instructions: 15000Note that these instruction counts are approximations. Your counts will be different for different input files. This output should be appended to the output file. Output files may be opened for appending by including a mode argument ios::app to the constructor or open call. E.g., ofstream out (argv[3], ios::app);To explore average, best, and worst-case behavior, input files containing 100, 500, 1000, 5000, and 10000 Rationals in random, sorted, and reverse sorted order will be provided on csserver in directory /home/hwang/cs215/project3. Run your program on each category of input file with output for each category going to the same output file as follows: data from the random files should go into file random.out, data from the sorted files should go into a second file sorted.out, and data from the reverse sorted files should go into a third file revsorted.out. Draw the following graphs showing the the size of input (x-axis) vs. the number of instructions (y-axis): ● One graph for each algorithm for the three categories of input. I.e., you should produce three graphs (containing data from a single algorithm, respectively) with 3 curves each (one for each category of input file). These graphs compare the effect of input order on a particular algorithm. ● One graph with the curves for the random input. I.e. a graph with 3 curves (one for each algorithm) of the data from the random input files. This graph compares the algorithms to each other. 02/14/2010 Page 2 of 3Answer the following questions based on your experimental results. Note that the first three questions ask you to compare each of the three curves (for random, sorted, and reverse sorted order) for each algorithm, while the last asks you to compare the algorithms with respect to each other. Briefly explain your answer. ● Which algorithm(s) have best-case running time when items are in sorted order? ● Which algorithm(s) have worst-case running time when items are in reverse sorted order? ● Which algorithm(s) have running time that is mostly unaffected by the input data order? ● Which algorithm appears to be the better algorithm? Note about the Rational class: You should fix any errors in your Rational class. In particular, it is very important that the
View Full Document
Unlocking...