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?

Answer 1

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;
     }
}

Answer 2

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.