3 To the insertSortjava program Listing 33 add a method call

.3 To the insertSort.java program (Listing 3.3), add a method called noDups() that removes duplicates from a previously sorted array without disrupting the order. (You can use the insertionSort() method to sort the data, or 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 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.

Solution

//copy the each distinct element into the new array

//you will get the new modified array

//which achieves O(N) time complexity.

//Look at the below code.

public class InsertionSort {

   public static void main(String[] args) {
       int A[] = {8,5,1,5,5,1,0,7,3};
       insertionSort(A);
A=noDups(A);
for(int i=0;i<A.length;i++)
{
System.out.println(A[i]);
}

   }
// the below method will removes the duplicates and add the unique elements to another array and returns the array
//which achives the time complexity of O(N).
static int[] noDups(int[] a)
{
int[] b=new int[6];
int count=0;
for(int i=0;i<a.length;i++)
{
while((i<(a.length-1))&&(a[i]==a[i+1]))
{
i++;
}
b[count]=a[i];
count++;
}
return b;
}
   /**
   * This method will sort the integer array using insertion sort in java algorithm
*/
   private static void insertionSort(int[] arr) {
       for (int i = 1; i < arr.length; i++) {
           int valueToSort = arr[i];
           int j = i;
           while (j > 0 && arr[j - 1] > valueToSort) {
               arr[j] = arr[j - 1];
               j--;
           }
           arr[j] = valueToSort;
       }
   }
}

---------------------------------------thanks-------------------------------------------