do this question with Rstudios $2\mathrm{.}2$ Comparing SelectionSort$(),$ BubbleSort$(),$ and built$-$in sort$()$ for time

efficiency $(15$pts$)$

Let's compare the efficiency of three different sorting algorithms, we'll compare SelectionSort$(),$

the BubbleSort$()$ you just wrote, and the built$-$in $R$ implementation in sort$().$ We're going

to do this using a function called system.time$().$ The way it works is you put a function that

you want to time inside the system.time$()$ call, and then the code is run with the output

being the amount of time that it took.

x rnorm$(1$e$5)$

time system.time$($sort$($x$))$

time

user system elapsed

$0\mathrm{.}0020\mathrm{.}0000\mathrm{.}003$ You'll notice that this returns three different values. We'll use the first one, the user time,

which is also sometimes called the "wall clock" time. You'll note that the code takes longer than

this to run, because system.time$()$ also initiates a garbage collection procedure to improve

consistency between runs when timing. If you want to store just the first element of the timing

results from the code above, you can use time $[1].$

We will analyze run time of sorting algorithms as a function of the length of the input sequence.

For each of Nin$\{{10}^1,{10}^2,{10}^3,{10}^4\}$ :

Generate $25$ sequences of $N$ normally distributed numbers

Time how long it takes to sort each sequence using system.time$()$

The two previous steps are most easily done using a for$()$ loop. After you've stored

the run times, for each of the three sorting algorithms, compute the mean and standard

deviation of the observed run times

After you've done this for each sequence length, plot the mean run time and a $95\%$ confidence

interval for each algorithm as a function of $log(N).$ To plot the $95\%$ confidence interval, use

the geom$\_$errorbar$()$ function and note that the ymax and ymin will be $\frac{?}{\text{b}\text{a}\text{r}}(t)+-1\mathrm{.}96{}_t.$ Plot each

algorithm in a different color. What algorithm appears to perform best? Which performs

worst?

# TODO: Conduct the run time simulation and plot the results