Activity 1, A Framework for Performance Testing.

Short Description:

Understand a framework for performance testing and describe the performance of selection sort.

Goals

When you finish this activity, you should have:

Formal Description

Please perform the following steps. The steps labeled TASK: require you to add content to a document. It will probably be easiest to do this in word, but you can use whatever you wish. You will be using excel in this activity.
  1. TASK: Start a document, record questions and reactions to this process. This will be your final document for submissions
    • Add the following to the top of your document
      • Your name
      • The names of any collaborators
      • The percent of the problem solved using AI. (This may change as you work your way through the activity)
  2. Log into prog1, or do whatever you do with vsc to get a working environment on prog1
    • make a directory for your work
    • Hint: mkdir activity1
    • You will be using the code from this activity in a future homework assignment.
  3. Download the following files
    • start.cpp
    • Makefile
    • Hint: wget https://mirkwood.cs.edinboro.edu/~bennett/class/cmsc3140/fall2026/homework/act1/start.cpp
    • Hint: wget https://mirkwood.cs.edinboro.edu/~bennett/class/cmsc3140/fall2026/homework/act1/Makefile
  4. Make sure that everything compiles, and run the program
    • Hint: make.
    • This program runs a sorting algorithm many times, it will take about 1/2 minute to run everything. Be patient.
    • Hint: ./start
    • TASK: Note any problems you encounter.
  5. Our next goal is to understand the pieces. Start at the top of the file start.cpp
    • Note that this uses a number of parts of the standard c++ library
      • algorithm for some simple functions like swap, but you will use another function in your homework.
      • random provides the current best practice random number generator
      • chrono provides the best practice timing utilities
      • vector provides a dynamic array, this one is worth learning if you don't know it.
    • TASK:Provide a brief statement in your document describing your current knowledge of these four standard library elements.
  6. The TimerT class
    • This is my creation, we really don't need a class, but this is easy to use.
    • It is somewhat equivalent to a stopwatch.
    • Start by looking at the private members
      • A time_point takes a clock and stores the current time value.
        • This is somewhat equivalent to a time_t with time
        • But is much better
        • The high_resolution_clock is the best reliable clock on the system.
        • So start and end will both hold time in some abstract unit.
      • A duration is a difference in time
        • So diff will hold the difference between two times.
    • The member functions support these operations.
      • Start() will start the stopwatch by recording the current time.
      • Stop() will stop the stopwatch and compute the time difference
      • Time() will return the difference in the requested unit.
    • DoExperiment uses this stopwatch
  7. The second unique element is random number generation
    • Look at the function GetRandomNumber.
    • This uses the modern random number package
    • a random_device is a source of randomness
      • static random_device rd;
      • This provides a seed to the RNG
      • This is usually based on hardware or other external events to provide a true source of randomness.
    • random::mt19937 is a random number generator.
      • static mt19937 gen(rd());
      • It is initialized with the random device declared above.
      • Making it static means that it will be created just once on the first entry to the function.
    • A uniform integer distribution is used to transform results to the range 0 to MAX_VALUE
      • static uniform_int_distribution <> distrib(0, MAX_VALUE);
      • Note, MAX_VALUE is a program declared constant.
      • We want this to be large enough so that there are not too many repeats in the data.
    • TASK: in your document describe the function of static when declaring a variable/class instance in a function. You might know this, or this might be a great place to either write some code and experiment or even work through it with an AI.
  8. Vectors
    • TASK: in your document, describe the action of the following lines of code
      1. vector<int> data;
      2. data.push_back(GetRandomNumber());
      3. data.size();
      4. data[j]
  9. DoExperiment
    • This function:
      • Generates an array of random integers
      • Starts the stopwatch
      • Sorts the data
      • Stops the stopwatch
      • Checks to see if the data was sorted correctly.
      • Reports the time, comparisons and swaps used in the sort.
    • TASK: look at Check, describe at a high level the three possible failures that this function will detect. Can you think of any other contditions that should be tested?
  10. Note, this program produces output as a CSV (comma separated value) file.
    • TASK: Run the program, and redirect the output to a file. Insert a screenshot of this into your document.
    • Hint: ./start > datafile.txt
    • Move datafile.txt to somewhere you can run Microsoft Excel (or another spreadsheet that supports pivot tables.)
    • wget, sftp, winscp, or something in vsc.
  11. TASK: Open the data file in a spreadsheet that supports pivot tables.
    • (file-> open), set type to all files select the proper directory and open datafile.txt.
    • When you do this, excel will present you with an Text Import Wizard.
      • Select Delimited if it is not selected and choose next
      • Import step 1
      • Mark comma , and select finish.
      • Import Step 2.
    • Create a pivot table
      • Select all of the data in the new worksheet
        • Move to cell A1
        • Press CRTL-SHIFT-DOWN, CRTL-SHIFT-RIGHT, or highlight all of the data.
          • Select All Data
          • Your entire data set should be selected (or grey)
          • I have hidden some rows in the picture.
      • Select Insert -> PivotTable to create a pivot table.
      • Creating a pivot table
      • Then select ok on the popup window.
    • Populate the pivot table
      • Drag Sort down into the Rows area (literally click and hold on Sort and drag it into the box.)
      • Drag Size into the Rows are under sort
      • rows in a pivot table
      • Drag Time into Σ Values.
      • You don't want the sum, so on drop down the menu select Value field settings and select Average in the popup box.
      • change sum to average
      • selecting average
      • You can do the same for Compares and moves.
      • TASK: insert a copy of your pivot table (screen shot or active) in your document.
    • Create a pivot chart
      • If you need to select the PivotTable Analyze tab
      • Pivot Table Table
      • And select PivotChart
      • Select an appropriate chart (Line is good)
      • Change the title (Big + sign, select title, change it), they should be time and array size.
      • An example pivot chart
      • TASK: Insert a copy of your pivot chart in your document.
      • TASK: Discuss the data as presented in the pivot table and pivot chart for the time needed for selection sort.
    • TASK: Create a pivot chart for both Compares and Moves
      • You will probably need a separate chart for each, as they have different scales.
      • Include each of these graphs in your document.
      • Discuss each of these graphs.
    • TASK: using the code in SelectionSort explain why the time and comparison graphs are O(n2), while the moves graph appears to be O(n).

Notes

My datafile for discussion.

Required Files

A single document demonstrating that you have completed the above tasks.

Submission

Submit the assignment to the D2L folder Activity 1 by the due date.