javainsertion-sortpost-incrementdecrement

Unclear behavior of ++/-- operators in sample insertion sort


I was practicing writing some sorting algorithms and wrote the following code for insertion sort:

public static void insertionSort(int[] nums) {
    for (int i = 1; i < nums.length; i++) {
        int idx = i;
        int val = nums[idx];
        while (idx > 0 && val < nums[idx - 1]) {
            nums[idx--] = nums[idx - 1];
        }
        nums[idx] = val;
    }
}

The previous code resulted in an index out of bounds exception at -1. My understanding of how nums[idx--] = nums[idx-1] would work is that nums[idx] would be assigned the value at nums[idx-1] and then the -- would reduce idx by one (I thought the whole purpose of having it after the variable was to allow the user to take action/execute assignments with the current value ~before~ incrementing it up or down. However, its seems that once the code checks nums[idx-1] on the left side of the expression, idx-- has already occured, resulting in the pointer hitting -1 at the end of the array. Based on this result, is it safe to say that my initial assumption that the decrementing is not the last executed part of this line, but rather we should assume that the decrementing will occur first if it is to the left of the next usage of the variable?

As a follow-up, does anyone know why is is set up to work this way? This seems counter-intuitive.

For reference, changing the code to the below fixed the issue, which verified that it must be incrementing prior to checking:

public static void insertionSort(int[] nums) {
    for (int i = 1; i < nums.length; i++) {
        int idx = i;
        int val = nums[idx];
        while (idx > 0 && val < nums[idx - 1]) {
            nums[idx] = nums[idx - 1];
            idx--;
        }
        nums[idx] = val;
    }
}

Solution

  • You're using idx multiple times per statement in line:

    nums[idx--] = nums[idx - 1];
    

    so here's what happens in your code:

    So, if idx was originally 1, nums[idx--] refers to nums[1] in step 1, but nums[idx - 1] refers to nums[0 - 1], which is nums[-1], leading to an ArrayIndexOutOfBoundsException.