Needed help understanding insertion sort

Question

In this code how does this work (java):

/** Move A[A.length-1] to the first position, k, in A such that there
* are no smaller elements after it, moving all elements
* A[k .. A.length-2] over to A[k+1 .. A.length-1]. */

static void moveOver (int A[]) {
   moveOver (A, A.length-1);
}

/** Move A[U] to the first position, k<=U, in A such that there
* are no smaller elements after it, moving all elements
* A[k .. U-1] over to A[k+1 .. U]. */

static void moveOver (int A[], int U) {
  if (U > 0) {
    if (A[U-1] > A[U]) {
      /* Swap A[U], A[U-1] */
     moveOver (A, U-1);
    }
  }
}

I got this from a berkeley cs class I am going through online, teaching myself. it is not homework (i wish was but not that fortunate). what I don't understand is the following:

suppose the numbers in A[] are 8, 2, 10, 5, 4, 12. When I use them above I get this in my iterations, tracing it.

1. the upper most subscript is U, or in this case 12, U-1 is 4, no swap is done
2. U is now 4 (recursive U-1) and the number above it is 5 (the other U-1). they get swapped.
3. U is now 4 because four just moved up and 10 is U-1 they get swapped.

My sequence is now 8,2,4,10,5,12.

My question is how do I get the numbers I already passed by? how will I get five, for example, to move up if I never go back to that subscript to test with.

I don't think I am tracing the program correctly and my be getting confused with the recursion. For the sake of this please assume the swap is done correctly.

Thank you.

se

Answer 1

As to your trace: you are going wrong at point 2, because the if condition does not hold, so no recursive call is ever made.

If the recursion confuses you, it may help to rewrite into an iterative form:

static void moveOver (int A[], int U) {
  while (U > 0 && A[U-1] > A[U]) {
    /* Swap A[U], A[U-1] */
    --U;
  }
}

Now it's easy to see that the loop will stop as soon as a smaller element is encountered. For this to be a complete sorting algorithm, more work is needed. Either way, this is not insertion sort; it looks more like a partial bubble sort to me.

Now where did you say you got this code from?

Answer 2

I think the key to your mis-understanding of the problem is actually hidden in the title of your question

Needing help understanding insertion sort

The algorithm indeed only sorts the current element, but the idea is that its run every time an element is added to the array. That way each time its called the rest of the array is already in order. In other words you are only trying to sort into position that last element.

So using your example numbers (8, 2, 10, 5, 4, 12) and adding/sorting them into the array one at a time in order, the sequence would be as follows (the sorting at each step happens exactly how you already describe):

To be added         | old array      | after push     | Result (after moveOver())
(8, 2, 10, 5, 4, 12)| []             | [8]            | [8]
(2, 10, 5, 4, 12)   | [8]            | [8,2]          | [2,8]
(10, 5, 4, 12)      | [2,8]          | [2,8,10]       | [2,8,10]
(5, 4, 12)          | [2,8,10]       | [2,8,10,5]     | [2,5,8,10]
(4, 12)             | [2,5,8,10]     | [2,5,8,10,4]   | [2,4,5,8,10]
(12)                | [2,4,5,8,10]   | [2,4,5,8,10,12]| [2,4,5,8,10,12]