CS 112 B1 - Spring 2003: Homework 5

Due Thursday, Apr 10 at 11:59 P.M.

Please keep in mind the policy on collaboration, as described on the syllabus.

Your code will be graded for style as well as correctness and should conform to the following style guidelines. Style will be worth 10 points total.

PROBLEM 1:

You are given a collection of template functions for inputting, outputting, and sorting an array of some class. You are also given a main() function that uses these templates on the integers. The current sort that's implemented is Bubble Sort. Implement function templates SelectionSortArray and QuickSortArray, in sort.h, analogously to bubble sort (in particular, use the swap function when needed, instead of swapping directly inside your sort using temporary variables--it'll make sense in the next problem). Test them out using main. A sample input file is included, but you should test on other inputs, as well. See comments inside sort.h to understand the proper input/output formats. For quicksort, use (for now, you'll change that later) the element in the lowest position as the pivot. The Ryba and Kruse textbook does a fairly good job explaining quicksort, you may use it (including pieces of code from the textbook, if you want, but note that the textbook uses a totally different way of organizing the code, so you'll have to modify it).

• sort.h
• intsort.cpp
• intinput

PROBLEM 2:

To get practice using templates, you will now use the same functions for sorting polynomials. We are providing you with the polynomial class, but it needs slight modifications: it needs friend operators >> and << for input and output, a friend function swap, and a member operator >. We provide >> and swap, and you will have to write the rest. When writing operator> (which is defined as follows: p1>p2 if degree of p1 is greater than degree of p2 or, if the degrees are equal, if the highest coefficient of p1 is greater than that of p2; if those are also equal, the answer is determined by the next terms, and so on), also add code to count the number of comparisons, analgously to how the number of swaps is counted (note the declaration and use of swapCount in polynomial.h and its definition initialization and increments in polynomial.cpp). If you do this correctly, you will be able to compile and link it together with polysort.cpp. You can now test the sorting of polynomials, and see how many comparisons and swaps your sort takes. A sample input and output files are included, but you should test on other inputs, as well. See comments inside polynomial.cpp to understand the proper input/output formats.

• polynomial.h
• polynomial.cpp
• polysort.cpp
• polyinput
• polyoutput

PROBLEM 3:

Create a new function, RandomizedQuickSortArray, which is just like your QuickSortArray but uses a random pivot (it may be easiest to swap it with the lowest element first). To get a random number between 0 and x-1, use rand() % x to take a random number returned by rand() modulo x (the function prototype for rand() is in cstdlib). Now your bad input from the previous problem is no longer bad.