#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 youINSERTall 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