Insertion Sort Understanding (Pseudocode)

Pseudocode of Insertion Sort.  Following TCRC convention,

for j = 2 to N
   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

33_P

Progress 20110331

Cursory Read: 42 pages of 1144.
Exercise up to 2-1.3

33_P

Chapter 2 (Read 1)

Finished Read 1 of Chapter 2's "Getting Started".  Hadn't done all the exercises except 2.1-1 and 2.1-2.  I greatly enjoyed the style.   The more important part is that I have immersed myself to think the algorithm through.   Now simple algorithm's pseudocode starts to float in my head automatically.

That feeling shouldn't be fuzzy in any parts. If you feel hesitant on some small detail, then the learning is bad. 

By itself Chapter 2 is also a good introduction to sorting as well because most of the analysis and exercises focus on sorting.  If all the exercises are done (including the sectionals and chapter-ends), then one would get a good feel of insertion, selection, merge and bubble sort.   Pretty good value for a chapter.

Feeling an algorithm is one thing, understanding an algorithm means you grok it - my definition of groking:

• You can write it in pseudo.
• You can write it in compilable and workable C, Java, Perl, Python, Assembly and Lisp without using a compiler.
• You understand the worst, the average and the best case analysis of the code. 
• You know all the standard variations, in the case of insertion, I need to know Shell. 
• You know the latest development, in the case of insertion, I need to know Library.
• You know the relationship of the algorithm with other algorithms.  To understand this relationship, it should be defined as the first 5 points above as well.
• You can propose a better algorithm than what are published.

With this definition, I got to admit I am a complete noob on sorting.

It's ok, it could be tough to be an expert on every algorithm.  I will use my usual approach : First read of the book can be shallow but always requires myself to finish all exercise before my read counts as real.

33_P

Progress 20110325

• Read and processed 26 pages out of 1144 pages of content, Chapter 1 was skipped.  Go straight to Chapter 2.
• I decided to immerse myself to think through an algorithm.  So even for simple algorithm like insertion-sort.  I will take my time and grok it.  I believe my weakness is that I don't really grok the algorithm before I used them.  Great programmers almost always grok the algorithm first.
• I want to face my weakness this time.

33_P

Started

For various reasons, I decided to improve my skills in algorithms and data structure.   My focus will be 3 sets of books.

1, Introduction to Algorithms 3rd Edition by TCRC.
2, The Art of Computer Programming.
3, Concrete Mathematics.

My initial goal is to read through 1 and use the other two as references.