Rosetta Code

Sorting algorithms/Radix sort: Difference between revisions

Page Discussion

Sorting algorithms/Radix sort (view source)

Revision as of 20:40, 15 May 2021

13,401 bytes added ,  3 years ago
m
→‎{{header|Phix}}: added syntax colouring the hard way
(Add Rust implementation)
m (→‎{{header|Phix}}: added syntax colouring the hard way)
Line 2,120:
 
=={{header|Phix}}==
<!--<lang Phix>function radixSortn(sequence s, integer nphixonline)-->
<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}}
<pre>
Petelomax
7,794

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/170207"