Insertion Sort

September 7, 2011 at 7:03 pm | Posted in Hacking | 2 Comments
Tags: ,

I always had a hard time understanding algorithms, so I tried to understand them and failed to understand them. This cycle repeated for at least 2 years. I always wanted to have solid grounding in algorithms and data structures. After 3 years of working in Phonologies I finally got my head around many programming skills. With that experience in my bag and my frustration of failing everytime from last 2 years, I decided to give algorithms a super-hard try again. I decided I will go hard-headed into algorithms like a man who will eat, sleep, drink and cry algorithms and nothing else. Just dig seep and get my whole body dirty in the process of digging like a labour man. Took me a few months to find out a book that fits my mindset. Its written in a very simple and straighforward manner and even after that I felt a lot of difficulty in understanding first few chapters. And finally I am able to get my head around algorithms. Have read first three chapters and insetion sort is given as an example while selection sort is given an exercise which Iw as able to solve. Here is my take on Insertion Sort, on how I understood it:

This is Insertion Sort from Wikipedia which is similar to Cormen’s book:

for j = 1 to length(A)-1
     key = A[ j ]
      i = j - 1
     while i >= 0 and A [ i ] > key
         A[ i +1 ] = A[ i ]
         i = i -1
     A [i +1] = key

Felt too much confused with this, I tried to understand many times but never did. Did not find anyone explaining in the way I understand, hence I tried to use a C array of integers to understand and came up with this:

  1. Take A = {3,5,2} as array to apply Insertion Sort pseudo code
  2. first 3 lines: j = 1, key = 5, i = 0
  3. while loop will not execute as A[0] = 3 and 3 > 5 is not true A = {3,5,2}
  4. Last line: A = {3,5,2}
  5. Outer loop 2nd turn, first three lines: j = 2, key = 2 , i = 1
  6. After inner while loop, first round A = {3,2,5}, i = 0
  7. After inner while loop, second round A = {3,3,5}, i = -1
  8. Last line: {2,3,5}
  9. Outer Loop finishes array is sorted

I am not a child prodigy hence it took me 3 hours to come up with an array with right elements in place. I did 3 pages of paper work with wrong values and wrong indices before I got them right. (please add 5 more days where I tried really haaaaaaaard to understand from the book). Hard part was not understanding the example of playing cards. Cormen’s book uses playing cards example to show insertion sort (special thanks to the authors as that picture of a hand sorting cards really helped). Real life sorting of playing card is very easy, I have done it a thousand times without thinking. Translating that practical approach into pseudo code was the hard part.


Copyright © 2011 Arnuld Uttre, Village – Patti, P.O – Manakpur, Tehsil – Nangal, Distt. – Ropar, Punjab (INDIA)

Verbatim copying and distribution of this entire article are permitted worldwide, without royalty, in any medium, provided this notice, and the copyright notice, are preserved.

Advertisements

2 Comments »

RSS feed for comments on this post. TrackBack URI

  1. This is Chad from comp.lang.c here. C doesn’t array of integers. It only has an array of objects. You might want to correct that before the language lawyers come after you -).

    • > This is Chad from comp.lang.c here. C doesn’t
      > array of integers. It only has an array of objects.
      > You might want to correct that before the language
      > lawyers come after you -)

      From the standrard (draft ’89)

      * An array type describes a contiguously allocated set of objects with a particular member object type, called the element type. Array types are characterized by their element type and by the number of members of the array. An array type is said to be derived from its element type, and if its element type is T , the array type is sometimes called “array of T .” The construction of an array type from an element type is called “array type derivation.”

      Thanks to Nick Keighley


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

Blog at WordPress.com.
Entries and comments feeds.

%d bloggers like this: