Daily Practice 20110504

Insertion Sort 63 (C): Good

Insertion Sort w Sentinel 3 (C): Good

Selection Sort 25 (C): Good

 

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

Daily Practice 20110430

Insertion Sort 58: Good

Selection Sort 22: Good

Insertion sort 56-57 (C)

They are all good.  My intention is test out characteristic of C. Listing 1 was the original algorithm.  Whereas Listing 2 and 3 are for insertion sort 56 and 57. I still find even when the for implementation is shortest, it is not as readable as the while implementation.  You can simply compare the C code with the pseudocode and realize that. 

I found listing 2 to be the best compromise.  It still keep the while-loop but shorten the program for 2 lines.  I will adopt it in my code from now on.

Listing 1:

  for(j=1;j<N;j++){

    k=A[j];
    i=j-1;
    while(i>=0&&A[i]>k){
      A[i+1]=A[i];
      i--;
    }
    A[i+1]=k;

  }

Listing 2: Insertion Sort 56

  for(j=1;j<N;j++){

    k=A[j];
    i=j-1;
    while(i>=0&&A[i]>k)

      A[i+1]=A[i--];
    A[i+1]=k;

  }

Listing 3: Insertion Sort 57

  for(j=1;j<N;j++){
    for(k=A[j],i=j-1;i>=0&&A[i]>k;A[i+1]=A[i--]);
    A[i+1]=k;
  }

Daily Practice 20110429

Insertion sort 55 (C): Good
Selection sort 21 (C): Good
33_P

53rd and 54th writing of insertion sort (CLRS pseudocode, C pseudocode) : insertion sort with sentinel

To deepen my understanding of insertion sort. I start to think through different variants of insertion sort.  The most trivial one is to use sentinel in the sort. 

In CLRS version, it looks like

1,  A[0] = -infinity

2,  for j = 1  to N

3,      key = A[j]

4,      i = j -1

5,      while A[i] > k

6,          A[i+1] = A[i]

7,          i = i - 1

8,      A[i+1] = k

I also wrote a C program on paper. So far looks good to me.  Of course, the compiler is still the final judge. 

Daily Practice 20110428

Insertion sort 52 (C): Good
Selection sort 20 (C): Good
33_P

Daily Practice 20110427(a)

Insertion sort 44 (C): Good
Selection sort 16 (C): Good


First time I got it right the first time.  Good. For another couple of days, I will start to add merge sort to my routine.
33_P

Expanded Further readings for insertion sort and selection sort

Further readings for insertion sort and selection sort

Insertion sort:
-sentinel version of straight insertion sort
-binary search
-binary insertion sort
-recursive version of insertion sort
-shell sort
-library sort
-tree sort(?)
-TAOCP Exercise in 5.2.1

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.23

Daily Practice 20110426(b)

Insertion sort 41 (C): Good
Selection sort 13 (C): Good
33_P

Daily Practice 20110426

Insertion sort 40 (C): Good
Selection sort 10,11,12 (C): 10 Bad, 11 Bad, 12 Good.  Why? 
10 used tmp rather than A in swapping - it's a good thing to always mind the variable you used.
11 used the assign A[j] to min instead of j.  The caused the whole program looks like it is working.  This is a subtle bug if the value of A is closed to sort.

My problem of selection sort is that I hadn't gone through the what if analysis of the whole algorithm.  I should try it some time.

33_P

Daily Practice 20110425

Insertion sort: 38th and 39th writings (C) : 38th - disaster, got syntax wrong for initializing an array and assigned a wrong variable to k.  Make it your habit to think the index order.  39th - get it right.

Selection sort: 8th writing and 9th writings (C) : 8th - wrong, change the sign of comparison.  So it sorts the other way.  9th is good.

Found myself not very focused today.

33_P

Daily Practice 20110424b

insertion sort: 38th and 39th writings in C :38th missed a ;, 39th is good.  At 11:35 p.m., I was feeling tired and certainly lost focus.  But this is good time to practice making myself focused.
selection sort: 7th writing in C: Good.

Each take around 3 mins.

33_P

Daily Practice 20110424

insertion sort: 37th writing in C : Good ~3mins.
selection sort : 5th and 6th writing in C : 5th is bad but 6th is good.  5th has issue because of swapping was slightly wrong.   Now I know a non-insertion sort error pattern in my head. ~5 mins.

I am taking approximately 3 mins in insertion sort and 5 mins in selection sort.  It is certainly something I can improve.   My first speed goal is to write them under 60 seconds.

33_P

36th writing of insertion sort(C)

Good.  33_P

35th writing of insertion sort

Good. 33_P

33rd writing of insertion sort (C)

Nailed it. Feel more natural.  It's better to time myself from now on.
33_P

27th writing of insertion sort (C)

Get it right.
33_P

26th writing of insertion sort (C)

Bad.  When I initialize the array, the elements mismatch. This is perhaps the first time I hit this problem.

33_P