3.5 Modify the insertionSort() method in insertSort.java (Listing 3.3) so it counts the number of copies and the number of comparisons it makes during a sort and displays the totals. To count comparisons, you'll need to break up the double condition in the inner while loop. Use this program to measure the number of copies and comparisons for different amounts of inversely sorted data. Do the results verify O(N^2) efficiency? Do the same for almost-sorted data (only a few items out of place). What can you deduce about the efficiency of this algorithm for almost-sorted data? // insertSort.java // demonstrates insertion sort // to run this program: C>java InsertSortApp class ArrayIns { private long[] a; // ref to array a private int nElems; // number of data items //-------------------------------------------------------------- public ArrayIns(int max) // constructor { a = new long[max]; // create the array nElems = 0; // no items yet } //-------------------------------------------------------------- public void insert(long value) // put element into array { a[nElems] = value; // insert it nElems++; // increment size } //-------------------------------------------------------------- public void display() // displays array contents { for(int j=0; j0 && a[in-1] >= temp) // until one is smaller, { a[in] = a[in-1]; // shift item to right --in; // go left one position } a[in] = temp; // insert marked item } // end for } // end insertionSort() public long valueAt(int index) { return a[index]; } public long median() { //Copy temp array and copy items ArrayIns b = new ArrayIns(nElems); for(int i = 0; i < nElems; i++) b.insert(a[i]); b.insertionSort(); if(b.nElems % 2 == 0) //If there are 2 middle numbers, return the average of them { int temp = b.nElems / 2; long median = (b.valueAt(temp) + b.valueAt(temp-1) ) / 2; return median; } else return b.valueAt(b.nElems/2); } //-------------------------------------------------------------- } // end class ArrayIns //////////////////////////////////////////////////////////////// class InsertSortApp { public static void main(String[] args) { int maxSize = 100; // array size ArrayIns arr; // reference to array arr = new ArrayIns(maxSize); // create the array arr.insert(77); // insert 10 items arr.insert(99); arr.insert(44); arr.insert(55); arr.insert(22); arr.insert(88); arr.insert(11); arr.insert(00); arr.insert(66); arr.insert(33); long medianValue = arr.median(); System.out.println(medianValue); arr.display(); // display items arr.insertionSort(); // insertion-sort them arr.display(); // display them again } // end main() } // end class InsertSortApp