CSCE 2014 - Homework 5
Due Date - 04/19/2011 at 11:59 PM

1. Problem Statement:

The goal of this programming project is to implement and evaluate a bucket sorting function for floating point values.

Bucket sort is a "divide and conquer" sorting algorithm that works by dividing the N input values into R buckets based on data values. These R buckets are then sorted and combined to obtain N sorted values. Typically the buckets are chosen to divide the range of data values into R equal parts. For example, if the input values range between [0..99], we could put the data into 10 buckets with ranges [0..9], [10..19], [20..29], ... , [90..99]. This way, if the data is uniformly distributed each bucket will have 1/10th as much data as the original and will be much faster to sort.

Your task in the assignment is to create a bucket sorting function that takes in an array of N floating point values, and uses an array of R linked lists to store/sort the data values in each bucket. Your function should then return the sorted data in the output array.

2. Design:

There are several key questions that must be answered in order to implement bucket sort. First, how will we divide the data? To answer this, you need to prompt the user for the [min..max] range we expect in the input data, and the number of buckets R. From this, your must create a mapping function of the form "map(data_value)->bucket_number" that can be used to decide where each data value should be put.

The next question is how should the data in each bucket be stored and sorted? It is impossible to know in advance how many data values will end up in each bucket, so a dynamic data structure like an array of linked lists is ideal. You have two choices for sorting the data. You can either use linked list insertion sort as you store data in each linked list, or you can store data in unsorted linked lists, and remove and sort the data in each bucket separately using your favorite sorting algorithm. There are pros/cons to both approaches, so it is up to you to decide which to use.

You are welcome to use/modify any of the sample linked list code list2.h list2.cpp and sorting code sort.cpp. that is provided in the class src directory. You will see that the linked list code has been written to handle floats, and that there are functions for insertion/deletion of nodes at the head, and also functions for sorted insertion. You will also see that the sorting code is all based on integers and must be converted to floats for you to reuse. Also the "bucket_sort" algorithm in sort.cpp is very different from the function you are writing because integers are much easier to sort than floats.

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 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.

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. Try your program on 2-3 input documents, and save your testing output in text files for submission on the program due date.

5. Documentation:

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.

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 "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 within ONE DAY of the due date. This can be done during class, during lab, or using the department mailbox. Attach a copy of the Programming Project Evaluation Form to your report with your name and project number filled in.