Lab #4: Sorting Algorithms

Description

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:

• Insertionsort

• Selectionsort

• Bubblesort

• Quicksort

• Mergesort

• Countingsort

Write a report with the results of running each algorithm as explained below.

General Considerations

• 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:

  • 100 (one hundred) items
  • 1,000 (one thousand) items
  • 10,000 (ten thousand) items
  • 100,000 (one hundred thousand) items
  • 1,000,000 (one million) items
  • 10,000,000 (ten million) items

• The execution of each algorithm using a vector of each size must be timed under three initial conditions:

  • The original vector contains pseudo-randomly computed items and is therefore, for practical purposes, unsorted.
  • All items from the original vector are in ascending order. In other words, the vector is initially ordered.
  • All items from the original vector are in descending order. In other words, the vector is initially in reverse order.

  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.

Starter Code

Initializing the values of a vector

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;
    }
}

Measuring Execution Times

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() / 1'000'000.0;

Deliverables

Using the word processor of your choice, write a single 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 "siblings" /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.).

Upload the report as a PDF document with the following name: lab4_report.pdf.

Only one team member needs to upload the file.

Due date is Wednesday, October 30.