Greetings!

This semester I am taking a Data Structures & Algorithms class in Java. We just got introduced to topic like searching through Arrays, simple sorting methods, and Big O notation. I am confused with the third part of the assignment so some help would be well appreciated!

Thanks!

Assignment Prompt:

ArraysIn Sample Code

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

Modify the i n serti on Sort () method in Arrays Ins . Java 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 numbers and comparisons for diferent amounts of inversely sorted data. Do the results verify O(N') 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