Here's an interesting way to remove duplicates from an array. The insertion sort uses a loop-within-a-loop algorithm that compares every item in the...

Here’s an interesting way to remove duplicates from an array. The insertion sort

uses a loop-within-a-loop algorithm that compares every item in the array with

every other item. If you want to remove duplicates, this is one way to start.

(See also Exercise 2.6 in Chapter 2.) Modify the insertionSort() method in the

insertSort.java program so that it removes duplicates as it sorts. Here’s one

approach: When a duplicate is found, write over one of the duplicated items

with a key value less than any normally used (such as –1, if all the normal keys

are positive). Then the normal insertion sort algorithm, treating this new key

like any other item, will put it at index 0. From now on the algorithm can

ignore this item. The next duplicate will go at index 1, and so on. When the

sort is finished, all the removed dups (now represented by –1 values) will be

found at the beginning of the array. The array can then be resized and shifted

down so it starts at 0.