ALGORITHM SortAnalysis(A[0..n − 1])
//Input: An array A[0..n − 1] of n orderable elements
//Output: The total number of key comparisons made
count ← 0
for i ← 1 to n − 1 do
v ← A[i]
j ← i − 1
while j ≥ 0 and A[j ] > v do
count ← count + 1
A[j + 1]← A[j ]
j ← j − 1
A[j + 1] ← v
return count
1. Please put the counter in the right place before continuing.
2. a. Code the driver of the algorithm above, with a properly inserted counter (or counters) for the number of key comparisons, on 20 random arrays of sizes 1000, 2000, 3000,..., 20,000.In addition to running the algorithm on the random arrays as indicated in 2a, I also want you to run the algorithm against the arrays sorted in ascending order, and then again on arrays already sorted in descending order. Perform the analysis for all three situations.
b. Analyze the data obtained to form a hypothesis about the algorithm’s average-case efficiency.
c. Estimate the number of key comparisons we should expect for a randomly generated array of size 25,000 sorted by the same algorithm.
Please code the algorithm in Java.
The output must be in a format that will allow me to copy and paste the numbers in an excel spreadsheet.