Sorting algorithms/Radix sort: Difference between revisions
Content added Content deleted
(Add Rust implementation) |
m (→{{header|Phix}}: added syntax colouring the hard way) |
||
Line 2,120: | Line 2,120: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
<lang Phix> |
<!--<lang Phix>(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
sequence buckets = repeat({},10) |
|||
sequence res = {} |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">radixSortn</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
|||
for i=1 to length(s) do |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">buckets</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">({},</span><span style="color: #000000;">10</span><span style="color: #0000FF;">),</span> |
|||
integer digit = remainder(floor(s[i]/power(10,n-1)),10)+1 |
|||
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span> |
|||
buckets[digit] = append(buckets[digit],s[i]) |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
end for |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">digit</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]/</span><span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)),</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span> |
|||
for i=1 to length(buckets) do |
|||
<span style="color: #000000;">buckets</span><span style="color: #0000FF;">[</span><span style="color: #000000;">digit</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">buckets</span><span style="color: #0000FF;">[</span><span style="color: #000000;">digit</span><span style="color: #0000FF;">],</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span> |
|||
integer len = length(buckets[i]) |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
if len!=0 then |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">buckets</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
if len=1 or n=1 then |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">len</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">buckets</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span> |
|||
res &= buckets[i] |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">len</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> |
|||
else |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">len</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">or</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> |
|||
res &= radixSortn(buckets[i],n-1) |
|||
<span style="color: #000000;">res</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">buckets</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> |
|||
end if |
|||
<span style="color: #008080;">else</span> |
|||
end if |
|||
<span style="color: #000000;">res</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">radixSortn</span><span style="color: #0000FF;">(</span><span style="color: #000000;">buckets</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
return res |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
end function |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span> |
|||
function split_by_sign(sequence s) |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
sequence buckets = {{},{}} |
|||
for i=1 to length(s) do |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">split_by_sign</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> |
|||
integer si = s[i] |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">buckets</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{},{}}</span> |
|||
if si<0 then |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
buckets[1] = append(buckets[1],-si) |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">si</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> |
|||
else |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">si</span><span style="color: #0000FF;"><</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> |
|||
buckets[2] = append(buckets[2],si) |
|||
<span style="color: #000000;">buckets</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">buckets</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],-</span><span style="color: #000000;">si</span><span style="color: #0000FF;">)</span> |
|||
end if |
|||
<span style="color: #008080;">else</span> |
|||
end for |
|||
<span style="color: #000000;">buckets</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">buckets</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">],</span><span style="color: #000000;">si</span><span style="color: #0000FF;">)</span> |
|||
return buckets |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
end function |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">buckets</span> |
|||
function radixSort(sequence s) |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
integer mins = min(s) |
|||
integer passes = max(max(s),abs(mins)) |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">radixSort</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> |
|||
passes = floor(log10(passes))+1 |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">mins</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">),</span> |
|||
if mins<0 then |
|||
<span style="color: #000000;">passes</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">abs</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mins</span><span style="color: #0000FF;">))</span> |
|||
sequence buckets = split_by_sign(s) |
|||
<span style="color: #000000;">passes</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">log10</span><span style="color: #0000FF;">(</span><span style="color: #000000;">passes</span><span style="color: #0000FF;">))+</span><span style="color: #000000;">1</span> |
|||
buckets[1] = reverse(sq_uminus(radixSortn(buckets[1],passes))) |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">mins</span><span style="color: #0000FF;"><</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> |
|||
buckets[2] = radixSortn(buckets[2],passes) |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">buckets</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">split_by_sign</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> |
|||
s = buckets[1]&buckets[2] |
|||
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">reverse</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sq_uminus</span><span style="color: #0000FF;">(</span><span style="color: #000000;">radixSortn</span><span style="color: #0000FF;">(</span><span style="color: #000000;">buckets</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span><span style="color: #000000;">passes</span><span style="color: #0000FF;">)))</span> |
|||
else |
|||
<span style="color: #0000FF;">&</span> <span style="color: #000000;">radixSortn</span><span style="color: #0000FF;">(</span><span style="color: #000000;">buckets</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">],</span><span style="color: #000000;">passes</span><span style="color: #0000FF;">)</span> |
|||
s = radixSortn(s,passes) |
|||
<span style="color: #008080;">else</span> |
|||
end if |
|||
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">radixSortn</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000;">passes</span><span style="color: #0000FF;">)</span> |
|||
return s |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
end function |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">s</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
?radixSort({1, 3, 8, 9, 0, 0, 8, 7, 1, 6}) |
|||
?radixSort({170, 45, 75, 90, 2, 24, 802, 66}) |
|||
<span style="color: #0000FF;">?</span><span style="color: #000000;">radixSort</span><span style="color: #0000FF;">({</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">8</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">9</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">8</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">7</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">6</span><span style="color: #0000FF;">})</span> |
|||
?radixSort({170, 45, 75, 90, 2, 24, -802, -66}) |
|||
<span style="color: #0000FF;">?</span><span style="color: #000000;">radixSort</span><span style="color: #0000FF;">({</span><span style="color: #000000;">170</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">45</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">75</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">90</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">24</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">802</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">66</span><span style="color: #0000FF;">})</span> |
|||
?radixSort({100000, -10000, 400, 23, 10000})</lang> |
|||
<span style="color: #0000FF;">?</span><span style="color: #000000;">radixSort</span><span style="color: #0000FF;">({</span><span style="color: #000000;">170</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">45</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">75</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">90</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">24</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">802</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">66</span><span style="color: #0000FF;">})</span> |
|||
<span style="color: #0000FF;">?</span><span style="color: #000000;">radixSort</span><span style="color: #0000FF;">({</span><span style="color: #000000;">100000</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">10000</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">400</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">23</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">10000</span><span style="color: #0000FF;">})</span> |
|||
<!--</lang>--> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |