Description
Getting motivated
Welcome to your first CS302 lab which consists of two parts that both focus on sorting. In Part A, you implement a data structure for storing multi-column data consisting of a firstname, a lastname, and a phone number (all made up, but you knew that), read unspecified amounts of such data from stdin and apply the std::sort algorithm before you print the result to stdout. In Part B, you implement a variant of the quicksort algorithm described in class that in its basic form replaces std::sort and in a more advanced version allows partitioning of the data followed by sorting within a given range. The latter extension will be based on the quickselect algorithm also described in class. You will also add command line option handling for selecting a particular method.
Read the assignment a couple of times. Look at the output examples below. Run the solution code to become familiar with its behavior. Ask questions on Piazza so the whole class can benefit from your confusion. Chances are you are not alone. Do this for every lab assignment.
Lab submission and due date
Your friendly TAs will tell you how to submit your work to Canvas. Do not email your code to the instructor or the TAs as they cannot upload the code to Canvas for you.
Part A is due 11:59pm Sunday Sep 1, 2019. Part B is due 11:59pm Wednesday Sep 11, 2019. You only submit one file each time. The incremental development outlined below is merely intended to make solving the problem more manageable. All submitted code must compile and execute without seg faulting to be graded.
Aim to submit Part A early, so you get a head start on the command line option handling. That way, you get more time to work on the quicksort and quickselect code.
Getting started and what you need to do
To help you get started, run the Hydra script /home/cs302/labs/lab1/copy to obtain the following files: QsortA.cpp and QsortB.cpp (skeleton code), sqsort (Hydra solution executable), list1.txt-list3.txt (data files), and a makefile. Your job is to write the missing source code which must behave as described next.
Develop your code in stages as described next. QsortA.cpp must contain ALL code needed to first satisfy Part A. You then copy and update this file to satisfy Part B. You will work with multi-file assignments in later labs.
-
Part A Vers. 1: Use your favorite editor to modify QsortA.cpp as follows. Add code for the input and output operators associated with the data class which has three private data members: firstname, lastname, and phonenumber. The input operator simply reads each of these every time it is called. The output operator prints a data object using the format: lastname firstname phonenumber. See examples below. Part of the assignment is for you to figure out how to maintain a fixed width of the name field so that all phonenumbers are left justified to the same column position. Finally, implement printlist() as a template function that takes generic iterator arguments and steps thru the data while printing to stdout. Do whatever else is needed to make the program compile such as adding missing header files. Then test and make sure it reads and writes data from the list files as required.
unix> QsortA < list.txt
-
Part A Vers. 2: Add an overloaded operator< to the data class, so you can impose an order on such objects. Test that it works by applying the std::sort algorithm before writing the list content to stdout. Objects that store the same lastname should use the firstnames to determine which is less than the other. Objects that also store the same firstnames should use the phone numbers to determine which is less than the other. See examples below.
This completes Part A. Submit QsortA.cpp on Canvas after you have cleaned the code up and added a few comments.
-
Part B Vers. 1: Add command line argument handling. When completed, any one of the following three ways of calling QsortB will be valid:
unix> QsortB -stl < list.txt unix> QsortB -rpivot < list.txt unix> QsortB -rpivot k0 k1 < list.txt
The first version executes the code from Part A. The second version uses your own implementation of quicksort to sort the data. The third version partitions the input data as described below before applying quicksort to sort the data in the range given by integers k0 and k1. Without checking, we will assume that k0 is less than k1. Do check if k0 is less than 0, in which case it should silently be changed to 0. Likewise, check if k1 is greater than or equal to the number of elements in the data array, say N, and if so, silently change it to N-1.
-
Part B Vers. 2: Implement quicksort as follows. Copy the partition_median2() and quicksort_median2() functions from the sorting4 handout. Replace the median-of-three pivot with a randomly chosen index in the left-to-right range and use it to partition the data. This new version forces you to think about how the median-of-three partitioning code works as unlike it, you must now explicitly check and prevent going out-bounds during the search for data pairs to swap. To make you think even more about the algorithm, merge all the functionality into the quicksort() function. That is, do not have an external function that carries out the partitioning. Keep it all in one function that gets called from the main() function. Test and compare the output with what you obtained using std::sort. The two output should be identical since they use the same comparison operator.
-
Part B Vers. 3: Copy the quickselect() function from the sorting4 handout. Embed the random pivot based partition code that you added to quicksort() in Part B Vers. 2. The function will take four arguments, i.e., quickselect(A, left, k, right) where A is a data array, left and right designate the first and the last indices to consider (the range), and k the element that needs to be selected (found and put in its proper place). Make whatever other modifications are needed to get the code to compile. Test the program to make sure you the selection is correct.
Use quickselect(A, 0, k0, N-1) to put the k0-th element in its proper location and partition the data in A accordingly. That is, ensure that all data stored to the left of A[k0] is lexicographically less than or equal to it. All data stored to the right of A[k0] must likewise be greater than or equal to it.
Then use quickselect(A, k0, k1, N-1) to put the k1-th element in its proper location and partition the data in A accordingly. Note that data indexed below k0 is ignored at this point. When this works, use the quicksort() function to sort the data in the k0 thru k1 index range.
This completes Part B. Submit QsortB.cpp on Canvas after you have cleaned the code up and added a few comments.
Example runs based on list1.txt
unix> cat list1.txt CANDACE WITT 250-939-5404 THEODORE PERKINS 723-668-3397 THAD HULL 708-807-6757 STEPHAN SALAZAR 415-413-5058 ISRAEL WILKINS 938-701-1455 BRUCE PERRY 540-916-2956 VALENTIN RIVERS 726-204-2377 WILFRED JOHNSTON 582-126-8861 JORDAN WILKINS 938-701-1455 LEVI SPENCE 985-365-7415 KAYLA NGUYEN 484-322-1527 unix> ./QsortA < list1.txt [same as below] unix> ./QsortB -stl < list1.txt [same as below] unix> ./QsortB -rpivot < list1.txt HULL THAD 708-807-6757 0 JOHNSTON WILFRED 582-126-8861 1 NGUYEN KAYLA 484-322-1527 2 PERKINS THEODORE 723-668-3397 3 PERRY BRUCE 540-916-2956 4 RIVERS VALENTIN 726-204-2377 5 SALAZAR STEPHAN 415-413-5058 6 SPENCE LEVI 985-365-7415 7 WILKINS ISRAEL 938-701-1455 8 WILKINS JORDAN 938-701-1455 9 WITT CANDACE 250-939-5404 10 unix> ./QsortB -rpivot 3 6 < list1.txt JOHNSTON WILFRED 582-126-8861 0 HULL THAD 708-807-6757 1 NGUYEN KAYLA 484-322-1527 2 PERKINS THEODORE 723-668-3397 3 ** PERRY BRUCE 540-916-2956 4 ** RIVERS VALENTIN 726-204-2377 5 ** SALAZAR STEPHAN 415-413-5058 6 ** SPENCE LEVI 985-365-7415 7 WILKINS ISRAEL 938-701-1455 8 WITT CANDACE 250-939-5404 9 WILKINS JORDAN 938-701-1455 10
The line numbers added to right for the last output are for illustrational purposes and not produced by the program. They help you see that the data in lines 3-6 is sorted (by design), that the data lines 0-1 and 9-10 is not, and that the data in lines 2 and 7-8 is (by chance).
Grading rubric
Note: Output format of your program must MATCH that of the solution executable. Use the diff command to compare.
Quicksort Part A (50)
25: Class data: operator>> and operator<< 15: Class data: operator< 10: Function printlist()
Quicksort Part B (150)
20: Command line argument handling: 30: Quicksort: random pivot, integrated partitioning while-loop safety guard(s) 20: Quickselect: random pivot, integrated partitioning, while-loop safety guard(s) 15: Output matches solution code output for list1.txt, list2.txt and list3.txt 15: Goldielocks comments: not too many, not too few -- just the right amount
