Sorting algorithms/Radix sort: Difference between revisions
(→Tcl: Added implementation) |
m (→{{header|D}}: + D) |
||
Line 2: | Line 2: | ||
In this task, the goal is to sort an integer array with the [[wp:Radix sort|radix sort algorithm]]. The primary purpose is to complete the characterization of sort algorithms task. |
In this task, the goal is to sort an integer array with the [[wp:Radix sort|radix sort algorithm]]. The primary purpose is to complete the characterization of sort algorithms task. |
||
=={{header|D}}== |
|||
<lang d>import std.stdio, std.math, std.conv, std.traits, std.range, std.algorithm ; |
|||
auto rdxsort(int N = 10 , R)(R r) |
|||
if(hasLength!R && isRandomAccessRange!R && isIntegral!(ElementType!R)) { |
|||
alias ElementType!R E ; |
|||
static if(isDynamicArray!R) { |
|||
writeln("input is array => in place sort") ; |
|||
alias r res ; |
|||
E absMax = reduce!max(map!abs(r)) ; |
|||
} else { |
|||
writeln("input is Range => return a newly sorted array") ; |
|||
E[] res ; |
|||
E absMax ; |
|||
foreach(v;r) { |
|||
res ~= v ; |
|||
if(absMax < abs(v)) |
|||
absMax = abs(v) ; |
|||
} |
|||
} |
|||
immutable passes = 1 + to!int(log(absMax)/log(N)) ; |
|||
auto pBucket = new E[][](N,0) ; |
|||
auto nBucket = new E[][](N,0) ; |
|||
void split(int pass) { |
|||
foreach(v;res) { |
|||
auto bIdx = abs(v / (N^^pass)) % N ; |
|||
if(v < 0) |
|||
nBucket[ bIdx ] ~= v ; |
|||
else |
|||
pBucket[ bIdx ] ~= v ; |
|||
} |
|||
} |
|||
void merge() { |
|||
int idx = 0 ; |
|||
foreach_reverse(ref b;nBucket) { // order revrsed for negative |
|||
foreach(v;b) |
|||
res[idx++] = v ; // reorder from bucket |
|||
b.length = 0 ; // reset this bucket |
|||
} |
|||
foreach(ref b;pBucket) { |
|||
foreach(v;b) |
|||
res[idx++] = v ; // reorder from bucket |
|||
b.length = 0 ; // reset this bucket |
|||
} |
|||
} |
|||
foreach(p;0..passes) { |
|||
split(p) ; |
|||
merge() ; |
|||
} |
|||
return res ; |
|||
} |
|||
void main() { |
|||
auto a = [170, 45, 75, -90, 2, 24, -802, 66] ; |
|||
writeln(rdxsort(a)) ; |
|||
writeln(rdxsort(map!"1-a"(a))) ; |
|||
}</lang> |
|||
Output : |
|||
<pre>input is array => in place sort |
|||
[-802, -90, 2, 24, 45, 66, 75, 170] |
|||
input is Range => return a newly sorted array |
|||
[-169, -74, -65, -44, -23, -1, 91, 803]</pre> |
|||
=={{header|J}}== |
=={{header|J}}== |
||
{{eff note|J|/:~}} |
{{eff note|J|/:~}} |
Revision as of 13:03, 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.
D
<lang d>import std.stdio, std.math, std.conv, std.traits, std.range, std.algorithm ;
auto rdxsort(int N = 10 , R)(R r)
if(hasLength!R && isRandomAccessRange!R && isIntegral!(ElementType!R)) { alias ElementType!R E ;
static if(isDynamicArray!R) { writeln("input is array => in place sort") ; alias r res ; E absMax = reduce!max(map!abs(r)) ; } else { writeln("input is Range => return a newly sorted array") ; E[] res ; E absMax ;
foreach(v;r) { res ~= v ; if(absMax < abs(v)) absMax = abs(v) ; } }
immutable passes = 1 + to!int(log(absMax)/log(N)) ;
auto pBucket = new E[][](N,0) ; auto nBucket = new E[][](N,0) ;
void split(int pass) { foreach(v;res) { auto bIdx = abs(v / (N^^pass)) % N ; if(v < 0) nBucket[ bIdx ] ~= v ; else pBucket[ bIdx ] ~= v ; } }
void merge() { int idx = 0 ; foreach_reverse(ref b;nBucket) { // order revrsed for negative foreach(v;b) res[idx++] = v ; // reorder from bucket b.length = 0 ; // reset this bucket } foreach(ref b;pBucket) { foreach(v;b) res[idx++] = v ; // reorder from bucket b.length = 0 ; // reset this bucket } }
foreach(p;0..passes) { split(p) ; merge() ; }
return res ;
}
void main() {
auto a = [170, 45, 75, -90, 2, 24, -802, 66] ; writeln(rdxsort(a)) ; writeln(rdxsort(map!"1-a"(a))) ;
}</lang> Output :
input is array => in place sort [-802, -90, 2, 24, 45, 66, 75, 170] input is Range => return a newly sorted array [-169, -74, -65, -44, -23, -1, 91, 803]
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