Insertion Sort and Generics

Insertion Sort and Generics
To the GenericArray.java program (provided in the lecture presentation), add a method called
removeDuplicates() that removes duplicates from a previously sorted array without disrupting the order.
(You must use the insertionSort() method to sort the data.) You 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 one
space every time a duplicate was discovered, but this would lead to slow O(N2
) time, at least when there
were a lot of duplicates. In your algorithm, make sure no item is moved more than once, no matter how
many duplicates there are. This will give you an algorithm with O(N) time. Question: How can this be
done?
Powered by