Sorting algorithms/Radix sort: Difference between revisions
m (whitespace) |
(→Tcl: Added implementation) |
||
Line 31: | Line 31: | ||
The wikipedia article cited in the introduction includes a python implementation of LSB radix sort. |
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> |
Revision as of 11:59, 19 January 2011
You are encouraged to solve this task according to the task description, using any language you may know.
Sorting Algorithm
This is a sorting algorithm. It may be applied to a set of data in order to sort it.
For comparing various sorts, see compare sorts.
For other sorting algorithms, see sorting algorithms, or:
Heap sort | Merge sort | Patience sort | Quick sort
O(n log2n) sorts
Shell Sort
O(n2) sorts
Bubble sort |
Cocktail sort |
Cocktail sort with shifting bounds |
Comb sort |
Cycle sort |
Gnome sort |
Insertion sort |
Selection sort |
Strand sort
other sorts
Bead sort |
Bogo sort |
Common sorted list |
Composite structures sort |
Custom comparator sort |
Counting sort |
Disjoint sublist sort |
External sort |
Jort sort |
Lexicographical sort |
Natural sorting |
Order by pair comparisons |
Order disjoint list items |
Order two numerical lists |
Object identifier (OID) sort |
Pancake sort |
Quickselect |
Permutation sort |
Radix sort |
Ranking methods |
Remove duplicate elements |
Sleep sort |
Stooge sort |
[Sort letters of a string] |
Three variable sort |
Topological sort |
Tree sort
In this task, the goal is to sort an integer array with the radix sort algorithm. The primary purpose is to complete the characterization of sort algorithms task.
J
keys f/. data
evaluates the function f on each group of data at the same position as similar keys. Sorting requires ordered keys. This code uses a J idiom: prepend the keys and matching data. The extra data is removed by behead }.
.
<lang j>NB. queue implementation of LSB radix sort. radixSort =: 3 : 0 NB. base radixSort data 16 radixSort y
keys =. x #.^:_1 y NB. compute keys length =. {:#{.keys extra =. (x,-length) {. ,. buckets =. i.x for_pass. 0{i.-length do.
keys =. ,&:>/ (buckets,keys{~"1<pass) <@:}./.extra,keys extra =. 1 |. extra
end. x#.keys NB. restore the data )</lang>
Sort 10 small numbers in base 3.
(,: 3&radixSort) ?@#~10 1 3 8 9 0 0 8 7 1 6 0 0 1 1 3 6 7 8 8 9
Python
The wikipedia article cited in the introduction includes a python implementation of LSB radix sort.
Tcl
<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:
0 0 1 1 3 6 7 8 8 9 2 24 45 66 75 90 170 802