Removing Duplicates Inside Insertion Sort

Question

I am basically dealing with the following problem where i am trying to alter the insert sort so that it can also delete duplicates it counters. The following is the insert sort.

public void insertSort() {

        for (int i = 1; i < nElems; i++) {

            int temp = a[i];
            int j = i;

            while (j > 0 && temp <= a[j - 1]) {

                a[j] = a[j - 1];

                j--;
            }

            a[j] = temp;
        }

    }

I am not quire sure if i have understood the approach correctly. IF i am understanding this correctly(please tell me if i am wrong or not) the approach suggests that i should iterate through the entire array before the inner while loop begins and label any duplicate with a arbitrary number such as -1. And then when the inner while loop starts it will sort out the array and all the duplicates will be stacked up at the beginning together.

If this is the case then i can simply compare every element in the array with each other right before the insert sort begins and label any duplicates - 1 and then the insert sort will take care of the sorting part. After which i can reduce arraySize.

However i feel i have not understood it correctly so can someone please make any suggestions regarding this?

Verse

what is name of the book that you are reading? – Tugman

Data Structures And Algorithms In Java! @KickButtowski any suggestions regarding the question i posted?:) – Verse

I am about to leave my job take a look at it later – Tugman

You only need to insert one single line into your insertSort method. The line is if(temp == a[j - 1]) temp = -1;. Now you just need to figure out where to place it. – Dispel

put inside the while loop , The funny thing is i tried this before but what i did was if(temp == a[j - 1]) a[j-1] = -1; IF you post this as answer i can upvote you @SpiderPig – Verse

@SpiderPig just out of curiosity is this possible to do with selection sort? if so i will try to solve it my self for practice. – Verse

In a selection sort you are searching through the entire list to find the smallest or largest element. You can of course check during that phase if the element exists more than once and set all the other ones to -1. Although in that case you should probably always search for the largest element, not the smallest. Then all the -1 will end up at the end of the array. – Dispel

Answer 1

You only need to add a single line to your while loop.

while (j > 0 && temp <= a[j - 1]) {
    if(temp == a[j - 1]) temp = -1;
    a[j] = a[j - 1];

    j--;
}

You can think of the array as having two parts. The first part goes from 0 to i-1 and is sorted. The second part goes from i to the end of the array and is unsorted. In each iteration of the loop you take the first of the unsorted elements (which is a[i]) and place it into temp. This is the element you want to insert into the sorted part. Then you shift all the elements of the sorted part up until you find the place to insert temp. If you change temp to -1, your element that you are trying to insert now has become -1. The sorting algorithm will go on to try and insert -1 at the right place, which is the beginning of the array.

Dispel

Yeah this makes perfect sense, very slick. – Verse

Answer 2

public void InsertSort()
{
    int t, j;
    for (int i = 1; i < _leght; i++)
    {
       t = _arr[i];
       for (j = i; j > 0; )
       {
            if (_arr[j - 1] == t) t = -1;
            if (_arr[j - 1] > t)
            {
                  _arr[j] = _arr[j - 1];
                  j--;
             }
             else break;
        }
        _arr[j] = t;
     }
}

Klopstock