Requirements for CS330 Fall 2001 Project 2

This series of experiments must be completed on your own and your own work should be handed in on the deadline. These are experiements. Different people should do different things and get different answers. You will take one (1) well known sort algorithm and code, test and time several versions of it.

Start by choosing any sorting algorithm for numbers in the first 5 chapters in the book, making it work, and testing it. Do this as soon as you can!

Finish with a report that compares several data structures and algorithms for sorting data.

2A. Strings.

Take your numeric sorting program and create a new version that sorts strings not numbers. PReserve your numeric sort for later! Test your string sort program on various (large and small) files of words.

Note. You can use other algorithms in the book (with some modifications) to turn any text file into a series of words. Or you use the following command in our UNIX to translate a string of non-letters ( -c "[A-Z}[a-z]") into a newline ("[\012*]"):

       tr -cs "[A-Z][a-z]" "[\012*]" <textfile >fileOfWords

2B. Compare arrays with vectors.

Take your original numeric sorting program and create two versions: one using arrays(2Ba), and one using vectors(2Bv). Compile, test and make both versions work on collections of n random numbers. Note your experiences as you develop the code. Time both of them for a range of n>1000. Record the times and draw rough graphs.

Hint. The book and CS202 covered generating random numbers.

2C. Compare vectors with lists.

Take your vector sort code (2Bv) and reprogram it to use lists(2Cl). Be ready to rethink the code while preserving the idea of the sort. Note your experiences as you develop the code. Then make the code compile and run correctly on random of sets of numbers. Then time the code. Record your results. Draw a rouch graph

Hint: subscripts must now become iterators.

2D. Generic and library sort functions.

Reprogram all your vector(2Bv) and list sorting(2C) programs to us the generic sorting algorithms for vectors and lists. Option: if you know about the C qsort function for arrays, time a version of 2Ba that uses it.

Hand in a report describing the differences between arrays, vectors and lists used for sorting data. Also compare the algorithm you used with the library algorithms. What do conclude? Include evidence for your conclusions: samples of code, graphs of times vs n, and explanations.

Grading: Each step (A, B, C, D) will be given the same weighting. The grade depends on writing obvious code, clear English, and clean diagrams. The code should include comments explaining all errors and clever ideas. Each class and function should be headed with a comment describing it's purpose. It should also give any simple invariants, pre-conditions, and post-conditions that might help convince the reader that the code works.