Implement all the following two sorting algorithms $($in separate functions$)$ per

the slides$$ codes:

$$ Insertion Sort

$$ Quicksort

Then, implement the following three versions by tweaking the algorithms

above, using the functions below $($respectively$).$ The versions below $($which may

result in enhancements$)$ should be modifications to the versions discussed in class.

$$ InsertionSortV$2$:

o Same as the lecture notes for bubble sort, this algorithm should detect

a sorted array and stop if found. Unlike the traditional version that

keeps going for n$-1$ passes every time.

$$ QuicksortV$2$

o In the original version, the pivot was the first item. Rerun your

experiment with two new pivot versions as below:

o QuicksortV$2$A: Pivot is the item in the middle of the array

o QuicksortV$2$B: Pivot is the item at the end of the array

Also, search any sorting algorithm that was not discussed in class, explain it and

its complexity and sort the arrays mentioned below using it$.$

Name: CSCI $215$ Worth $15\%$

Required Input Scenarios: You must read from files. Make sure you do

not update the files after sorting. Slides on how to read from a text file have been

provided.

Random Array:

Your program should sort the provided integer array of size $100,000$ filled with

random integers and sort it using the six algorithms listed above $($Insertion sort,

quicksort, InsertionSortV$2,$ QuicksortV$2$A$,$ QuicksortV$2$B$,$ and the one you chose$).$

Measure the time it takes each algorithm and compare the results. Make sure you are

using the provided random array. At the end, run the program at least three times

$($with the same provided array$),$ and take the average ofthese runs for each algorithm.

Use the library to determine the execution time.

Sorted Array $($Ascending Order$)$:

Repeat the same process above for a sorted array of the same size $(100,000).$ Make

sure you are using the provided sorted array.

Sorted Array $($Descending Order$)$:

Again, repeat the same process above for a sorted array in a descending order of the

same size $(100,000).$ Make sure you are using the provided array $($sorted in

descending order$).$

Of course, we are interested in comparing the traditional version$$s performance

against the $2$nd $($and third$)$ versions for insertion and quick sorting algorithms. You

should do so for all cases $($random$,$ ascending, and descending order$).$ For example,

the second version may be faster in one input scenario, but slower in another. Also,

we you should be looking into how each algorithm performs against a different one

including the new one you presented.

In other words, use the $6$ algorithms to sort all three arrays and report your findings.

The analysis is the most important part. By analysis, we are not just talking about the

results but the explanation of your results and the complexities.

Start your report with your system specifications and the programming environment:

Operating System, CPU, and RAM size $($screenshots would be good$).$ These results will

be system dependent. Try to document all the details. Also, use charts and tables to

compare all algorithms for the three tested arrays.

In your report, add references to where you searched codes or ideas from; anything

you didn$$t create, you have to cite $($by referencing the source$).$ Also, add comments

explaining how does your code work.

You must submit a softcopy and a hardcopy $($both are necessary to get a grade$).$ A

code from the net that does the sorting only is not enough, no grades for Google

search! You must achieve the requested task and report your findings in a scientific

manner. The inclusion of tables, figures, and screenshots are required. You must

include in your printed $($hardcopy$)$ report: The code you wrote $($used$)$ and

screenshots of the output screen.

After you finish, write a report regarding your findings for all the algorithms and try

to explain your findings. Include the code in an appendix. No need for the output, I

will check it from the soft copy. So$,$ your print function for the array before and after

the sorting should be there but commented out. Also, define const int SIZE $=100000$

and use it for your loops throughout the entire program