Question

Exercise 1: Sorting

void mysort(vector & v);

Write a function called mysort that rearranges elements of a vector v so that they form an increasing sequence of values. Allow for different vector positions to contain the same value. Develop your own sorting algorithm; do not use a predefined sort routine from the standard library. Implement a simple sorting algorithm rather than an efficient algorithm. Write code that thoroughly tests your function. Express your tests using assertions.

Exercise 2: Comparison

For this exercise, create 2 programs defined in files slow.cpp and fast.cpp. In slow.cpp, generate a random vector of size 100,000 and pass it to your sorting algorithm. Run the program and observe that it never ends. Press CTRL C to terminate the process. In fast.cpp, generate a random vector of size 100,000 and pass it to the sort routine that is part of the C++ standard library. The following code shows how you would call the sort function on a vector v.

sort(v.begin(), v.end());

If the above line fails to compile, you may need to include the algorithm header as follows.

#include <algorithm>

Run fast.cpp and notice how quickly it terminates. The reason for this is that the sorting function in the standard library is using is more efficient than the one you produced. How quickly algorithms terminate is within an area of computer science referred to as complexity theory.