Question

1a .Write a program that perform insertion sort (ascending order) on an input array and print the total number of comparisons that have been made. You can implement by using any programming languages such as C/C++. For example, in the case of array B = [ 30 , 10 , 20 , 40 ], there are 4 needed comparisons to perform insertion sort (30 vs 10, 20 vs 30, 20 vs 10, and 40 vs 30).

1b. Write a program that perform insertion sort while printing the value of input array after each step of insertion sort from the leftmost element to the rightmost element. You can implement by using any programming languages such as C/C++, Java, Python, etc. After that, perform test on the given array A.

A= [7,6, 12, 9, 3, 4, 5, 11, 9, 14, 2, 8]

Answer 1

Answer 1:

public class InsertionSort {
   /* Function to sort array using insertion sort */
   static int sort(int values[], int numValues) {
       int n = numValues;
       int count=0;
       for (int i = 1; i < n; ++i) {
           int key = values[i];
           int j = i - 1;

           while (j >= 0 && values[j] > (key)) {
               values[j + 1] = values[j];
               j = j - 1;
               count++;
           }
           values[j + 1] = key;
           //printArray(values);
       }
       return count+2;
   }

   /* A utility function to print array of size n */
   static void printArray(int arr[]) {
       int n = arr.length;
       for (int i = 0; i < n; ++i)
           System.out.print(arr[i] + ",");

       System.out.println();
       System.out.println();
   }

   // Driver method
   public static void main(String args[]) {
       int arr[] = {30 , 10 , 20 , 40};
       int c=sort(arr, arr.length);
       printArray(arr);
       System.out.println("Number of comparions : "+c);
   }
}

Answer 2:

public class InsertionSort {
   /* Function to sort array using insertion sort */
   static int sort(int values[], int numValues) {
       int n = numValues;
       int count=0;
       for (int i = 1; i < n; ++i) {
           int key = values[i];
           int j = i - 1;

           while (j >= 0 && values[j] > (key)) {
               values[j + 1] = values[j];
               j = j - 1;
               count++;
           }
           values[j + 1] = key;
           printArray(values);
       }
       return count+2;
   }

   /* A utility function to print array of size n */
   static void printArray(int arr[]) {
       int n = arr.length;
       for (int i = 0; i < n; ++i)
           System.out.print(arr[i] + ",");

       System.out.println();
       System.out.println();
   }

   // Driver method
   public static void main(String args[]) {
       int arr[] = {7,6, 12, 9, 3, 4, 5, 11, 9, 14, 2, 8};
       int c=sort(arr, arr.length);
       System.out.println("Number of comparions : "+c);
   }
}