I was implementing a version of insertion sort when I noticed my function did not work properly if implemented the following way. This version is supposed to sort the elements as they are copied into a new array while keeping the original intact.

vector<int> insertionSort(vector<int>& heights) {
    vector<int> expected(heights.size(), 0);
    int j, key;
    for(int i = 0; i < expected.size(); i  ){
        expected[i] = heights[i];
        
        j = i-1;
        key = expected[i];
        while(j >= 0 && expected[j] > key){
            expected[j 1] = expected[j--];    
        }
        
        expected[j 1] = key;
        
    }
    
    return expected;
}

I noticed that when doing expected[j--] the function does not work as it should but when I decrement outside of the bracket it works fine. In other words, what is the difference between

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

and

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

CodePudding user response：

To answer this, we need to take a look at what order the arguments to expected[j 1] = expected[j--]; are evaluated in. Looking at cppreference's page on order of evaluation, we see the following applies for C 17 and newer:

20. In every simple assignment expression E1 = E2 and every compound assignment expression E1 @= E2, every value computation and side effect of E2 is sequenced before every value computation and side effect of E1

In your case, this means that every value computation and side effect of expected[j--] is computed before it begins evaluating expected[j 1]. In particular, that means that j 1 will be based on the value j has after you've decremented it with j--, not the value it had before.

Prior to C 17, it was indeterminate whether the left hand side or the right hand side of the assignment operation was sequenced first. This means that in C 14 and earlier, your code exhibits undefined behavior:

2. If a side effect on a memory location is unsequenced relative to a value computation using the value of any object in the same memory location, the behavior is undefined.

In this case "a memory location" is j and the decrement in j-- is unsequenced relative to the value computation j 1. This is very similar to cppreference's example of undefined behavior:

a[i] = i ; // undefined behavior until C 17

In the second version of your code, the decrement to j does not take place until after the assignment has been completed.