Zen and the Art of Motorcycle Maintenance (Part 6)

Read another 10 pages. Now starting Chapter 26.  This is indeed a difficult book to read.

Prisig suggested that one should unify both the subject and the object sides of quality together in a fundamental level.   I don't know how this could be done but I know when this feeling appears to me.

Have you written a merge sort in the past?   In the traditional top-down merge sort.  There are usually three pieces of code: the merge function, the merge_sort function and the driver of the program.

When I look at individual piece, they look fairly ugly before you understand what they do as a whole.

After I finally got it running (,search merge_sort in this blog for my attempts), the feelings are entirely different.   What a marvelous idea!  In fact there is even an easy proof of its performance.

Then I went back to each of the program.  Another feeling kicks in, wow, the program is indeed very smart.   For a typical C implementation, you just need to pass in a piece of working memory.  But the code does the magic.  Unsorted array becomes sorted.   How wonderful.

It is feeling like this keep us programmers working.  Not money, not reputation, not fame.   It is this beautiful feeling to get new things working make us keep on.

I guess we all have this feeling daily.  It just a matter of recognizing it consciously.

Ah. My merge sort and binary search in C are all wrong......

By Joshua Bloch found in http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html

This surprised me.  So apparently my code in merge sort and binary search are wrong then. 

coreutil's sort

It's based on merge sort.  In fact, to my surprise, sort can be used a merging tool!

btw, I took a look of GNU coreutil. Ah... suffice to say, my skill in unix programming needs to blush up badly.

Some TAOCP readings: merge sort, sequential search and my first MIXAL.

Among the three classic textbooks.  TAOCP is probably the most difficult to read.  The requirement on math is certainly an issue but I found the most difficult part is to understand MIX and MIXAL.  My honest reaction to MIX and MIXAL is - why would anyone use it? 

If I was going to write a book about programming, I would certainly used C or probably Intel Assembly language.   But after I understand the first MIX program, a sequential Search in Chapter 6, only 7 lines but it's already a wrestle for me,  I start to understand why Prof. Knuth would want to do things like that.  (See Listing 1)

      K EQU 10
      N EQU 10
    KEY EQU 200
   INFO EQU 210
START LDA 10
      ENT1 1-N
2H    CMPA KEY+N,1
      JE SUCCESS
      INC1 1
      J1NP 2B
FAILURE EQU *
SUCCESS LDA INFO+N,1
EXIT JMP *


The reason why MIX is used is to convince the reader that programming is independent of the choice of language.  So if the language is created within a book, one can still use it to analyze programs.   Their properties would just be exactly the same as written in any programming languages!

Of course, once you figure out the meaning of every line of the program and how it works.  You can start to see the beauty of it as well!

In a way, Prof. Knuth is like the Tolkien in C.S. He create a new language within his book which is quite an epic like The Lord of the Rings.

* 5.2.4 is a mysterious to me.
* 6.1 opens my eyes.   I have no idea there are so much to think about in sequential search.  I should implement linear search as part of practice.

Sedgewick's Algorithms in C Chapter 8 (2nd read)

Read the 2nd time and I certainly grasp more.  I am surprised how much improvements can there be for even the simple merge sort with memory.  Time to rewrite the complementary list.

Merge sort 5(C)

Merge sort 5 : Good

My current version without extra insertion sort:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 20
void merge(int a[],int w[],int p, int m, int r)
{
  int i,j,k;
  i=p;
  j=m+1;
  k=p;
  while(i<=m&&j<=r)
    w[k++]=(a[i]<a[j])?a[i++]:a[j++];
  while(i<=m)
    w[k++]=a[i++];
  while(j<=r)
    w[k++]=a[j++];
}
void merge_sort(int a[],int w[],int p,int r)
{
  if(p<r){
    int m = (p+r)/2;
    merge_sort(a,w,p,m);
    merge_sort(a,w,m+1,r);
    merge(a,w,p,m,r);
    memmove(&a[p],&w[p],(r-p+1)*sizeof(int)/sizeof(char));
  }
}
int main(int c, char* v[])
{
  int A[N]={20,1,3,4,-1,5,7,9,-10,-20,6,9,10,0,9,100,-100,0,-11,77};
  int W[N];
  int i;
  merge_sort(A,W,0,N-1);
  for(i=0;i<N;i++)
    printf("%d ",A[i]);
  printf("\n");
  return 0;
}

Awesome! My first hand-crafted NLogN search!

Next:

-Put this into my practice from now on. 

-It's time to finish 2.3-2
-It would be fun to sort 1 M number and time.

Merge sort 4(C)

Merge Sort 4 : Failed.
Cause:
-Forget to define N
-Use the original memory space as the workspace. (Yikes!)

Merge sort 3 (C)

Merge Sort 3 : Failed. 
Cause: I have read Prof. Shene's source code before I implemented.  There are two major issues when I implemente it.

1, the index should be inclusive, so most of my checkings was wrong. 
2, just like the perl version.  The C version doesn't increase the index correctly. 

There are other issues:
1, In C, one needs to dereference the address before pass to function such as memmove. 
2, I got the whole assignment code wrong in merging. 

With some debugging, of course this kind of issues can be easily identified and resolved.  But it means I am not yet good enough in this move.

Merge sort from Prof Shene's book

One of a less well-known book by Prof Ching-Kuang Shene is 名題精選百則：技巧篇.  It is presented in C (my favorite) and most of the code are neat.

For example, I found the merge sort in the book is probably the clearest for a merge sort requires an extra memory.   That's probably become the merge sort I will write in future.

Merge sort 2 (perl)

I finally wrote my first merge sort.  Even in perl, it requires heavy debugging.  I think this is ok.  Mergesort is significantly more involved than insertion and selection sort.

Here is the summary of what I did wrong in the perl version:
Major problems
-I didn't think through the right termination condition for the merge_sort.
-index was wrong while merging.

Minor problems:
-In perl, declaration of arrays using my, need to be done line-by-line. (Is it true?)

In any case, I think I am ready to write the C version.  In fact, I could assume I only need one more working memory with size N.  That is not tough.   Mr Ching-Kuang Shene's book should give a very good example. I think the more important issue is to think through different variants of merge sort.   That is not easy at all. It's also time to finish 2.3-2.

Sedgewick's Algorithm in C Chapter 8

I just got a copy of Sedgewick's Algorithms (in C) and I certainly feel very excited about this.

The first thing I looked at is insertion sort.  It covers sentinel in insertion sort and it gives pretty good discussion on its pros and cons.  I love it.

Then I looked at merge sort,  I feel very blurry about the details of it.  Merge sort is not covered deeply in CLRS.  So there are things I don't fully grasp.

Sedgewick's Algorithm is well known to be deep in sorting but tends to have bugs in its C program.  It will probably take me some time to fully digest it.

Merge sort 1 (CLRS pseudocode)

Wrote the first CLRS pseudo.   After some thought, it is clear to me my first real implementation in merge sort should be in perl or python first.  Because writing in C will require me to get the memory allocation correct.   Technique exists to just use one working memory to solve the problem.  But they are certainly not the same as the style from CLRS.

Also read through 5.2.4 by DEK,  I don't thoroughly understand it.

Status at 20110425

* Finished 2.3-1.  It's trivial. 
* Also thought through 2.3-7, it's a cute question. It teaches a pattern. Whenever you got stuck at a problem, try to sort some of the data.
* Exercises 2.3-2 - 2.3-6 are all cute exercises which guide the reader through slightly advanced concept such as binary search as well as binary insertion tree. This makes one able to learn 5 sorting algorithms in this chapter.  Pretty neat indeed.
* It's also time to make merge sort to be one of my move. Pretty neat idea as well.

Browse Read: 200/1144
Exercises up to Section 2.3-2
Exercises which are finished but not on paper: 2.3-7, 6.1-7, 6.2-3 and 6.2-4.

Status at 20110422 (b)

I was able to break my reading block on heap sort.  Then I cruised through chapter 7 on quick sort and come to chapter 8.   I believe 6, 7, 8 are advanced topics which require good background in theory.  So reread is necessary.   There are topics which I feel blurry - that include priority queue and the analysis of quick sort.  Those are very important but not easy to fully understand.

I also reread the material about merge sort and Chapter 3 again.   Now I get them.  My mind just wasn't ready for them.  In fact, this is a very good book to own because once you finished Chapter 2 and drill it seriously.  You already know 4 basic comparison sorting algorithm by heart, one even has performance in theta(nlogn).

Browse Read: 200/1144
Exercises up to 2.2-3

33_P
(Correction: there are only 1144 pages in the 3rd edition.)