Inserting Value in ordered Array?

Question #1:

Can someone explain me what is happening in the below code snippet?

Answer #1:

Lets first examine how one would iterate through such a structure and print out the elements in order. I'm using the example from the book in your question:

Here's how it looks in Java:

int i = 0;
while (k[i] != 0) {
    System.out.println(a[k[i]]);
    i = k[i];
}

If you want to insert a value to such a structure, you have to know how to iterate it. You have to know the i of the first element (a[k[i]]) that is equal to or greater than the element you wish to insert (x):

Procedure insert(x) inserts x to a[free].

Now the indices have to be updated to accommodate an extra link in the ordered chain. That is, to go from this:

| ... | a[k[i]] >= x | ... |

to this:

| ... | x | a[k[i]] >= x | ... |

The element directly after x is a[k[i]]. We have to temporarily detach it from the chain to insert x. Therefore: k[free] = k[i].

Next, do: k[i] = free. a[k[i]] will now be x (remember, we inserted x to a[free]).

Now the magic happens. a[k[i]] == x and the element directly after it is a[k[free]] (which used to be a[k[i]] before).

Then free is incremented by one and we are done.

Question #2:

How should I initialise variable k (as an index array for a array) and what should be the values for a?

Answer #2:

The example from the book looks just fine:

import java.util.Arrays;
class IndirectReference {
    static final int Q = 0; // This value is irrelevant; added for clarity
    static int a[] = {Q, 44, Q, 22, 55, 33, 66, Q};
    static int k[] = {3, 4, Q, 5, 6, 1, 0, Q, Q, Q};
    static int free = 7;
    
    public static void main(String[] args) {
        insert(50);
        
        System.out.print("a = ");
        System.out.println(Arrays.toString(a));
        
        System.out.print("k = ");
        System.out.println(Arrays.toString(k));
        
        System.out.println("free = " + free);               
    }
    
    static void insert(int x) {
        int i = 0;
        while (k[i] != 0 && a[k[i]] < x) {
            i = k[i];
        }
        a[free] = x;
        k[free] = k[i];
        k[i] = free++;
    }
}

Note: this procedure relies on the fact that free saves the index of the next free location in both tables.

In the example above, it's wrongly set to 8 after insertion of 50 because the procedure assumes there's always enough space at indices free, free+1, free+2, ... in both a and k.

Once you run out of free space you can either resize both arrays or compact them (put non-trailing ?s at the end of both tables), though I can't quite see a clear way how to do that.

You can initialise k and a to be empty integer arrays:

int[] a = new int[10];
int[] k = new int[10];
int free=0;

The empty spaces in a are probably to illustrate what it could look like if there had been some deletions. If all you are doing is inserting, all elements of a before a[free] would have an inserted value, although it can still be 0 if you inserted a 0, but that's not what appears to have happened in the example.

As to what the code is doing, that's a bit of a longer explanation. The data values in a are our inserted data. The data values in k are references to index elements in a and k which we can follow to traverse our data in ascending order. The value of k[0] will always contain the index of a which has the lowest data value. So using the example from the book, k[0] is 3. a[3] is 22, and 22 is the lowest data value in our ordered list.

The data in k is also used to traverse the elements of k, and we always start at 0. So the next element would be k[3], which contains a 5. a[5] is 33, the second-lowest number in our data.

So if we wanted to insert 27 into the list, and we follow this algorithm, the relevant entries in k are k[0]==3, k[3]==5, and k[5]==1. After we insert, a[7] will be 27 because free was 7 when we inserted (will be 8 after the insert). k[0] will still be 3, since 22 is still our lowest value data. k[3] will be 7, since our second-lowest data value is now 27 and is stored at a[7]. k[7] will be 5, since a[5] is 33, now our third-lowest data value, and k[5] is still 1 (hasn't changed).

So where we would have traversed our list following k indices 0,3,5,1,4,6 (according to the book), we would now follow this path: 0,3,7,5,1,4,6, giving us data values: 22, 27, 33, 44, 55, 66