insertion sort - syntax question

I c开发者_Python百科ame across a rather peculiar shorthand notation: A[j+1] = A[j--]

It seems that this line does two operations: move A[j] right and decrement j

is it possible to break this down into individual steps to help me understand the shorthand?

Pseudo code:

n=A.length
for i <- 1 to n-1
    curr = A[i]
    j = i - 1
    while j >= 0 && A[j] > curr
        A[j+1] = A[j--]
    A[j+1] = curr

source

Sure:

int targetIndex = j + 1;
int tmp = j;
j--;
A[targetIndex] = A[tmp];

Note that the targetIndex is computed before anything else happens - the left hand side of the assignment operator is effectively determined before the right hand side.

However, the decrement happens before the assignment itself takes place, and even before the right hand array access is evaluated. You can see that in this sample code:

public class Test {
    public static void main(String[] args) {
        int[] x = { 0, 1, 2, 3, 4 };
        int j = 3;
        try {
            x[j + 1] = x[j-- + 10];
        } catch (Exception e) {
            System.out.println("Caught exception");
        }

        System.out.println(j); // Prints 2
    }
}

Here, you can see that j has been decremented even though the assignment itself can't take place.

Indeed, the same happens if we use x[j + 10] = x[j--]; - in other words, if it's the target index which is out of bounds. By the time that's discovered, the decrement has already occurred.

Since in your example, j is always less than A.length

A[j+1] = A[j--];

Is the same as

int index = j + 1;
A[index] = A[j];
j = j - 1;

as the following program illustrates:

import java.util.Arrays;

public class Test {
    public static void main(String[] args) {

        int[] A = { 1, 2, 3, 4, 5 };

        int j = 2;
        A[j+1] = A[j--];

        // prints: [1, 2, 3, 3, 5]
        System.out.println(Arrays.toString(A));

    }
}

I don't know if I good understood your problem but if you aren't sure j-- notation try my example. Shows difference between --j and j-- it can help you in the future:

public static void main(String[] args) {
    int j = 10;
    System.out.println("Current=" + j);
    System.out.println(j--);
    System.out.println("Current=" + j);
    System.out.println(--j);
    System.out.println("Current=" + j);
}

Output:

Current=10
10
Current=9
8
Current=8