Assignment 07

Due: Friday, October 18, 2019 at 12:01 p.m., 100 points

For this assignment you will submit at least 3 files, but possibly more.

For this assignment, you will use:

    • all the stuff you've learned up to now

    • arrays

    • the random number generator

    • sorts (sort of sorts, .... , well you know, sorting algorithms)

    • process timing

Bach ground here

Background: Sometimes, Dr. Nick has troubles sorting out things .... stuff he's sorta responsible for. Thus, he now wants you to write some sorting algorithms and then tell him which is the best to use. Of course, this has no application in the medical field, but neither does Dr. Nick. ... at least none that you want to be involved in.

Specifications: There are two "parts" to this program:

    1. Seed the random number generator with 42 srand(42);. Declare an array of 15 integers, populate it with random values between and including 5 and 100, i.e. from the interval [5,100]. Then output that array on one line with a space between each value. Then apply your bubble sort routine to it and print it out again afterward. Repeat this but using your Nick's sorting routine (described below).

    2. Now have your program create two arrays of 15,000 ints and populate both of these two arrays with the same list of randomly chosen numbers (integers) whose value falls between 105 and 15,000, inclusive. It is to sort one of these arrays using "bubble sort" and time how long it takes, and then the other array using "Nick's" sort, and once again time it. (By the way, if you can do this with just one array with the same numbers, then do so and we'll be proud of you.) Your program is to do this assigning and sorting 10 times and output: i) the minimum sorting time; ii) the maximum sorting time; and iii) the average sorting time for each sorting algorithm. Thus, you will be comparing bubble sort to Nick's sort for "speed".

      1. NOTE: DO NOT print any part of this second part's arrays!

Details: There are several details to discuss.

  • You are to template both of your sorting algorithms, and any "helper" functions they use. If you are a smart programmer, you will put both these algorithms in their own header files so that you can easily carry them to other projects. Way cool!

  • The sort routine that you are to use is described as follows (we'll call it Nick's Sort -- a name that is unique, interesting, intriguing, fashionable, descriptive, and, above all, imaginative). The filled portion of the array (henceforth known as 'the array') will be partitioned into two sub-arrays: the sorted sub-array, and the unsorted sub-array. At first, the unsorted part will be full and the sorted part will be empty. For example, suppose we have

    • a[0] a[1] a[2] a[3] a[4] a[5] a[6] 5 9 -1 4 7 0 3

      • as our array to begin with. The sorted part is nonexistent and the unsorted is the entire array. The first step of Nick's Sort is to examine the first value in the unsorted part and move it into its proper position in the sorted part. As you can see, nothing has really changed; it's just that the sorted part now is distinguished from the unsorted part. Thus we have

      • a[0] a[1] a[2] a[3] a[4] a[5] a[6] 5 9 -1 4 7 0 3

      • Next, examine the new first element of the unsorted part (a[1] = 9) and move it into its proper position in the sorted part. Since it is bigger than 5, it stays in its relative position. Thus, we have

      • a[0] a[1] a[2] a[3] a[4] a[5] a[6] 5 9 -1 4 7 0 3

      • Next, examine the new first element of the unsorted part (a[2] = -1) and move it into its proper position in the sorted part. Its movement would look like

      • a[0] a[1] a[2] a[3] a[4] a[5] a[6] 5 9 -1 4 7 0 3 a[0] a[2] a[1] a[3] a[4] a[5] a[6] 5 -1 9 4 7 0 3 a[2] a[0] a[1] a[3] a[4] a[5] a[6] -1 5 9 4 7 0 3

      • And so on. This looks simple here, but when programming this routine, you may find it more difficult. Don't underestimate the difficulty of this problem. Note there is only one array in this process of sorting; you don't use a second array!

    • Bubble sort will be described to you in class, if it hasn't already been.

    • Timing is affected using the following commands:

      • start = clock(); sort_my_array(); finish = clock(); run_time = (static_cast<float>(finish) - start)/CLOCKS_PER_SEC;

    • Of course, you must declare start and finish as long int and and run_time as float. CLOCKS_PER_SEC is a system constant. No system files need be included to do this stuff. So, run_time will give you the time it takes to do that sort. You must decide what to do with that value and how to couch this in a loop.

    • Make your program so that it is divided logically into functions. Further, make your sorting algorithm functions so that they are completely portable -- so that they don't rely on any particular declarations of constants and so that they have (together) their own header and .cpp files.

    • Template appropriate code.

When you submit: Notice there is no user input for this assignment. So, just submit.

As always, if you have a question about this or any other assignment, be sure to ask your instructor or the LEAD help.