During this activity, students will be able to:
This activity must be developed in the pre-assigned teams of two.
Translate the following sorting algorithms from the pseudocode presented in chapter 6 of [STEPHENS] to C++ code:
Write a report with the results of running each algorithm as explained below.
The sorting operations must be performed on vectors of integer values (std::vector<int>
). These integer values must be between 0 and 999, inclusive.
After calling each sorting algorithm you must verify that the vector has been correctly sorted. This must be done using the std::is_sorted
function.
The algorithms should be tested with vectors of the following sizes:
The execution of each algorithm using a vector of each size must be timed under three initial conditions:
Make sure to run all your code on the same computer (or AWS Cloud9 environment) so that timing measurements are meaningful.
IMPORTANT: Some algorithms, especially those with a complexity \(\textrm{O}(N^2)\), may be extremely slow for large values of \(N\). If the program takes more than three minutes to run for a certain combination of algorithm/size/initial-vector-condition it is okay to stop it and simply report that case as “too slow”.
In addition to the six requested algorithms, you must run and time the predefined standard library function std::sort
using vectors of the same sizes and with the same initial conditions as those already described above.
The following code initializes all items in the values
vector with random integers between 0
and max_value - 1
, inclusive.
#include <cstdlib> void fill_random(std::vector<int>& values, int max_value) { std::srand(0); for (int i = 0; i < values.size(); ++i) { values.at(i) = std::rand() % max_value; } }
The following code initializes all items in the values
vector with integers that go progressively upward from 0
to some value less than max_value
.
void fill_incremental(std::vector<int>& values, int max_value) { double section = max_value / static_cast<double>(values.size()); double current = 0.0; for (int i = 0; i < values.size(); ++i) { values.at(i) = static_cast<int>(current); current += section; } }
The following code initializes all items in the values
vector with integers that go progressively from some value less than max_value
down to 0
.
void fill_decremental(std::vector<int>& values, int max_value) { double section = max_value / static_cast<double>(values.size()); double current = 0.0; for (int i = values.size() - 1; i >= 0; --i) { values.at(i) = static_cast<int>(current); current += section; } }
The following snippet allows us to time the execution of a portion of our program. What needs to be measured should be substituted in place of the corresponding comment. At the end, the total_time
variable contains a floating point value with the number of seconds it took the code to run.
#include <chrono> . . . auto start = std::chrono::high_resolution_clock::now(); // Place here the code to time auto stop = std::chrono::high_resolution_clock::now(); auto duration = std::chrono::duration_cast<std::chrono::microseconds>( stop - start); double total_time = duration.count() / 1000000.0;
Using the word processor of your choice, write a report containing the following:
Cover Page: Includes the title of the lab, as well as the team number, IDs (matrículas), names and emails of the authors of the report.
Introduction: Establishes the purpose and methodology of this lab. It must have an extension of at least 100 words.
Computational Resources: Includes the information regarding the hardware and software used to develop the lab.
If you are using AWS Cloud9 with Ubuntu, you can determine the available hardware and software by running the following commands from the terminal:
CPU model:
grep "model name" /proc/cpuinfo
Number of CPU cores:
grep "cpu cores" /proc/cpuinfo
Total RAM (the number in row Mem:
, column total
):
free -mh
Total secondary storage memory (the number in column Size
):
df -h | egrep '/$|Size'
Operating system version:
lsb_release -ds
C++ compiler version:
g++ --version
Results: For each algorithm (including the std::sort
function), indicate its complexity and include a table filled with the respective execution times. Something like this:
Algorithm Name: (for example: Bubblesort)
Complexity: (for example: \(O(N^2)\))
Number of Items | Initial Condition | ||
---|---|---|---|
Unsorted | Ascending Order |
Descending Order |
|
100 | |||
1,000 | |||
10,000 | |||
100,000 | |||
1,000,000 | |||
10,000,000 |
Conclusions: Summarizes what the authors learned during the process of developing this lab. It must have an extension of at least 100 words.
Acknowledgements: (Optional) Include the name of anyone who helped to develop this lab that is not part of the team.
References: Includes the citations to any document consulted (electronic or on paper) using the APA style.
Appendix: Includes the contents of all the source files used to develop this lab (*.cpp
files, *.h
files, Makefile
files, etc.).
Download the report as a PDF document with the following name: lab4_report.pdf
.
To deliver the lab4_report.pdf
file, please provide the following information:
Only one team member needs to upload the file.
Due date is Tuesday, October 18.