Java insertion sorting: "same" variable get different result

Question

I was doing an insertion sort using Java. For example, if I have an integer array {8,7,6,5,4,3,2,1},

This will give me the result which is wrong: 7,6,5,4,3,2,1,8 picture

public static int[] insertionSort(int[] list) {
    int[] insertionList = list.clone();
    for(int i = 1; i < insertionList.length; i++) {
        int temp = insertionList[i];
        int j = i - 1;
        while(j >= 0 && insertionList[j] > insertionList[i]) {
            insertionList[j + 1] = insertionList[j];
            j--;
        }
        insertionList[j + 1] = temp;
    }
    return insertionList;
}

And this will give me the result which I wanted: 1,2,3,4,5,6,7,8 picture

public static int[] insertionSort(int[] list) {
    int[] insertionList = list.clone();
    for(int i = 1; i < insertionList.length; i++) {
        int temp = insertionList[i];
        int j = i - 1;
        while(j >= 0 && insertionList[j] > temp) {
            insertionList[j + 1] = insertionList[j];
            j--;
        }
        insertionList[j + 1] = temp;
    }
    return insertionList;
}

Just wondering what different between insertionList[i] and temp. I wrote two println statements to test these, but they also show the same number.

Thanks!!!!!

You should add your code in the post also. By the way, the first version of insertion sort seem wrong in your test. it should be "8,7,6,5,4,3,2,1" -> "7,8,6,5,4,3,2,1" — Huy Nguyen, Oct 08 '18 at 03:05
Of course there is a difference between the two. `insertionList[i]` might be modified within the while loop but `temp` does not change. — Dabiuteef, Oct 08 '18 at 03:07
Just a guess: perhaps it's because `insertionList[i]` gets over-written in your `while` loop. So preserving the value before the loop starts prevents a bug. — dave, Oct 08 '18 at 03:08
Possible duplicate of [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) — Max Vollmer, Oct 08 '18 at 03:29
As others have correctly pointed out, `insertionList[i]` changes in the loop, `temp` does not. Things like this are easily detected using a debugger. Check the linked duplicate to learn how. — Max Vollmer, Oct 08 '18 at 03:31

Johnson Carneiro · Answer 1 · 2018-10-08T03:36:49.010

1

The difference is that the 'insertionList' gets modified inside the while loop. When you set the temp variable to 'insertionList[i]' the value of temp remains the same throughout the while loop.

edited Oct 08 '18 at 03:36

answered Oct 08 '18 at 03:27

Johnson Carneiro

109
1
6

I used JetBrains, eclipse, and terminal in my mac. all result are same. I didn't get right answer in the code with insertionList[i] – Chenran J Oct 08 '18 at 03:42

score 0 · Accepted Answer · answered Oct 08 '18 at 03:11

0

while(j >= 0 && insertionList[j] > insertionList[i]) {
            insertionList[j + 1] = insertionList[j];
            j--;
        }

the wrong is here. insertionList[j + 1] = insertionList[j]

in the first execution, j + 1 = i, and it will change the value of insertionList[i]

and it will effect to your condition.

insertionList[j] > insertionList[i]

So it should be change to temp variable.

answered Oct 08 '18 at 03:11

Huy Nguyen

1,931
1
11
11

I still get same result. – Chenran J Oct 08 '18 at 03:49
you ask "Just wondering what different between insertionList[i] and temp", i explained it. – Huy Nguyen Oct 08 '18 at 05:05

score 0 · Answer 3 · answered Oct 08 '18 at 03:51

while(j >= 0 && insertionList[j] > insertionList[i]) In this line you are comparing with the ith element of insertionList and during the iteration in while loop insertionList[j + 1] = insertionList[j]; this code might change the value insertionList[i] was holding. But when you are using temp variable then for the whole iteration the value for comparison here insertionList[j] > temp does not change. That's why you are getting different output.

Java insertion sorting: "same" variable get different result

3 Answers3