IN C++:

Try to match the Average Case of algorithm A10 as we derived in class and the Real Average of the algorithm using Monte Carlo approach.

A10: void Insertion (int A[ ], int n) // in reality the elements to be sorted are indexed from // index 1 to index n { int i,j, temp; A[0]=-32768; //smallest possible integer using 2 bytes integer representation for (i=1; i<=n; i++) { j=i; (1) while ( A[j] < A[j-1]) { // swap temp=A[j]; A[j]=A[j-1]; A[j-1]=temp; j--; } } } First you must modify A10 to return the number of steps executed. Please note that we consider only basic operations, which are the comparisons only. Call this subroutine Insertion-Mod( ).

1) (Calculated Average) a) Let n = 100. b) Calculate the Average-case A(n) as we derived in class. c) Let bound be an integer (choose a large number). d) Let tot-number-steps = 0 (accumulates total number of e) Generate a sequence of n integers (positive and negative as well) using a random number generator where the numbers of the sequence are between 0 and bound. Call Insertion-Mod ( ) using this sequence and add the number of steps returned by this algorithm to tot-number-steps. f) Repeat steps e 100,000 times (i.e., generate 100,000 random sequences and update tot-number-steps). g) Calculate the real average of algorithm A10 and let this number be A2(n).

Repeat steps a)-thru g) for the following values of n, n= {100, 500, 1000, 2500, 3000, 3500}. You final output should look like: Input size Calculated Average Real Average 100 XX XX 500 XX XX .. .. .. 3500 XX XX

----

Other answers on here are not correct, please don't copy and paste.