3.3 To the insertSort0.java program (Listing 3.3), add a method called noDups() that removes duplicates from a previously sorted array without disrupting the order. You can simply use main() to insert the data in sorted order. One can imagine schemes in which all the items from the place where a duplicate was discovered to the end of the array would be shifted down (left) one space every time a duplicate was discovered, but this would lead to slow O(N^2) time, at least when there were a lot of duplicates. In your algorithm, make sure no item is moved (left) more than once, no matter how many duplicates there are. This will give you an algorithm with O(N) time. You may not use a second array to remove the duplicates. Input : arr[] = {1, 2, 2, 3, 4, 4, 4, 5, 5} Output : arr[] = {1, 2, 3, 4, 5} new size = 5

Insert Sort java --

class InsertSortApp0 { public static void main(String[] args) { int maxSize = 100; // array size ArrayIns0 arr; // reference to array arr = new ArrayIns0(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 ArrayIns0 arr2 = new ArrayIns0(maxSize); arr2.insert(1); arr2.insert(2); arr2.insert(2); arr2.insert(3); arr2.insert(4); arr2.insert(4); arr2.insert(4); arr2.insert(5); arr2.insert(5); arr2.display(); //arr2.noDups(); arr2.display(); } // end main() } // end class InsertSortApp

ArrayIns0 java --

// insertSort.java // demonstrates insertion sort // to run this program: C>java InsertSortApp //-------------------------------------------------------------- class ArrayIns0 { private long[] a; // ref to array a private int nElems; // number of data items //-------------------------------------------------------------- public ArrayIns0(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 ////////////////////////////////////////////////////////////////