removing duplicates using insertion sort java

Question

I am having half an issue with the following code, it is an insertion sort method used with the Comparable interface. In this specific case it is supposed to sort elements in decreasing order, which it does fine. However, I am also trying to remove duplicates within the same method but it is not working. I was wondering whether it is actually possible to do that within the same method? I have looked at the answer at the following question Removing Duplicates Inside Insertion Sort but I am not sure how to apply it in here. Not necessarily looking for the solution but if you can point me into the right direction from where I can take it further. Thanks in advance.

public void InsertionSortDecrease(){
    for(int i=1;i<size();i++){
        T keyelement = get(i);
        int pos=i;
        while(pos > 0 && 
(((Comparable)keyelement).compareTo((Comparable)get(pos-1)) > 0)){
            set(pos,get(pos-1));
            pos--;
        }
        set(pos,keyelement);
        if(((Comparable)get(pos)).compareTo((Comparable)get(pos+1)) 
== 0){
            remove(pos);
        }
    }
}

Have you implemented equals() for the class of your keyObject? Even better, declare the type as T extends Comparable<T> — Bohemian
– Bohemian ♦, Commented Dec 11, 2017 at 19:54

C.Champagne · Accepted Answer · 2017-12-11 20:08:21Z

1

I would personaly use a TreeSet which does what you want.

You can only add an item if it is not already present in the set which is always kept sorted.

answered Dec 11, 2017 at 20:08

C.Champagne

5,5492 gold badges25 silver badges39 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

FranB Over a year ago

Thank you, never used it but I am going to experiment with that

Snow · Accepted Answer · 2017-12-11 19:52:58Z

0

You are attempting to remove elements while sorting them. For something like this an Iterator would be a lot better to avoid running into a concurrent modification error.

answered Dec 11, 2017 at 19:52

Snow

11 bronze badge

Comments

Bohemian · Accepted Answer · 2017-12-11 20:54:31Z

0

Your bug is you are counting up, but you should be counting down, because there's no more room to the left of the final result so you should be shuffling to the right as you find the insertion point.

You'll then need to compare for duplicate the current and the previous (if it exists) positions, because you'll already know it's less than the next due to the terminating condition of the first loop. But then you'll have to shuffle them all back if it's a dupe.

Better, first find the insertion point, then if it's a dupe do nothing otherwise shuffle and insert. If you refactor your code in this way, you can then improve the insertion point finder from O(n) to O(log n) by doing a binary search because you know you are operating with sorted data.

answered Dec 11, 2017 at 20:54

Bohemian♦

427k103 gold badges604 silver badges750 bronze badges

1 Comment

FranB Over a year ago

Thanks you and apologies about the delay in responding.

Collectives™ on Stack Overflow

removing duplicates using insertion sort java

3 Answers 3

1 Comment

Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related