Skip navigation

#include <stdio.h>

void p( int a[], int len )
{
  for( int i = 0; i < len - 1; i++ )
    printf( "%d, ", a[i] ) ;
  printf( "%d\n", a[ len - 1 ] ) ;
}


int main()
{
  int a[] = { 5, 9, 1, 22, 6, 7, 7, 90 } ;
  int len = sizeof( a ) / sizeof( int ) ;  // *note:
  // sizeof() doesn't work for pointer (int * a) style arrays 

  p( a, len ) ;

  // The insertion sort algorithm is here, and
  // every line is explained in comments.

  // UNDERSTANDING INSERTION SORT
  // The best analogy for understanding insertion
  // sort is if you think of holding a hand of cards.

  // Say you have this hand:
  // 7, 2, 5, 8 

  // Now you like to see things in order, so you
  // want them to have the order 2, 5, 7, 8.  What's
  // the easiest way to order the cards without
  // putting them down flat on the table?

  // You'd probably do this.  Start at the
  // very left hand side.  Skip the first card,
  // and PULL OUT the second card
  // so now you're looking at the 2.

  // In left hand:  7, ___,  5, 8
  // In right hand:  2

  // (the empty space is where the 2 WAS)

  // FROM the place where the 2 WAS,
  // work backwards until
  // you find where that 2 "SHOULD GO"
  // in the GREEN ("already sorted") section.

  // Clearly the 2 should go in front of the 7.

  // Thinking like a computer...

  // To make the 2 go in front of the 7, we have
  // to SLIDE the 7 over to occupy the space
  // where the 2 WAS:

  // In left hand:  ___, 7,  5, 8
  // In right hand:  2

  // Now we can insert the 2 into that blank spot:

  // In left hand:  2, 7,   5, 8
  // In right hand:  ___

  // You just keep going
  // until you INSERT all the cards from the
  // UNSORTED section
  // into their correct positions in the SORTED section

  // Next step:  We're on the 5.
  
  // Pull it out.

  // In left hand:  2, 7, ___  8
  // In right hand:  5

  // WORK BACKWARDS FROM the ___ spot.

  // AS WE STEP BACKWARDS,
  // we are looking for an entry in
  // the already sorted section that
  // is SMALLER than the number
  // we have plucked out in our right hand
  // (the 5 in this case)

  // In left hand:  2, 7, ___  8
  // ** NO, 7 is not SMALLER than 5.
  // So we simply siddle the 7 up

  // In left hand:  2, ___, 7  8
  // ** YES, 2 is smaller than 5, so
  // our 5 will belong right after the
  // 2 (where the blank space happens
  // to be right now!!)

  // We simply insert the 5 here,
  // and we are done with the 5.
  // In left hand:  2, 5, 7  8

  // last step:  remove the 8:

  // In left hand:  2, 5, 7, ___

  // Start by looking at the 7.  7
  // is less than 8, so the 8 goes
  // in after the 7 (where it was
  // basically)

  // In left hand:  2, 5, 7, 8

  // And that's the algorithm.

  // NOTICE the method you use.  At every card
  // you attempt to sort, you count BACKWARDS
  // from the place you pulled it out from,
  // until you find a number that is SMALLER
  // than the card you are trying to insert.


  //////////////
  // THE C CODE: 

  // the outer for loop.  the outer loop walks us
  // THRU the array, FORWARDS, ONCE.

  // In this SINGLE PASS through the array
  // we are sorting, at EVERY number we hit
  // we will STOP, look back through the
  // beginning part of the list, and put that
  // number WHERE IT BELONGS.

  for( int j = 1;  // start at the SECOND element of the list
       j < len ;   // go until the end of the list
       j++ )       // one at a time.
  {
    // { 5, 9, 1, 22, 6, 7, 7, 90 } ;
    //     ^^^
    //    ( START HERE, not at the very beginning )
    
    // Now, at EACH number you're at
    // first, we must SAVE IT OFF.

    // Reason:  Its going to be overwritten.
    int KEY = a[ j ] ;

    // This is equivalent to "pulling
    // the card out" in the explanation above.

    // Next, we walk BACKWARDS through
    // the array, STARTING at the position
    // JUST BEFORE the card we "pulled out"

    int i ;
    for( i = j - 1 ;  // start at position JUST BEFORE item we pulled out
         i >= 0 ;     // we'll walk down until the VERY BEGINNING of the list
         // ** UNLESS WE FIND A NUMBER IN THE LIST
         // THAT IS SMALLER THAN KEY (in which case
         // we will BREAK out of this loop)

         i-- )        // we're walking backwards thru the list
    {
      // Now, we are LOOKING FOR
      // a number in a[] that is
      // SMALLER than the KEY we
      // have in our hand.

      // Once we find a number that
      // is SMALLER than the KEY,
      // we will know where to
      // insert the KEY (right
      // after THAT number which is
      // smaller than the KEY.)

      // Notice how this assumes that
      // everything to the left of the KEY
      // IS ALREADY SORTED (which it will be
      // as this algorithm works through
      // the list).
      if( a[ i ] < KEY )
      {
        // Found spot for KEY.  Stop "siddling"
        // (see ELSE statement below for "siddle").

        break;
      }
      else
      {
        // siddle.  copy element over.
        
        a[ i + 1 ] = a[ i ] ;

        // on the first iteration, this
        // operation will overwrite the KEY
        // in the array (hence the need to
        // save it off in a separate variable).
      }
    }

    // Insert the key.
    a[ i + 1 ] = KEY ;
  }

  p( a, len ) ;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: