Lab 08

Random Number Generation

Simple random numbers can be created with the rand() function. This is part of the cstdlib library.Because we are comparing multiple sorting algorithms, it makes sense to test them on the same data. So, we want the randomly generated array used in one sorting method to be the same randomly generated array used in another. This can be done by ‘seeding’ the random number generator, so that using this seed, the generator will create the same random numbers in the same order. Seeding the random number function can be done with the srand() function. You only want to seed once. That is to say you don’t want to seed each time you create a new random number, but just once before the number creation process starts.

Another, more complicated method is also given below, which is supposedly immune to the possible pattern generation of the simple mod method. This method divides the randomly generated number by the maximum possible value for randomly generated numbers, creating a number from 0 to 1. This is then multiplied by the number of integers between the min and max number and added to the minimum number. The code is slightly more complicated than the description I give, but thats the short of it.

Random Numbers: Example code

Simple Modulus Method

  
    #include <cstdlib>
    srand(123);   //seed the random number generator
    int highest = 100;
    int lowest = 0;
    int randomNumber = lowest + rand()%((highest-lowest)+1);
  

More Complicated Method

  
    #include <cstdlib>
    srand(123);   //seed the random number generator
    int highest = 100;
    int lowest = 0;
    int range = (highest-lowest)+1;
    int randomNumber = lowest+int(range*(rand()/(RAND_MAX+1.0)));
  

Probably either one of these will work for our purposes, people just seem to lean towards using the second one.

Timing

Timing code execution can be done in C++ using the ctime library.

Example code

  
    #include <sys/time.h>
    
    // Used to get the time of day for timing comparisons.
    unsigned long getTime()
    {
      timeval tv;
      gettimeofday (&tv, NULL);
      return tv.tv_sec * 1000000ul + tv.tv_usec;
    }
  

Here is the function being used:

  
    unsigned long start;
    unsigned long finish;
    
    start= getTime();

    // do something

    finish = getTime();
    unsigned long totalTime = finish - start;
  

In the getTime function, we utilize the gettimeofday function passing in a timeval struct that is modified to contain the current time. Inside this struct we have two values: tv_sec which holds the number of seconds passed since January 1, 1970, and tv_usec, the number of microseconds. We return the summation of the number of seconds passed, converted to microseconds, and the number of microseconds passed.

Check out the man page for gettimeofday for more information.

Timing Considerations

Other applications running, and other issues might affect the performance of these algorithms. This is why it would probably be in your best interest to keep the conditions of your computer as static as possible when running these tests.

You can make sure it compiles on the EECS computers (and runs), but do the actual tests on your computer, where there will most likely be more controllable conditions.

Remember, only include the sorting in your timing tests. Don’t include the array creation in your timing.

Other Notes

The file SelectionSort.cpp has the typedef statement used in all the other sorting algorithms, so in your main file, include it before any of the others.

Use the strcomp() == 0 method if you want to leave your input arguments as c strings.

The Selection sort file includes two functions indexOfLargest and swap that need to be declared before the selectionSort function.

The Merge sort has a maximum integer size that you can modify to be the maximum value needed for these experiments.

Make sure you delete the array at the end of the program.

Automation of Testing

A shell script could be used to automatically call these tests and append their outputs to a file.

Shell scripts usually have the file extension ‘.sh’.

A shell script starts with a line indicating the interpreter program that will execute the file. In our case, we would like the default shell to run the commands so our first line would be:

  #!/bin/sh

Then we can add lines to the file, each one will be executed as if they were typed in from the command prompt.

  ./lab06 250 random selection >> select_out.txt
  ./lab06 500 random selection >> select_out.txt

Note the use of the ‘>>’ character. This redirects the output of the command to a file. The double arrow indicates that the output will be appended to the file, instead of overwriting the contents of the output file.

So you could make a line like this for everyone of your needed commands and have the output be added to one or more files. (You would probably want that output to include some information about the current test being executed, so you don’t get the times confused.)

To make this shell script executable, navigate to the directory holding it in the terminal and add executable rights to the file:

  chmod +x lab06.sh

then you can run it from the command line like a normal executable program.

Shell scripts can be considerably more complex (loops, if/then, etc), but this should be sufficient for the application.