Thursday, 30 December 2010

Insertion sort


Think of arranging cards for a rummy match. The cards are distributed evenly among players and each players arranges the card sequentially from a pile of card by hand.

You pick the first card and consider it as sorted.

Next, you pick another card and insert it in right position. Similarly u continue inserting the cards. Note that, mostly you take the top most card from the pile in every pick.


Implement the above methodology for sorting numbers.

So, you have,

  • List of numbers fully in random order
  • pick the first number by default
  • take the second number and check where it lies with the first number
  • now, the first 2 numbers in the list are sorted
  • continue till the end of the list and always create a sorted list in each iteration


Algorithm:

You can refer the pseudo code from "Introduction to Algorithms - By Cormen, Rivest". Just jotting down my understanding on the on-place algorithm given on the book.

Important points:

* When you sort a list on-place without using extra space, you should create a hole so that numbers can be shifted. So, store the number you pick from unsorted list in a temporary variable and use that as a hole to shift.


* MOST IMPORTANT PROPERTY OF INSERTION SORT, on each iteration you get the numbers sorted at one side of the list.  that is, in 1st iteration, first 2 numbers in the list will be sorted,
          2nd, first 3 numbers will be sorted
          3rd, first 4 numbers will be sorted

  So, if you just want partially sorted list(that is only 1/2 list is required), you can stop at the required point.


* Note that the above tells that, every iteration creates a sorted list always. This is the invariant condition. An INVARIANT is an assertion that doesn't change in executing a piece of code.  A LOOP INVARIANT is something that holds at the beginning of a loop, and continues to hold after each iteration. Usually, an invariant is used to prove correctness of algorithm


* We need 2 loops, one for taking a number from the list(j). another is for inserting the number at the right position by rearranging (i)

* “i” will run in reverse (exits when it becomes zero) and reorders the array to insert the element at right position.


* “i” will be set to the “j” as “j” will be always the end of the sorted list after every iteration.


Code

   1:  void insertion_sort(int *arr, int n)
   2:  {
   3:      for(int j=1; j<n;j++)
   4:      {
   5:          int key = arr[j];
   6:          int i=j-1;
   7:          while(i>=0) {
   8:              if(arr[i] < key)
   9:              {
  10:                  arr[i+1] = arr[i];
  11:                  i = i - 1;
  12:              }
  13:              else
  14:                  break;
  15:          }
  16:          arr[i+1] = key;
  17:      }
  18:  }
  19:   
  20:  void main()
  21:  {
  22:      int test_arr[] = {5,3,2,6,8,9};
  23:      insertion_sort(test_arr, 6);
  24:  }

Exercise problems from the book:
- Linear search problem - find the loop invariant and prove the algorithm

<http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15211/fall.97/www/lectures/lect0916>