Exercise 23
Info

This is an in-class exercise. An exercise page like this one will contain a brief description but is intended to be supplemented by discussion during our meeting time. Complete the exercise to the best of your ability in the time given. Feel free to talk with other students as you work, and do not be afraid to ask questions if you get stuck. Aim to complete as much as possible during our meeting, and submit on Gradescope to check your solution. You are encouraged to work at home to complete what you do not get through today, and ask questions over Piazza or in office hours.

Learning Objectives

Reinforces concepts learned in today meeting:

  • C++ basics: I/O using iostream library, how to compile/link/execute
  • Using the C++ Standard Template Library (std::vector)
  • Recursion
Task

Complete the implementation of code which read a target count from the standard input, generates a std::vector with that many random values, sorts them, and then validates that the result is in fact sorted.

Part 1

Get started by running git pull to update your clone of the public repository, and then copying the exercises/ex23 directory into your personal git repository. You’ll see that we have provided a file named sort.cpp.

Part 2

In the supplied file, sort.cpp, read an integer from the standard input into count.

Part 3

Modify the vec array so that it stores count random values.

Part 4

First, compile and link sort.cpp by typing:

g++ -std=c++11 -Wall -Wextra -pedantic sort.cpp -o sort

Next, run the executable sort, specify that the vector vec should have 50 values, and confirm that this causes an assertion failure (because the random numbers are not sorted), either by typing:

echo 50 | ./sort

or by calling the function:

./sort

and then entering the value 50 at the prompt.

Part 5

Define the sort function so that implements the merge sort algorithm.

Tip

The merge sort algorithm is a recursive algorithm for sorting a set of values. It splits a set of values into two, sorts each of the two subsets independently, and then merges the two sorted subsets into a single sorted set.