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 20110426c

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




My first selection sort in perl. Feels good.
33_P

30th writing of insertion sort (perl)

Got it right. Checking mentally is important.
33_P

23rd writing of insertion sort (perl)

Bad: The print was written within the loop. Not my intention.  The sorting is correct though.

33_P

4th writing of insertion sort

Preciseness is still a problem.  It turns out I wrote something like. (Assuming non-decreasing order)

Listing 1
1 for j = 2 to N
2     key = A[j]
3     i = j -1
4     while i > 0 and A[i] > key
5         A[i+1] = A[i]
6         A[i] = key
7         i = i -1

There's nothing wrong with this code but this is not strictly insertion sort.  At line 6, key is exchanged when shifting of the array to right. This is not necessary because we can do (as in TCRC)

Listing 2
1 for j = 2 to N
2     key = A[j]
3     i = j -1
4     while i > 0 and A[i] > key
5         A[i+1] = A[i]
6         i = i -1
7    A[i]= key

This reduces an extra operation in the inner loop.

I also rewrite the C and perl version of the insertion sort.   It is a breeze though it is still easy to make mistakes.   This type of exercise is great to be done routinely.

* Got to remind myself to refresh on Python and Java.   I hope that everytime I write an algorithm, I can think through in at least these 4 langauges.

33_P