Implement quicksort using the Lomuto partitioning method with the median-of-three variant for selecting a pivot element (as described in class and in the textbook.) Use a constant to determine what minimum size (and above) array to apply the median-of-three technique, and determine a good value for this constant experimentally. Include a readme file that describes your testcases and how you determined a good mo3 constant.

You may use a Vector (C++) or an array to store your data.

C++ implementations are not required to use classes for this assignment.

INPUT

The input to your program will an unspecified number of entries. Each entry is a non-negative integer containing nine (zero padded) digits ( this means that the integer may have either leading or trailing zeros), one per line. Read your input from STDIN.

OUTPUT

Send the values, one per line, as they were input (all nine digits including leading zeroes, if any), sorted in ascending order, to STDOUT. The only output of your program is the numeric results. (i.e. don't output your name, assignment number, prompts etc.)

EXTRA CREDIT

Once your Lomuto partition method is coded, working, and tested thoroughly, add an alternate version of the partition method that use Hoare's partitioning scheme. (You will still be using the median of three technique.) Note that if you use Hoare's partition method, you may need different versions of your various (helper) functions. Thoroughly test the revised version of the program, and then re-test the original version of your program to make sure it still works. Your program should use the Lomuto partition method by default. Include a command line parameter ("-h") to select the Hoare partition method instead. Include analysis of this version of your algorithm (in the same readme file as above.) One half of the extra credit is for the implementation and one half is for the additional analysis. You will score no extra credit if both methods are not functioning properly.