Questions related to sorting

Nice. Finished the first question about sorting.  As expected, some questions trip me.   There are two reasons, 1 is that the implementation of the lecture could be different from mine.  So I need to study the algorithm a bit before I can decide.  Second is that some algorithm is intrinsically tricky to think through.  For example, quicksort and mergesort are two sorts which take some serious time to consider.

But oh well, this is nice because it gives me some insight to some existing sorts which I thought I know (such as selection, insertion, bubble) and some new sort (such as quicksort and radixsort).

Insertion Sort 73 (Perl)

This is certainly one of those programming I did that for fun. I was just trying to get the shortest insertion sort in perl.  Obviously it's still too long compared to what I can find in stackoverflow.  (BTW, it's a great place to learn from good programmers.)

Insertion Sort 72 (Perl): Bad

@A=(-10,0,50,7,8,8,1,2,3);
for($j=1;$j<scalar(@A);$j++){
    ($k,$i)=($A[$j],$j-1);
    ($A[$i+1],$i)=($A[$i],$i-1) while($i>=0&&$A[$i]>$k);
    $A[$i+1]=$k;
}
printf("%s\n",join(" ",@A));

Here is a 72 chars from stackoverflow

sub i{my$m;$_[$_]<$_[$m]&&($m=$_)for 1..$#_;(splice(@_,$m,1),@_?i@_:@_)}

Daily Practice 20110504

Insertion Sort 63 (C): Good

Insertion Sort w Sentinel 3 (C): Good

Selection Sort 25 (C): Good

 

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

Daily Practice 20110430

Insertion Sort 58: Good

Selection Sort 22: Good

Insertion sort challenge - the shortest insertion sort program (from Stackoveflow)

That just makes me want to learn Golfscript

http://stackoverflow.com/questions/1712606/insertion-sort-code-challenge

Daily Practice 20110429

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

Why I fail so easily in my perl one-liner insertion sort?

I guess part of it is that the program is complicated and takes simplification.

For instance, one can reduce the two assignments in the outer loop to

$k=$A[$j]; 

$i=$j-1;

to ($k,$i)=($A[$j],$j-1);

and

$A[$i+1]=$A[$i];

$i--;

to ($A[$i+1],$i)=($A[$i],$i-1);

Also the while loop should be gone because it is always the loop require more inspection adn error checking.
This should shorten the loop and reduce the chance of error.

In the case of perl, it also seems to be a good idea to have less $ in the program.  Got to think about it.

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(b)

Insertion sort 48 - 51 (python) : only 51 is good.  48: I don't even know the syntax. 49: syntax error, there is no i-- in python.  50, I don't realize the python use 0-based array!
Selection sort 17-19 (python) : only 19 is good.  17: don't realize python has zero-based array. 18: can't remember the cause.

It's good to exercise in unfamiliar language.  Python's code is significantly shorter than perl and C even in simple programs such as insertion and selection sorts.

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

Daily Practice 20110426c

Insertion sort 42 (Perl): GoodSelection sort 15 (Perl): Good




My first selection sort in perl. Feels good.
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

insertion sort with sentinels

Found two papers (wow.) on insertion sort with sentinels.
Using Sentinels In Insert Sort (1989) by Harold Thimbleby


Also An improved insert sort algorithm

Also Jon Bentley's method of insertion sort actually reduce one subtraction in the outside loop of straight insertion sort without sentinels.   Ah ,where is my "Programming Pearl"?   Who doesn't want to exhaust the topic as simple as insertion sort?

33_P

Daily Practice 20110426(b)

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

TAOCP Vol 3 (5.2.1 and 5.2.3)

I reread the two sections about insertion sort and selection sort in TAOCP.  Those are two very good sections on this seeminly simple subject.  In fact, I should regard I understand these broad types of sorting technique *after* I finished the exercises in TAOCP first.

One thing I learn is that insertion sort's performance is actually related the average number of inversion in a sequence.  This gives a better insight than the standard probablistic arguments.

Very interesting.  There are just so many things I don't know even in "simple" matters.

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