10.3 Insertion Sort

In order to use a binary search you need to have the items sorted. Insertion sort is the first of several different methods we will look at. You start by looking at the first two items. If they aren't in order swap them. Now look at the third item. Find the location where the third one should go amongst the first three and swap if not in its correct location. Keep doing this with gradually longer sets of items until you've done all the data. Now the items are in order. Here is an applet to demonstrate this.

Example

This applet demonstrates how an insertion sort works.

Notice how many items of data need to move each time one item is inserted. The farther to the left the item is inserted the more items need to move right to get out of the way.

Now let's look at the code to implement this sort: 

public static void insertSort (double[] list)
{
   for (int top = 1; top < list.length; top++)
   {
      double item = list[top];
      int i;
      for (i = top; i > 0 && item < list[i - 1]; i--)
         list[i] = list[i - 1];
      list[i] = item;
   }
}

Try tracing through the code using a set of numbers from the above applet. It would get called in a fragment like this:

double[] nums = new double[10];
// fill the array with your unsorted numbers
insertSort(nums);