How are expression with logical operators evaluated in Java?

Question

I have been trying to implement insertion sort in Java and came across a weird bug in my program. The while loop that did the insertion had the following condition:

while (arr[j] > key && j>=0)

The loop crashed with an ArrayIndexOutOfBoundsException when j<0. I spent hours trying to fix this, but apparently changing the order of expressions fixed the problem:

while (j >= 0 && arr[j] > key)

What is the reason behind this behaviour?
Here is the Complete Code:

//Insertion Sort

class Sort {
    public int[] sort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
        int j = i - 1;
        int key = arr[i];

        while (arr[j] > key && j>=0) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
    return arr;
    }
}

public class InsertionSort {
    public static void main(String[] args) {
        System.out.println("THis is it");
        int[] test = { 54, 68, 92, 3, 565, 8, 7, 64, 0 };
        Sort lort = new Sort();
        lort.sort(test);
        for (int a : test)
            System.out.println(a);
    }
}

Do you mean to say that the first version crashed with an `ArrayIndexOutOfBoundsException` while the second one didn't? That's plausible. — John Kugelman, Feb 04 '21 at 02:27

John Kugelman · Answer 1 · 2021-02-04T02:38:07.400

It's important to check if the array index is valid before attempting to access it. Java evaluates the left-hand side of && before the right-hand side. If you check arr[j] > key first then you don't know if j is a valid index since that's what j >= 0 checks.

When you swap the order and write j >= 0 && array[j] > key then it will only access array[j] if j is non-negative. If it's negative the loop bails immediately. The invalid index is never accessed, avoiding the exception.

Further reading:

aran · Answer 2 · 2021-02-04T02:58:21.800

When j hits -1, this:

while (arr[j] > key && j>=0)

Evaluates the first part and arr[-1] throws an ArrayIndexOutOfBoundsException.

When j hits -1, this:

while (j>=0 && ...)

Won't ever try to access to arr[-1], as this is an AND operator and the first condition being false is enough to end the evaluation. The second condition is irrelevant, hence not executed at runtime. This way you avoid trying to read from the position [-1] of a Java array;

Some say this is operation is cursed and Linus Torvalds will show up on your dreams for the rest of your life telling how bad C++ is.

score 1 · Accepted Answer · answered Feb 04 '21 at 02:38

The boolean operators (&& and ||) are 'short-circuiting'. This means: They will just up and drop what they were doing immediately, once it is clear the answer is set in stone.

In particular, that means somethingThatEvalsToFalse && foo results in foo not even being evaluated at all - false && anything is false, thus, there is no point. Same applies to somethingThatEvalsToTrue || foo - true || anything is neccessarily true, thus, foo need not be evaluated to provide the answer.

This is relevant if foo has side-effects. array[j] > key has the side-effect that it will throw AIOBEx if j is negative, or exceeds the size of array. The whole expression is not evaluated if short-circuiting kicks in.

The Java Lang Spec covers this, but I don't advise learning java by reading the lang spec. This should be a chapter in a tutorial.

How are expression with logical operators evaluated in Java?

3 Answers3