Sliding Things Over

Next on the list of sorts is the insertion sort. Where the selection sort picked one spot and found the lowest value to place there, the insertion sort looks at a value and decides where it should go. Observe the following process.

   Assume that the first value is already "sorted"

   place the next letter into a temporary variable

   if the next letter is less than the first one 
      {
       move the first letter up and insert the second one in its place
      }

   go to the next letter in the list, and place it in a temporary variable

   compare it to all the letters below it, and see where it fits

   move each of the lower letters up as needed,
       and insert the next letter into the proper place

Consider the following example.

The letter in the first slot (i.e., index zero) is assumed to be sorted. This is like the selection sort in that the left side list (i.e., left if the working index as it moves through the list) is sorted and the right side list is not.

Next, the value of index one (i.e., letter 'd') is compared to 'j'. Since 'd' is less than 'j', the 'j' is moved up one slot, which happens to be in the location where 'd' was, and then the 'd' is placed in the index zero slot.

Obviously, since the element where the letter to be inserted resides may be overwritten, the value of the "to be inserted" element must be temporarily stored in an outside variable during the testing and shifting process. The results are shown here.

Consider the next step. The letter 'm' in element two is placed in the temporary variable, and then compared to the 'j' in element one. Since 'm' is greater than 'j', the 'm' is inserted at element two, which happens to be where it had come from.

In the programming code, this step can be eliminated if the element is to be inserted back in its own slot, but the efficiency is not improved, so it is little worth it.

The next operation is a little more interesting. The item in element three is the next value to be inserted. The letter 'k' is stored in a temporary variable, and then compared to element two. Since element two contains the letter 'm', which is greater than 'k', the letter 'm' is moved into slot three, as shown here.

Then the letter 'k' is compared to the letter 'j' in element one. Since it is greater than the letter 'j', the letter 'k' is inserted in element two, as shown here.

Finally, the letter 'b' is placed in a temporary variable, and starts its trip down the list to find its spot. Follow the graphical process below to observe the process.

The letter 'b' searches for a letter lower than itself, or the bottom of the list, whichever comes first.

All the letters are moved up one slot so that the letter 'b' can be placed into the first element. The array would finish in a sorted state, as shown here.

This operation could have been implemented by swapping the letter 'b' down to its location, but that would cost quite a bit more overhead. As mentioned before, the letter is held in a separate variable while the other letters are assigned up by one and it searches for the right spot in which to be inserted.

As mentioned in the earlier loop chapter, there are many times that simply using your functional abstraction is a whole lot easier than trying to manage complex nested loops.

You still have to handle nested loops, but wherever programming can be made more safe with another function, it is a better choice.

The code for the outer loop is as follows. The process will start with listIndex at one since the first item at index zero is assumed to be "sorted" to begin with. The loop iterates with listIndex increasing by one after the letter at that index has found the slot in which it is to be inserted. Here is the code.

   /*
   Name: runInsertionSort
   Process: sorts characters using the selection sort strategy;
            array returns data via return statement
   Function input/parameters: characters in array (char[]), array size (int)
   Function output/parameters: none
   Function output/returned: sorted characters in array (char *)
   Device input/keyboard: none
   Device output/monitor: none
   Dependencies: loadArray, swapCharsByIndex
   */
   char *runInsertionSort( const char *letters, int arraySize )
      {
       // initialize function/variables
       char *localArray = (char *)malloc( arraySize * sizeof( char ) );
       int searchIndex, listIndex = 1;
       char tempChar;

       // load local array with data from parameter array
          // function:loadArray
       loadArray( localArray, letters, arraySize );

       // loop across entire array starting at element two
       while( listIndex < arraySize )
          {
           // store test character found at listIndex given by outer loop
           tempChar = localArray[ listIndex ];

           // start at index given by outer loop
           searchIndex = listIndex;

           // loop while not at bottom, and while the test character
           // is less than the item in the slot below
           while( searchIndex > 0
                       && tempChar < localArray[ searchIndex - 1 ] )
              {
               // copy the item below to the present index
               localArray[ searchIndex ]
                                    = localArray[ searchIndex - 1 ];

               // decrement the search index
               searchIndex--;
              }
        // end insertion loop

        // insert the character
        localArray[ searchIndex ] = tempChar;

        // increment the list loop index
        listIndex++;
       }
    // end list loop

    // return sorted array
    return localArray;
   }

The code for the insertion process is a little more complicated, but once again it should be somewhat intuitive once you understand the algorithm. This function also demonstrates the use of the const keyword in the parameter list to protect the incoming array from being modified, as was demonstrated in a previous section. Inside the function, a different array is created and returned to the calling function with the return quantity char * as opposed to allowing the array to be returned as a parameter.

Notice the while loop operation. The searchIndex is tested first to make sure it is not already below the bottom of the list. If you recall from the earlier chapter, if this test fails, there will be no test for list[ searchIndex ] > item, thanks to the short circuiting process. This is a safety mechanism so that the loop and the test can be combined without accidentally trying to test the list array outside its boundaries (i.e., below index zero).

If the while decision shows that the search process has not made it to the bottom of the list, and the item being tested one slot below is still larger than the item being inserted, then the loop is iterated, the item being tested is moved up (assigned) to the next element above itself, and the search is repeated. Once the loop either hits the bottom of the list or identifies the correct spot to place the item, then the loop stops.

The outer (list) loop then takes the process to the next item in the list, which again searches its way down the list until it finds a location in which to be inserted, or the bottom of the list if a location is not found. As you can see, while the selection sort was a little like card players finding cards and putting them into a certain order, the insertion sort can be even more like the card player getting a new card, starting at the high end, and working her way down the cards until she finds where it fits, and then inserting it in its appropriate location.

As before, you can watch this video to see an animation of this process. And as before, it provides several opportunities to learn about tracing code, and really coming to understand how array management works. As stated previously, it is not a goal for you to learn these sorting algorithms, although they are kind of fun, your primary learning goal at this point should be to understand how to effectively manipulate an array.

This is the last of the sorting topics, but there is one searching topic that will be provided in the next topic. Again, it will give you even more opportunity to learn how to read active code, and modify and maintain it.