DN625817031

Subject: "Good" implementation of bubble sort in Tcl? - DN [1]

"Rolf Lochb hler" <rolf@weitewelt.net> - 21 May 2000 - comp.lang.tcl

 Hi there!

 Trying to learn Tcl, I implemented a simple integer bubble sort in
 Tcl in two versions: (1) sorting an array, and (2) sorting a list.

 Below is what I came up with so far. Both versions work, although
 sorting a list seems to be slower than sorting an array.

 (Yes, I know there is a lsort function that of course would do the
 job much faster...)

 I'm wondering if there is anything a good Tcl coder would/should
 write differently to improve the execution speed... (besides not
 using bubble sort, of course)

 Any hints are very much appreciated.

 And here are my two implementations. The unsorted input data is in
 a file (one integer per line) that is specified as a command line
 argument, the output data is to be written into a file named
 "out".

 First the array sort...

 -(1)---------
 set inFile [open $argv r]
 set i -1
 while {![eof $inFile]} {
   incr i
   gets $inFile x($i)
 }
 set N $i
 close $inFile

 for {set limit [expr $N - 1]} {$limit > 0} {incr limit -1} {
   set sorted 1
   for {set i 0} {$i < $limit} {incr i} {
     set k [expr $i + 1]
     if {$x($i) > $x($k)} {
       set temp $x($k)
       set x($k) $x($i)
       set x($i) $temp
       set sorted 0
     }
   }
   if {$sorted} {break}
 }

 set outFile [open out w]
 for {set i 0} {$i < $N} {incr i} {
   puts $outFile $x($i)
 }
 close $outFile

 exit
 -(1)---------

 Second, the list sort...

 -(2)---------
 set inFile [open $argv r]
 set i -1
 set x ""
 while {![eof $inFile]} {
   incr i
   set x [concat $x [gets $inFile]]
 }
 set N $i
 close $inFile

 for {set limit [expr $N - 1]} {$limit > 0} {incr limit -1} {
   set sorted 1
   for {set i 0} {$i < $limit} {incr i} {
     set k [expr $i + 1]
     set xi [lindex $x $i]
     set xk [lindex $x $k]
     if {$xi > $xk} {
       set x [lreplace $x $i $k $xk $xi]
       set sorted 0
     }
   }
   if {$sorted} {break}
 }

 set outFile [open out w]
 for {set i 0} {$i < $N} {incr i} {
   puts $outFile [lindex $x $i]
 }
 close $outFile

 exit
 -(2)---------

 - Rolf

 --
 Rolf Lochb=FChler <rolf@weitewelt.net>
 Home page: http://www.weitewelt.net/