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, youll 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(N2 (only a few items out of place). What can you deduce about the efficiency of this algorithm for almost-sorted data? ) efficiency? Do the same 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; j

for(out=1; out0 && 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() //-------------------------------------------------------------- } // 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);

arr.display(); // display items

arr.insertionSort(); // insertion-sort them

arr.display(); // display them again } // end main() } // end class InsertSortApp