CSCE 2014 - Homework 4
Due Date - 04/10/2014 at 11:59 PM

1. Problem Statement:

The purpose of this programming assignment is to learn more about sorting algorithms. Your task is to create two sorting functions "corn_sort" and "hilow_sort" and use these functions to sort an array of 100 random integer values between [0..999].

The corn sort algorithm is a variation on the traditional bubble sort algorithm. In each pass over the unsorted array, you look at two adjacent values and swap them if they are out of order. With bubble sort, these passes over the data are always going from left-to-right. With corn sort you do one pass from left-to-right followed by another pass from right-to-left and this is repeated until there are no exchanges. Thus with corn sort, we will bubble the largest value to the far right on the first pass, and the smallest value to the far left on the second pass. Hence, we should be able to sort random numbers in fewer passes over the data.

The hilow sort algorithm is a variation on the traditional selection sort algorithm. With selection sort, each pass over the unsorted data selects the smallest remaining data value, and this is stored to the right of the sorted data values. With the hilow sort, each pass over the unsorted data will select the largest and the smallest remaining data values, and these two values will be stored in appropriate locations in the sorted array -- the smallest value to right of previous small values, and the largest value to left of previous large value. Hence with hilow sort, we will move two values into their correct locations with each pass over the data.

2. Design:

Students are encouraged to use the sample sorting code in labs 10 and 11 as a framework for creating random data values, and reading and writing ascii sorted and unsorted data files. You should use the same parameters for "corn_sort" and "hilow_sort" as the "bubble_sort" and "selection_sort" functions.

3. Implementation:

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 always 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. Also, remember to keep backup versions of your code, so you always have a version to fall back on if you accidentally delete your code or your changes do not work out.

4. Testing:

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. You are required to include your testing results in your project report to demonstrate that your program works correctly. To do this use the "script" command to save all program input/output in a "typescript" file, and cut and paste from this ascii file into your program documentation.

5. Documentation:

When you have completed your C++ program, use the "Programming Report Template" on the class website to document your programming project. This report has separate sections to describe the problem statement, your design decisions, your implementation process, and your testing results. Each of these sections should be 1-2 paragraphs long, so your completed report will be 2-3 pages long once you have included your testing output.

6. Project Submission:

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 "Upload" your documentation (a single docx file), and your C++ program (a single ascii text file).

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:

You will receive partial credit for all programs that compile even if they do not meet all program requirements, so handing projects in on time is highly recommended.