This weeks, we cover insertion and selection sort algorithms. Both algorithms are given below. When two algorithms are compared on the same data set, it is expected that insertion sort outrun selection sort. It is because insertion sort makes less number of comparison than selection sort. However, computer simulations $($this$)$ show that they are close to each other in terms of running time. $"$So$,$ what are we missing" you may think.

Answer is running time of comparison vs swap operations. Insertion sort makes less number of comparisons than selection sort; however, insertion sort does lots of swaps $($data exchanges in the memory$).$ On the other hand, selection sort makes many comparisons but less number of swaps. Therefore these two algorithms are comparable to each other if data is randomly distributed even though algorithmic analysis shows insertion sort is faster than selection sort. In the computer memory comparison of two values $($such as less than, greater than, or equal to$)$ is much easier than swapping of two values.

Task

In this activity you need to compare both algorithms' running times $($see this$)$ on best, average, worst cases.

Subtasks

Define an int array with $32,000$ elements, and fill with ascending ordered numbers between $-20000$ and $20000,$ such as $[-19988,-19975,...0,...,19983,19989].$ Array items are randomly selected. Then, sort this array with selection and insertion sort algorithms. Report corresponding running times.

Define an int array with $32,000$ elements, and fill with random numbers between $-20000$ and $20000.$ The is no order to observe. Then, sort this array with selection and insertion sort algorithms. Report corresponding running times.

Define an int array with $32,000$ elements, and fill with descending ordered numbers between $-20000$ and $20000,$ such as $[19982,19979,...0,...,-19980,-19991].$ Array items are randomly selected. Then, sort this array with selection and insertion sort algorithms. Report corresponding running times.

Output of your program should be in the following format:

Asc ordered, SS: X sec$,$ IS: X sec

Ran ordered, SS: X sec$,$ IS: X sec

Des ordered, SS: X sec$,$ IS: X sec

X is number with two$-$decimal points. See this class example for the formatting hint.

Make sure that both algorithms sort the same array in each subtask. Use the sorting algorithms given below.

You need to implement your code using below pseudocodes.

Do not include unnecessary headers and functions.

$//$ Selection sort

for $($int i $=0$; i $<$ N; i$++)$

$\{$

int min $=$ i;

for $($int j $=$ i$+1$; j $<$ N; j$++)$

if $($ small$($A$[$j$],$ A$[$min$])==$ true$)$ min $=$ j;

swap$($A$,$ i$,$ min$)$;

$\}$