Download sort1.cpp , File10k.fil, Sorting Chart, and Quad Sorts into your account.
The first step in this assignment is to print out a copy of Sorting Chart for yourself. You will be filling in your results on this chart as you determine them. The first two columns of the chart are the expected number of moves and comparisons. This information can be found in the Quad Sorts handout-this is NOT to be done on the computer.
The second step is to fill in the missing code in sort1.cpp. Check the Pre & Post-Conditions of all the functions, especially MOVE, COMPARE and SWAP functions for writing the code of the sort algorithms. Run the program, making sure that the actual moves and comparisons matches (or comes close too depending on the situation) the expected moves and comparisons. Once you are sure the code is correctly implemented, record in the Sorting Chart the actual moves and comparisons and the amount of run-time needed to sort the data depending on the size of the array, and the precondition of the array. Run your test a couple of times to make sure you get the same time, or a time that occurs the most often. WARNING: USE THE SAME COMPUTER FOR YOUR TESTS! Computers run at different speeds and have different software configurations. To insure that your timing marks are accurate use the same computer for all of your trials!!!
In writing the code for the three sorting functions you will need to add a comment after the outer loop for each sorting function indicating what the loop invariant is for the outer loop.
After your sort analysis chart is completed, fill in which sort would be best for the given situation in your sort analysis chart.
Lastly type a double spaced paper describing how each sort works, it's good points and bad points, and how the data you acquired from your tests either supports or doesn't support your descriptions.
You will receive no partial credit if you do not turn in the report.
Turn in the following, stapled together, in the following order: