I have following Insertion Sort implementation in java and I had following questions:

a) the pseudocode of the insertion sort algorithm and assertions between lines of the algorithm.

b) As insertion sort has a nested-loop of two layers, you need to put one assertion in each loop.

c) a proof of the partial correctness of the algorithm using mathematical induction

c.1) prove the correctness of the two assertions you added in the previous question.

d) a theoretical analysis of the running time of the algorithm using big-Oh

Analyze the complexity of insertion sort algorithm using big-Oh. Briefly show how to derive the big-Oh notation in terms of the number of primitive operations.

e) an experimental analysis of the running time of the algorithm

You may write some codes to conduct the experiments. For example, you may randomly sample nelements, run the insertion sort program to sort these n elements in an ascending order, and calculate the time required. Different values of n should be used to conduct the experiments. Then you may plot a running time figure with respect to the input size n, and check whether it is consistent with your theoretical complexity analysis.

InsertionSort.java:

package insertionsort; /** * * @author author */ public class InsertionSort {

/** * @param args the command line arguments */ public static void main(String[] args) { int[] array1 = {48,24,42,112,14,134,16,84,68}; int[] array2 = Insertion_Sort(array1); //loop for diplay array2 with , seperated for(int i:array2){ System.out.print(i); System.out.print(","); } } //method Insertion_sort for sorting array public static int[] Insertion_Sort(int[] array_input){ //temp variable int temp; //for loop excute untill the length of aaray1 and it's length is 9 for (int i = 1; i < array_input.length; i++){ //nested loop for swappig array element in reverse order for(int j = i ; j > 0 ; j--){ //swap value with used of temp variable if(array_input[j] < array_input[j-1]){ temp = array_input[j]; array_input[j] = array_input[j-1]; array_input[j-1] = temp; } } } return array_input; } }