Binary insertion sort 1 (CLRS pseudocode)

Just sketch up a version of binary insertion sort.  It is an unstable version but it's quite easy to change it to be stable.



I have fun on this because it makes use of several technique I learned recently. (insertion sort and binary search).

Binary insertion sort 1 (CLRS pseudocode)

Just sketch up a version of binary insertion sort.  It is an unstable version but it's quite easy to change it to be stable.



I have fun on this because it makes use of several technique I learned recently. (insertion sort and binary search).

Binary insertion sort 1 (CLRS pseudocode) , 2(C) and 3(C)

Binary insertion sort 1 (CLRS ):  bad

Binary insertion sort 2 (C): bad

Binary insertion sort 3 (C): bad

After knowing the binary insertion sort from Programming Pearl.  I worked out ex. 2.3-5 and give a simple description of binary insertion sort.   Easy enough.  

Though when I first implement a binary insertion sort - I did that for fun - I stumbled upon how to get it correct - a normal insertion sort would only give you whether the searched value is located in the array or not.   It doesn't automatically tell you where the search value located within the array.    This makes me realize my first version was incorrect.

So a simple plug-in of the iterative version of binary search within an insertion sort doesn't automatically work.   

Luckily, this is not a tough problem, if you are using a version of binary search which always use exclusive bound, i.e. the one which always exclude the mid point.  Then in the case when the search fails, the searched value would be in between lo and lo+1.  So, you just need to do a shift from lo to j+1, then your job is done.  

What about the mid point and the key is the same then? If stability is not a concern, you can simply insert the item right after the mid point.  If stability is a concern, then you can look backward to see if there are same value from the mid point. 

Why is it the case?  Well, first observe that, when there are only 1 items left in the range, we can only have l=r. In the first case, if A[m]=A[l]<key or A[m]=A[l]=key, then both insertion points would be l. (i.e. we will insert after l).  Just a logical check, can A[m]> key? Impossible, because previous search step would make the range to be the left of l.

This is all logical.  So my first implementation looks like

     1    #include <stdio.h>
     2    #define N 20
     3    int main(int c, char *v[])
     4    {
     5      int A[N]={10,7,8,3,2,1,8,12,14,15,
     6                17,8,9,11,13,7,8,12,14,5};
     7      int i,j,k,l,h,m;
     8      for(j=1;j<N;j++){
     9        k=A[j];
    10        h=j-1;
    11        l=0;
    12        while(l<=h){
    13          m = l + (h-l)/2;
    14          if(k<A[m]){
    15            h=m-1;
    16            i = l;
    17          }
    18          else if(k==A[m]){
    19            i = m;
    20            break;
    21          }
    22          else {/* k> A[m]*/
    23            l=m+1;
    24            i = l;
    25          }
    26        }
    27        m=j-1;
    28        while (m>=i)
    29          A[m+1]=A[m--];
    30        A[m+1]=k;
    31      }
    32      for(i=0;i<N;i++)
    33        printf("%d ",A[i]);
    34      printf("\n");
    35      return 0;
    36    }

This becomes my binary insertion sort 2.  I feel confident and tell myself that this search is likely to be correct (humble, humble).

But it's obvious that the binary search part can be shorter.  So here's another possibility.  if in the last iteration, both cases for A[m]>key and A[m]=key give us the insertion point = l.  Can we just collapse these two cases?  As it turned out, one can do it.  Because in iterations other than the last, when A[m]=key, you can just keep on searching.  So here comes another implementation, 

     1    #include <stdio.h>
     2    #define N 20
     3    int main(int c, char *v[])
     4    {
     5      int A[N]={10,7,8,3,2,1,8,12,14,15,
     6                17,8,9,11,13,7,8,12,14,5};
     7      int j,k,l,h,m;
     8      for(j=1;j<N;j++){
     9        k=A[j];
    10        h=j-1;
    11        l=0;
    12        while(l<=h){
    13          m = l + (h-l)/2;
    14          if(k<=A[m])
    15            h=m-1;
    16          else /* k> A[m]*/
    17            l=m+1;
    18        }
    19        m=j-1;
    20        while (m>=l)
    21          A[m+1]=A[m--];
    22        A[m+1]=k;
    23      }
    24      for(j=0;j<N;j++)
    25        printf("%d ",A[j]);
    26      printf("\n");
    27      return 0;
    28    }

This is a shorter program. Not everything is cleaned up. Logical argument makes me believe that the program is correct. 

I stopped at this point, fully aware that this algorithm is unstable (Consider sequence with numbers to be all the same), if one really wants it to be stable, you might just search it leftward.  There is another disadvantage - the search now always run lgN+1 iteration.

So BIS3 is unlikely my final binary insertion search.  Given I am hungry though, I will let it go for today

33_P

The Art of Computer Programming by Knuth

Trying to restock all books in my house.   I finally get back my 3 volumes of "The Art of Computer Programming".   How I am fascinated by it!   Even simple as insertion, there is a lot of things I don't know!

And how much I want to know about random generator! How much I want to know about selection!

At this point I just treat it as a reference.  But one day I will read it like a book.

33_P

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.

Practice in insertion sort

After some drilling and practice (33 times so far) of the basic insertion sort on pseudocode, c, perl and python.  I start to feel mildly comfortable with the algorithm.  This kind of exercises are very useful.  In fact, looking back, a deep understanding of one single algorithm, even if it is very simple, seems to sharpen my mind more than browsing thousands of algorithms.  It tends to expose holes in your mind.

It is some progress, I will follow my own goal on each algorithm.   To grok the algorithm : That is to think through it, to write the correct program without the need of compiler/interpreter, to understand it fully theoretically and to know all known extensions of it.

Of course, at the end of the day, if I can propose a better one, I will be ultimately satisfied.

For insertion sort, I am still far far away.  The next thing I plan to do are
1, Learn the basic variations of insertion sort.
2, Do the same practice on selection sort.
3, Do the same practice of linear search.

1 is trivial.  In C, there are around 3 possible code variations floating around on the web just for straight insertion sort. Each of them has their merit.  One important variation is the sentinel version.  It is known to be faster. (Why?)

It's also important to understand the some more advanced version of insertion sort, such as binary insertion sort, shell sort and the new kid, library sort.  Those..... by themselves should be treated with respect and need to be practiced separately.  More on those later. But part of the reason I will do 3 is because it will be the bridge of doing binary search.   It will be two foundations before I start to do a binary insertion sort.

33_P