Objectives: Comparison of Insertion short and Shell sort

Shell sort is a highly efficient sorting algorithm and is based on Insertion sort algorithm. Write a program to sort a random integer array as follows:

$1.$Use Insertion sort to sort the random array. Print the number of comparisons, the number of item movements $($swapping$),$ and calculate the sorting time in nanoseconds.

$2.$Use Shell sort to sort the random array. $$Print the number of comparisons, the number of item movements $($swapping$),$ and calculate the sorting time in nanoseconds.

$3.$For each test case, calculate the time performance of Shell sort over Insertion sort in percentage using this formula:

o $$Calculate the difference of time performance of the two sorting algorithms

o $$Calculate the average of time performance of the two sorting algorithms.

o $$Time performance $=($difference $/$ average$)*100$

Extra Credit $(5$ points$)$

$4.$Setup a table to summarize the test data sizes and the time performance.

$5.$Create a graph to demonstrate the item $4.$

Test your program on different number of elements. $$To be consistent, use modulus $(\%)50$ for random function.

Notes on the sample outputs: $$The number of movements, comparisons and time performance of your program would not be the same as the sample given output because of the random array and different computers.

THIS IS AN EXAMPLE ON HOW THE OUTPUT SHOULD LOOK LIKE:

Sample Output $1$ Insertion and Shell sorts

$*****$ Program to compare Shell sort and Insertion sort $*****$

Enter the number of elements to be sorted $(0$ to exit$)$: $50$

$====================$ TEST $1=========================$

Test case with $50$ elements:

$58651501057723026897358784$

$3934885955017465315187413653$

$988929567436854168656691817617$

$6264365155$

$------------$ Insertion sort $------------$

$-$ Number of comparisons: $500$

$-$ Number of items moves: $546$

$-$ Sorting time : $6400$ nanoseconds

$112557101517172629303436$

$363639414146505051535355565758$

$596264656566687374768184858787$

$8889899198$

$------------$ Shell sort $------------$

$-$ Number of comparisons: $164$

$-$ Number of items moves: $246$

$-$ Sorting time : $5200$ nanoseconds

$112557101517172629303436$

$363639414146505051535355565758$

$596264656566687374768184858787$

$8889899198$

Time performance of Shell sort over Insertion sort: $20\mathrm{.}69\%$

$-------------------$ New Test Case $----------------------$

Enter the number of elements to be sorted $(0$ to exit$)$: $100$

$====================$ TEST $2=========================$

Test case with $100$ elements:

$68425736866976889749455189056$

$18529651432992232856976324672$

$1645478286352175787822814814$

$695272382959459714843573242767$

$29678513755555968128963412232$

$70619716986457489942451635276$

$037513491905655640$

$------------$ Insertion sort $------------$

$-$ Number of comparisons: $2449$

$-$ Number of items moves: $2542$

$-$ Sorting time : $30400$ nanoseconds

$0014556912141416171818$

$222223242427282829292932323435$

$363737384142434545464849515151$

$515252525254555555565656575759$

$596163636364646467686869697072$

$727376767678787878818486888989$

$90909192949697979798$

$------------$ Shell sort $------------$

$-$ Number of comparisons: $514$

$-$ Number of items moves: $747$

$-$ Sorting time : $14200$ nanoseconds

$0014556912141416171818$