Daily Practice 20110504

Insertion Sort 63 (C): Good

Insertion Sort w Sentinel 3 (C): Good

Selection Sort 25 (C): Good

 

Updated complementary exercises of sorting for CLRS 20110503

Insertion sort:
-sentinel version of straight insertion sort (done)
-different ways to avoid -INT_MAX as the sentinel. (state of art?)
-binary search
-binary insertion sort
-recursive version of insertion sort
-non-adaptive version of insertion sort.
-shell sort
-library sort
-tree sort(?)
-TAOCP Exercise in 5.2.1
-Sedgewick 6.3
-Sedgewick 6.3 Exercise


Selection sort:
-stable version of selection sort.
-bidirectional version of selection sort.
-comparison with insertion sort.
-comparison with bubble sort
-recursive version of insertion sort
-cycle sort
-heap sort variants
     -tournament sort
     -smoothsort.
-TAOCP Exercise in 5.2.3
-Sedgewick 6.2
-Sedgewick 6.2 Exercise


Merge sort:
-perl
-in place
-no extra memory implementation (state of art?)
-TAOCP Exercise in 5.4
-Sedgewick 8
-Sedgewick 8 Exercise.

Separating variants of insertion sort

I decided to put insertion sort with sentinels as part of the daily practice.  If I want to, I might merge them later on.  Right now, just practice on insertion and selection are too boring.

Insertion sort with sentinels 1 and 2

Insertion sort w sentinel 1 : Bad

Insertion sort w sentinel 2 : Good

1 was wrong because I misspelled INT_MAX and used MAX_INT instead. Shame. I looked that up before I started.

This is the implementation which I settled on 2. In practice, having a sentinel could really be hard. 

#include <stdio.h>
#include <limits.h>
#define N 11
int main (int c, char *v[])
{
  int A[N] = { -INT_MAX,10,1,7,4,3,12,8,9,6,0};
  int i,j,k;
  for(j=1;j<N;j++){
    k=A[j];
    i=j-1;
    while(A[i]>k)
      A[i+1]=A[i--];
    A[i+1]=k;
  }
  for(i=1;i<N;i++)
    printf("%d ",A[i]);
  printf("\n");
  return 0;
}

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.

Daily Practice 20110503

Insertion Sort 61: Bad

Insertion Sort 62: Good

Selection Sort 24: Good

 

Though mentally fixed a bug in the selection sort.  I skipped a parsing error in insertion sort 61 --  Certainly not in the flow.  Feeling frustrated for various things in life. 

 

This is boredom.  In one way I should start at least one thing new today because it's hard to do something routine and hope that boredom doesn't kill me. 

 

I also want to remember how long I can keep writing correct code.  That gives an idea how long my concentration can hold.

Daily Practice 20110502

Insertion Sort 60: Good

Selection Sort 23: Good