Java Insertion Sort with an Array List of objects?

Question

I have a class Card which contains value (int), suit (String) and faceValue (String). It seems like a regular insertion sort on Card.value should work fine. I just use the whole object when moving things around. For some reason, this crashes and burns. It ends up duplicating the highest card into every element except for a random element that I can't understand.

value, suit, and faceValue are pulic, also.

This is my code:

public static void insertionSort(ArrayList<Card> Array) {

    int i,j;
    Card key = new Card(0, "","");

    for (i = 1; i < Array.size(); i++) {
        key.value = Array.get(i).value;
        key.suit = Array.get(i).suit;
        key.faceValue = Array.get(i).faceValue;
        j = i;
        while((j > 0) && (Array.get(j - 1).value > key.value)) {
            Array.set(j,Array.get(j - 1));
            j--;
        }
        Array.set(j,key);
    }


}

I checked this against Wikipedia's pseudo code, and I can't find any fundamental difference. I've been through the debugger a dozen times, and I can't see any reason for the compiler to do what it's doing. Does anyone have an idea why it's not working?

Thanks.

Is using the language features an option? Having Card implement Comparable and using Collections.sort — oschlueter
– oschlueter, Commented May 6, 2014 at 20:11
@oschlueter I think that he uses this algorithm for practice. — DRAX
– DRAX, Commented May 6, 2014 at 21:01

Community · Accepted Answer · 2016-04-06 05:58:29Z

4

I would like to extend ginz's answer.

Java objects are passed by reference. So you are changing one object and setting it to multiple indexes.

To visualize (before and after):

visual representation

For after: Please note that not all indexes must reference to same object. Some of them could remain unchanged.

Better approach would be to move objects, instead of trying to duplicate them.

Also, by Java standard, name of properties (variables) should always start with small letter.

Here is working code:

public static void insertionSort(ArrayList<Card> array) {
    int i, j;
    for (i = 1; i < array.size(); i++) {
        Card tmp = array.get(i);
        j = i;
        while ((j > 0) && (array.get(j - 1).value > tmp.value)) {
            array.set(j, array.get(j - 1));
            j--;
        }
        array.set(j, tmp);
    }
}

edited Apr 6, 2016 at 5:58

CommunityBot

11 silver badge

answered May 6, 2014 at 20:56

DRAX

32.8k2 gold badges28 silver badges30 bronze badges

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

1 Comment

TechnoSam Over a year ago

Yeah, normally I'm pretty good with the lowercase names, I'm not sure why I differed this time. Thanks for pointing that out. =)

benc · Accepted Answer · 2024-12-13 23:09:22Z

3

At every cycle, you insert the object "key" into the list (Array.set(j,key);). So, at the end your whole list will be made of references to the object "key". So when you set key.value, key.suit and key.faceValue at the end, you are setting the fields of every element of your list, because your list consists of references of the same object.

move Card key = new Card(0, "",""); inside the for loop. Like this:

public static void insertionSort(ArrayList<Card> Array) {

    int i, j;

    for (i = 1; i < Array.size(); i++) {
        Card key = new Card(0, "","");
        key.value = Array.get(i).value;
        key.suit = Array.get(i).suit;
        key.faceValue = Array.get(i).faceValue;
        j = i;
        while((j > 0) && (Array.get(j - 1).value > key.value)) {
            Array.set(j,Array.get(j - 1));
            j--;
        }
        Array.set(j,key);
    }


}

gl with your studies :)

edited Dec 13, 2024 at 23:09

benc

2,1195 gold badges35 silver badges44 bronze badges

answered May 6, 2014 at 21:00

Kicsi

1,1431 gold badge10 silver badges23 bronze badges

4 Comments

njzk2 Over a year ago

again, set is not insert.

TechnoSam Over a year ago

Thanks! Wow, I never thought of that, but it actually makes sense. I really appreciate that! Thanks for the well wishes. =)

DRAX Over a year ago

Keep in mind, that this code makes unnecessary object duplicates.

njzk2 Over a year ago

also this does not scale. How does it work if you have tens of properties in your object? not to mention that you destroy the initial objects and replace then by new ones. good way to break things elsewhere in your code.

Dmitry Ginzburg · Accepted Answer · 2014-05-06 20:32:38Z

3

You're setting all the fields of Array(OMG, please rename it!) with the same element: key. So, all the elements would be the same.

answered May 6, 2014 at 20:32

Dmitry Ginzburg

7,4612 gold badges41 silver badges48 bronze badges

1 Comment

QuantumMechanic Over a year ago

Piling on the "rename it, for the sake of all that is holy!" bandwagon along with you...

njzk2 · Accepted Answer · 2024-12-13 18:55:01Z

2

The basic algorithm is

for each element
search for the first smaller element going downward
insert element right after that

So, in your case:

public static void insertionSort(ArrayList<Card> cards) {

    for (int i = 1; i < cards.size(); i++) {
        int value = cards.get(i).value;
        for (int j = i-1; j >= 0; j--) {
            if (cards.get(j).value <= key.value) {
                break;
            }
        }
        cards.add(j,cards.remove(i));
    }
}

One important point here is that at no point does the array contains duplicated values (which happens when you use set)

edited Dec 13, 2024 at 18:55

answered May 6, 2014 at 21:14

njzk2

39.4k7 gold badges72 silver badges111 bronze badges

4 Comments

SnappyRiffs Dec 11, 2024 at 22:09

make sure that it should be int j = 1 not j=i

njzk2 Dec 12, 2024 at 20:27

@SnappyRiffs cards from 0 to i are sorted, since they have been inserted in order

SnappyRiffs Dec 12, 2024 at 21:45

you did not set j to an integer. The compiler will not work unless you set j to int

njzk2 Dec 13, 2024 at 18:54

that's weird... thanks

user8833640 · Accepted Answer · 2021-05-19 03:14:25Z

0

Use Iterator for getting the elements.

public static void insertionSort(ArrayList<Integer> arrL) {
    Iterator<Integer> it = arrL.iterator();

    while(it.hasNext()){
        int new_element = it.next();

        int j = arrL.indexOf(new_element);
        while(j>0 && arrL.get(j-1)>new_element){
            arrL.set(j, arrL.get(j-1));
            j--;
        }

        arrL.set(j, new_element);
    }
 }

answered May 19, 2021 at 3:14

user8833640

1

Collectives™ on Stack Overflow

Java Insertion Sort with an Array List of objects?

5 Answers 5

1 Comment

4 Comments

1 Comment

4 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

1 Comment

4 Comments

1 Comment

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related