# Lab: Sorting

## Learning Objectives

- Learn how to develop algorithms that solve computing problems.
- Learn about sorting algorithms.
- Learn about time complexity.

## Exercise 1: Sorting (20 points)

void mysort(vector<int> & 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 (20 points)

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.