radixSort ?.@#~10
0 0 2 4 4 5 6 7 9 9
but:
radixSort 10 ?.@#20
0 0 17 19 19 6 12 14 14 15
If I'm not wrong 'your' radixSort only works on 1-digit numbers.
I suggest some changes:
(only one of them is really important)
radixSortR =: 3 : 0 NB. base radixSort data
16 radixSortR y
:
keys =. x #.^:_1 y NB. compute keys
length =. #{.keys
extra =. (-length) {."0 buckets =. i.x
for_pass. i.-length do.
keys =. ; (buckets,keys{~"1<pass) <@:}./.extra,keys
end.
x#.keys NB. restore the data
)
radixSortR 10 ?.@#20
0 0 6 12 14 14 15 17 19 19
If you insist. Here is a (n ugly) version without explicit loop
rSort =: 4 : 0
a=. #{. z =. x #.^:_1 y
e =. (-a) {."0 b =. i.x
x#.1{::(<:@[;([: ; (b, ] {~"1 <@[) <@:}./. e,]))&>/^:a [ z;~a-1
)
R=.?.@#~1e6
(/:~-:10&radixSortR)R
1
(/:~-:10&rSort)R
1
Observations about the influence of the LHA:
ts '10 radixSortR R'
1.73746 1.60437e8
ts '64 radixSortR R'
1.00039 9.33347e7
ts '1024 radixSortR R'
0.472434 5.5623e7
ts '20000 radixSortR R'
0.648589 5.79863e7
Hallo David Ward Lambert, je schreef op 19-01-11 04:59:
> Another opportunity to show me how to remove explicit loops!
> http://rosettacode.org/wiki/Radix_sort
>
> 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
> )
>
> ----------------------------------------------------------------------
> For information about J forums seehttp://www.jsoftware.com/forums.htm
>
--
Met vriendelijke groet,
=@@i
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
