Sorting algorithms/Counting sort: Difference between revisions
Content deleted Content added
add Tcl |
→{{header|Tcl}}: Small improvements |
||
Line 157: | Line 157: | ||
=={{header|Tcl}}== |
=={{header|Tcl}}== |
||
{{works with|Tcl|8.5}} |
|||
<lang tcl>proc countingsort {a min max} { |
<lang tcl>proc countingsort {a {min ""} {max ""}} { |
||
# If either of min or max weren't given, compute them now |
|||
if {$min eq ""} { |
|||
set min [::tcl::mathfunc::min $a] |
|||
} |
|||
if {$max eq ""} { |
|||
set max [::tcl::mathfunc::max $a] |
|||
} |
|||
# Make the "array" of counters |
|||
set count [lrepeat [expr {$max - $min + 1}] 0] |
set count [lrepeat [expr {$max - $min + 1}] 0] |
||
# Count the values in the input list |
|||
foreach n $a { |
foreach n $a { |
||
set idx [expr {$n - $min}] |
set idx [expr {$n - $min}] |
||
lincr count $idx |
lincr count $idx |
||
} |
} |
||
# Build the output list |
|||
set z 0 |
set z 0 |
||
for {set i $min} {$i <= $max} {incr i} { |
for {set i $min} {$i <= $max} {incr i} { |
||
Line 175: | Line 189: | ||
} |
} |
||
# Helper that will increment an existing element of a list |
|||
proc lincr {listname idx {value 1}} { |
proc lincr {listname idx {value 1}} { |
||
upvar 1 $listname list |
upvar 1 $listname list |
||
Line 180: | Line 195: | ||
} |
} |
||
# Demo code |
|||
set min 1 |
|||
⚫ | |||
set max 10 |
|||
⚫ | |||
puts $a |
puts $a |
||
puts [countingsort $a |
puts [countingsort $a]</lang> |
||
<pre>9 7 10 2 9 7 4 3 10 2 7 10 2 1 3 8 7 3 9 5 8 5 1 6 3 7 5 4 6 9 9 6 6 10 2 4 5 2 8 2 2 5 2 9 3 3 5 7 8 4 |
<pre>9 7 10 2 9 7 4 3 10 2 7 10 2 1 3 8 7 3 9 5 8 5 1 6 3 7 5 4 6 9 9 6 6 10 2 4 5 2 8 2 2 5 2 9 3 3 5 7 8 4 |
||
1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 5 5 5 5 5 5 6 6 6 6 7 7 7 7 7 7 8 8 8 8 9 9 9 9 9 9 10 10 10 10 |
1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 5 5 5 5 5 5 6 6 6 6 7 7 7 7 7 7 8 8 8 8 9 9 9 9 9 9 10 10 10 10 |