Question about in-place sort

Question

For example, we have the following array:

char data[]=new char[]{'A','S','O','R','T','I','N','G','E','X','A','M','P','L','E'};

and an index array:

int  a[]=new int[]{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14};

void insitu (char data[], int a[], N)
{
    for (int i=0;i<N;i++)
    {
        char v=data[i];
        int j, int k;
        for (k = i; a[k] != i; k = a[j], a[j]=j)
        {
            j=k;
            data[k]=data[a[k];
        }
        data[k]=v;
        a[k]=k;
    }
}

My question is what j should be initialized to. When I run this code, it asks me to initialize j; what should I do?

Answer 1

This is a Java implementation of the in-place sort in Sedgewick's Algorithms in C++ (see page):

public class InSitu {
    public static void main(String[] args) {
        int[] a = { 0, 10, 8, 14, 7, 5, 13, 11, 6, 2, 12, 3, 1, 4, 9 };
        char[] data = { 'A', 'S', 'O', 'R', 'T', 'I', 'N', 'G',
            'E', 'X', 'A', 'M', 'P', 'L', 'E' };
        insitu(data, a, a.length);
        System.out.println(java.util.Arrays.toString(a));
        // prints "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]"
        System.out.println(java.util.Arrays.toString(data));
        // prints "[A, A, E, E, G, I, L, M, N, O, P, R, S, T, X]"
    }
    static void insitu(char[] data,int[] a, int N) {
        for (int i = 0; i < N; i++) {
            char v = data[i];
            int j, k;
            for (k=i; a[k] != i; k = a[j], a[j] = j) {
                j = k;
                data[k] = data[a[k]];
            }
            data[k] = v;
            a[k] = k;
        }
    }
}

---

On array declarations

Please, please, do not make a habit of declaring arrays like this:

int x[];

You should instead put the brackets with the type, rather than with the identifier:

int[] x;

Related questions

• Is there any difference between Object[] x and Object x[] ?
• Difference between int[] myArray and int myArray[] in Java
• in array declaration int[] k,i and int k[],i
  • These declarations result in different types for i!

---

On definite assignment

The compiler is smart enough to know when a local variable is definitely assigned, taking into account loop constructs, etc.

The following code compiles:

        int local;
        do {
            local = 0;
        } while (local != 0);

While this doesn't:

        int local;
        while (local != 0) { // doesn't compile!
            local = 0;
        }

Similarly, this compiles:

        for (int local; ; local++) {
            local = 0;
        }

This is because of the semantics of for loop, where the loop body (local = 0;) precedes the loop update (local++) in the control flow, even though it may not look like it in the text.

The specification doesn't allow the compiler to be too smart; for example the following doesn't compile:

    boolean b = false; // or whatever
    int local;
    if (b) {
        local = 0;
    }
    if (!b) {
        local = 1;
    }
    local++; // doesn't compile! 

But this does:

    boolean b = false; // or whatever
    int local;
    if (b) {
        local = 0;
    } else {
        local = 1;
    }
    local++;

See also

• JLS 16 Definite Assignment