The goal of this programming assignment is to gain experience with sorting algorithms. So far, we have only spoken about methods to sort an array of integers. These algorithms can be easily modified to sort an array of floats or an array of strings. Things get more complicated when we want to sort by multiple data fields. For example, if you have data records with [int1, int2, string] we might want to sort all records based on one of these data fields, or we may want to sort by two or more fields. The order in which these sorts are applied will have a huge impact on the result. Sorting numerically by int1 then alphabetically by string will give very different results compared to sorting by string followed by int1.
Your task in this assignment is to write a program that initializes an array of [int1, int2, string] values, and sorts this data according to user commands. You will be given an ascii file data.txt where each line in the file contains a unique int1, int2, string record (representing word frequency data similar to hw2). Your program should prompt the user for which field to sort by, and use one of the classic sorting algorithms (excluding bubble sort) to sort the data. This sorting process should continue so the user can sort by multiple fields until the user hits 'q' to quit. The sorted data should then be written to an output file "data.out" for examination. When testing your code make sure you get different results when you reverse the order in which you sort multiple fields.
Note: Some of the sorting methods we have discussed in class and lab are "order preserving" and others are not. Hence you may have cases where the second sort will "mess up" the ordering of records from the first sort. Don't worry about this since you are not using this code in a commercial product.
There are a number of design decisions you need to make in order to complete this assignment. First, how will you store the data? Keep in mind that you want to be able to quickly access/modify the int1, int2, string values. Second, how will you adapt the sorting algorithms to work with this data? You need to make sure that the three data fields always 'stay together' when you sort the data. Finally, you need to work out what user interface you create. To keep things simple, a menu-based approach may be best.
You can implement this program using either a bottom-up approach or a top-down approach. If you go for a bottom-up approach, start by creating basic methods and classes, and test theses methods using a simple main program that calls each method. When this is working, you can create the main program that uses these methods to solve the problem above.
If you go for a top-down approach, start by creating your main program that reads user input, and calls empty methods to pretend to solve the problem. Then add in the code for these methods one at a time. This way, you will get an idea of how the whole program will work before you dive into the details of implementing each method and class.
Regardless of which technique you choose to use, you should develop your code incrementally adding code, compiling, debugging, a little bit at a time. This way, you always have a program that "does something" even if it is not complete.
When you think you are about 1/2 way through the program, upload a copy of your source code and your program output at that point. Be sure to hand in something that compiles even if it does not do much when it runs.
Test your program to check that it operates correctly for all of the requirements listed above. Also check for the error handling capabilities of the code. Try your program on 2-3 input documents, and save your testing output in text files for submission on the program due date.
When you have completed your C++ program, write a short report (less than one page long) describing what the objectives were, what you did, and the status of the program. Does it work properly for all test cases? Are there any known problems? Save this report in a separate text file to be submitted electronically.
In this class, we will be using electronic project submission to make sure that all students hand their programming projects and labs on time, and to perform automatic analysis of all programs that are submitted. When you have completed the tasks above go to the class web site to "submit" your documentation, C++ program, and testing files.
The dates on your electronic submission will be used to verify that you met the due date above. All late projects will receive reduced credit (50% off if less than 24 hours late, no credit if more than 24 hours late), so hand in your best effort on the due date.
You should also PRINT a copy of these files and hand them into your teaching assistant in your next lab. Include a title page which has your name and uaid, and attach your hand written design notes from above.