Write a program that sorts an array of random numbers, using the shell sort and the quick sort. Both sorts should use the same data. Each sort should be executed twice. For the first sort, fill the array with random numbers between 1 and 999. For the second sort, fill the array with a nearly ordered list. Construct your nearly ordered list by reversing elements 19 and 20 in the sorted random-number list. For each sort, count the number of comparisons and moves necessary to order this list.

Run the program three times, once with an array of 100 items, once with an array of 500 items, and once with an array of 1000 items. For the first execution only (100 elements), print the unsorted data followed by the sort data in 10-by-10 matrixes (10 rows of 10 numbers each). For all runs print the number of comparisons and the number of moves required to order the data.

To make sure your statistics are as accurate as possible, you must analyze each loop limit condition test and each selection statement in your sort algorithms. The following notes should help with this analysis:

a. All loops require a count increment in their body.

b. Pretest loops (while and for) also require a count increment either before (recommended) or after the loop to count the last test.

c. Remember that C uses the shortcut rule for evaluating Boolean and/or expressions. The best way to count them is with a comma expression, as shown below. Use similar code for the selection statements.

while ((count++, a) && (count++, b))

Analyze the statistics you generated and write a short report (less than one page) concerning what you discovered about these two sorts. Include the data in Table, one for the random data and one for the nearly ordered data. Calculate the ratio to one decimal place.