Data Structures

Lab #4: Sorting Algorithms

Objective

During this activity, students will be able to:


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:

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

General Considerations

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:

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


Upload Instructions

To deliver the lab4_report.pdf file, please provide the following information:

Request PIN

Only one team member needs to upload the file.

Due date is Tuesday, October 31.