Lab 3: Nested Loops and Sorting

Due: Wednesday, Sept. 17, 2014 @ 11:59 p.m.

Description:
In this lab, you will write a simple C program that will use nested loops. Your program will use a random number generator to initialize an array. It will then call a function to sort the array. After returning from the function, the program will print out the sorted array.
Background Preparation:
Read the manual page for the rand() function. Continue your work learning about editing with vi/vim, general Unix commands and transferring files to and from Mason and/or Zeus.

Generating Random Numbers:
In order to use rand to generate a random number, you first must "seed" the random number generator. In your program, you will create a #define macro named RNG_SEED with the last four digits of your G number as the token for the macro. You may then use the following C statement within your code:

srand(RNG_SEED); // Reminder: You will need to #include <stdlib.h>

This statement should only be called one time, before any calls to the rand() function are made. To actually generate a random number, you then simply call the function rand(), which will return a large integer.

Example:

int my_random_num = 0; // declare your own var to hold random number
srand(RNG_SEED); // "Seed" random number gen. with system time
my_random_num = rand(); // my_random_num now contains a large integer

Your program will actually generate floating point values in the range of [0..1000]. To do this, you will need to divide the value returned from the rand() function by (RAND_MAX/1000.0):

double my_random_val = rand()/(RAND_MAX/1000.0);

Insertion Sort:
The program will sort the array using the Insertion Sort algorithm. It works as follows:

          InsertionSort(A)   /* sort A[1..n] in place */
		for j <-- 2 to n do
			key <-- A[j]   /* insert A[j] into sorted sublist A[1..j-1]
			i <-- j-1
			while ((i > 0) and (A[i] > key)) do
				A[i+1] <-- A[i]
				i <-- i-1
			A[i+1] <-- key

Note that the above algorithm uses the value 1 to index the first element in the array. Remember that C does this differently.

Specifications:
Your program will start by printing an informational message, stating your name, lab section, and what the program will do.

It will declare in main() a local array numArray, that holds 25 values of type double.

It will seed the random number generator as described above.

The program will then perform the following five times using a loop:

Call a function that uses numArray and its size as parameters, and generates an array of random floating point values of type double. These values are stored in numArray. The prototype for this function is:

void InitializeArray(double *numArray, const int arrayLength);

After returning from the function described in 1, the list of 25 numbers is printed to the screen, up to four decimal places.
A separate function is then called to sort the values in the array. It has the following requirements:

It has two input parameters: numArray, and the length of numArray
It uses the insertion sort algorithm given above to sort numArray in ascending order
For every iteration of the while loop in the given algorithm, a counter is incremented (this counter is initialized to 0 at the start of the function)
After the array is sorted, the function returns the value of the counter. The sorted values are contained in numArray
The prototype for this function is:

int SortArray(double *numArray, const int arrayLength);

After returning from the function described in 3, the sorted list of 25 numbers is printed to the screen, up to four decimal places
The value (X) returned from the function described in 3 is also printed using a statement such as "The number of swaps for this list was: <X>"

Your program will not use any global variables.

Any constants used in the program (5, 25, your G# and the range of the random values (1000.0)) will be given as #define macros (this doesn't include the value used in the for loop of the sorting algorithm or the 4 used for the number of decimal places printed)

You will compile your program with a Makefile using the gcc compiler. You may edit a Makefile taken from Lab 1 or Lab 2, but your Makefile must not contain any references to any programs and files other than those necessary for this lab.

Testing:
Test your program to ensure that the data generated is being sorted correctly, and that each of the five iterations actually creates distinct lists (i.e. you are using your random seed correctly). Make sure that the program output is neat and readable. Also make sure that your code is neat, with consistent indenting and good comments.

Submission:

Log in to mason or zeus and copy your program there. Start a typescript session. Type "uname -a" to show that you are on mason or zeus. Use the cat command to list both your source file and Makefile. Compile your program using the make command. Run your program to show that it executes correctly. Then exit the typescript session by typing cntl-d.

Verify that your script file was created correctly by using the more (or less) command (your choice) to see the contents of the file. Information on these commands can be obtained by using the manual pages ("man more" or "man less"). Once you are sure the file is correct, copy the script file, source file and Makefile back to your local computer and submit all three of them to Blackboard as Lab 3.