Sorting II

Introduction

The labs in CSC172 follow a pair programming paradigm. Every student is encouraged (but not strictly required) to have a lab partner. Labs will typically have an even number of components. The two partners in a pair programming environment take turns at the keyboard. This paradigm facilitates code improvement through collaborative efforts, and exercises the programmers cognitive ability to understand and discuss concepts fundamental to computer programming. The use of pair programming is optional in CSC172. It is not a requirement. You can learn more about the pair programming paradigm, its history, methods, practical benefits, philosophical underpinnings, and scientific validation at http://en.wikipedia.org/wiki/Pair_programming.

Every student must hand in his own work, but every student must list the name of the lab partner (if any) on all labs.

This lab has six parts. You and your partner(s) should switch off typing each part, as explained by your lab TA. As one person types the lab, the other should be watching over the code and offering suggestions. Each part should be in addition to the previous parts, so do not erase any previous work when you switch.

The textbook should present examples of the code necessary to complete this lab. However, collaboration is allowed. You and your lab partner may discuss the lab with other pairs in the lab. It is acceptable to write code on the white board for the benefit of other lab pairs, but you are not allowed to electronically copy and/or transfer files between groups.

Quicksort++ (4 parts)

This is Exercise 7.26 of Weiss. Use the quicksort code from the book (figs 7.2, 7.13 - 7.15, attached as an appendix). You are to remove one of the recursive calls by
  1. rewriting the code so that the second recursive call is unconditionally the last line in quicksort. Do that by reversing the if/else and returning after the call to insertion sort.
  2. performing a test so that the smaller subarray is processed by the first recursive call and the larger subarray is processed by the second recursive call.
  3. removing the tail recursion by writing a while loop and altering left or right as necessary.
  4. Demonstrate your quicksort works on several examples that span the range of possible issues.

Experiments (2 parts)

This is Exercise 7.49 of Weiss. Use your quicksort to experiment with combinations of pivot-finding and cut-offs. Namely, try pivoting on first, middle, random, median of 3, and median of 5 elements. Try cutting off the quicksort and switching to insertion sort at values from 0 to 20. Split up the work evenly. Present your findings elegantly.

Hand In

Hand in the source code from this lab at the appropriate location on the blackboard system at my.rochester.edu. You should hand in a single compressed/archived (i.e. zipped) file that contains the following.) You will need to include the images of your plotted results.
  1. A README that includes your contact information, your partner's name, a brief explanation of the lab (A one paragraph synopsis. Include information identifying what class and lab number your files represent.).
  2. Several JAVA source code files representing the work accomplished for this lab. All source code files should contain author and partner identification in the comments at the top of the file.
  3. A plain text file named OUTPUT that includes author information at the beginning and shows the compile and run steps of your code. The best way to generate this file is to cut and paste from the command line. Also present your experimental results here.

      Grading

      172/grading.html

      Each section (1-6) accou'nts for 15% of the lab grade (total 90%) (README file counts for 10%)

      Appendix -- Code

      This page is maintained by Deer Boy

      Last update: 10/13/12