Anonymous user
Sorting algorithms/Radix sort: Difference between revisions
→Tcl: Added implementation
m (whitespace) |
(→Tcl: Added implementation) |
||
Line 31:
The wikipedia article cited in the introduction includes a python implementation of LSB radix sort.
=={{header|Tcl}}==
{{trans|Python}}
<lang tcl>package require Tcl 8.5
proc splitByRadix {lst base power} {
# create a list of empty lists to hold the split by digit
set out [lrepeat $base {}]
foreach item $lst {
# pulls the selected digit
set digit [expr {($item / $base ** $power) % $base}]
# append the number to the list selected by the digit
lset out $digit [list {*}[lindex $out $digit] $item]
}
return $out
}
# largest abs value element of a list
proc tcl::mathfunc::maxabs {lst} {
set max [abs [lindex $lst 0]]
for {set i 1} {$i < [llength $lst]} {incr i} {
set v [abs [lindex $lst $i]]
if {$max < $v} {set max $v}
}
return $max
}
proc radixSort {lst {base 10}} {
# there are as many passes as there are digits in the longest number
set passes [expr {int(log(maxabs($lst))/log($base) + 1)}]
# For each pass...
for {set pass 0} {$pass < $passes} {incr pass} {
# Split by radix, then merge back into the list
set lst [concat {*}[splitByRadix $lst $base $pass]]
}
return $lst
}</lang>
Demonstrations:
<lang tcl>puts [radixSort {1 3 8 9 0 0 8 7 1 6}]
puts [radixSort {170 45 75 90 2 24 802 66}]</lang>
Output:
<pre>
0 0 1 1 3 6 7 8 8 9
2 24 45 66 75 90 170 802
</pre>
| |||