Tcl 2002 programming contest: solutions to problem 1

The solutions submitted to problem 1 gave a clear illustration of how little understanding there is of Tcl performance in the Tcl community. The following table gives the relative times needed for a number of different implementations:

    Proc containing [lsort]      1.00    - This approach was forbidden
                                           by the contest rules

    Fastest answer known to      1.39
    the contest judges

    Fastest answer submitted     2.63    - As submitted, had a bug
                                           (see below)

    Winning answer               4.81

    Slowest answer submitted    15.07

As you can see, even with highly motivated and presumably expert Tcl'ers, the speed of execution of a Tcl procedure to solve a given problem can vary by an order of magnitude.

Mac Cody submitted the winning answer (shown here slightly reformatted):

 proc sort5 {list} {
   foreach i $list {
      if {[info exists l2]} {
         set cntr 0
         while {[lindex $i 0] >= [lindex [lindex $l2 $cntr] 0] 
                && $cntr < [llength $l2]} {
            incr cntr
         }            
         set l2 [linsert $l2 $cntr $i]
      } else {
         lappend l2 $i
      }
   }
   return $l2
 }

It's essentially an insertion sort, with the return value maintained in a separate list.

The fastest submission in terms of raw speed was Roy Nurmi's elegant code:

 # Bubble sort, optimized for 5 elements
 #
 proc sort5 {l} {
  foreach {i j} {0 1 0 2 0 3 0 4  1 2 1 3 1 4  2 3 2 4  3 4} {
    if {[string compare [lindex $l $i 0] [lindex $l $j 0]] > 0} {
      set t [lindex $l $i]
      lset l $i [lindex $l $j]
      lset l $j $t
    }
  }
  return $l
 }

It does a classical sort like the ones seen in any introductory programming text: one interesting bit is that the nested [for] loops that one would normally see:

   for { set i 0 } { $i < 4 } { incr i } {
       for { set j [expr { $i + 1 }] } { $j < 5 } { incr j } {
           ...
       }
   }

are replaced with a single [foreach].

Unfortunately, as submitted, the solution has a bug: the problem statement called for a stable sort, and the procedure above can change the order of equal elements in the original list.

When the judges were examining the solution, however, they noticed that while the comment said that the algorithm was a bubble sort, the code implemented a selection sort. Suddenly, there was an insight that simply changing the indices on the [foreach] statement would change the selection sort to a bubble sort - and make it stable. The slightly changed procedure,

 # Bubble sort, optimized for 5 elements
 #
 proc sort5 {l} {
  foreach {i j} {0 1 1 2 2 3 3 4  0 1 1 2 2 3  0 1 1 2  0 1 } {
    if {[string compare [lindex $l $i 0] [lindex $l $j 0]] > 0} {
      set t [lindex $l $i]
      lset l $i [lindex $l $j]
      lset l $j $t
    }
  }
  return $l
 }

passed all the tests, and took the same running time as Roy's original.

In preparing for the contest, one of the judges (KBK) began with a solution very like Roy's, and then decided to work on improving it still further. His page poses the question, How fast can we sort 5 elements?

Tcl2002 programming contest: problem 1

The Great Canadian Tcl/Tk Programming contest, eh?