In this project we will 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)
Let n = 100.
Calculate the Average-case A(n) as we derived in class. Let bound be an integer (choose a large number).
Let tot-number-steps = 0 (accumulates total number of
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.
Repeat steps e 100,000 times (i.e., generate 100,000 random sequences and update tot-number-steps).
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
Please explain the outcome of the experiments.
