Sorting algorithms/Radix sort: Difference between revisions
Content added Content deleted
m (→{{header|Tailspin}}: syntax update) |
Thundergnat (talk | contribs) (Rename Perl 6 -> Raku, alphabetize, minor clean-up) |
||
Line 98: | Line 98: | ||
output: |
output: |
||
<pre>-802-90 2 24 45 66 75 170</pre> |
<pre>-802-90 2 24 45 66 75 170</pre> |
||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
Line 289: | Line 287: | ||
printf("%d%c", x[i], i + 1 < ARR_LEN(x) ? ' ' : '\n'); |
printf("%d%c", x[i], i + 1 < ARR_LEN(x) ? ' ' : '\n'); |
||
}</lang>output<pre>-182 -175 -151 -141 -70 -51 -20 -5 -1 41 70 103 171 198 227 242</pre> |
}</lang>output<pre>-182 -175 -151 -141 -70 -51 -20 -5 -1 41 70 103 171 198 227 242</pre> |
||
=={{header|C sharp|C#}}== |
|||
{{works with|C sharp|C#|3.0+}} |
|||
<lang csharp>using System; |
|||
namespace RadixSort |
|||
{ |
|||
class Program |
|||
{ |
|||
static void Sort(int[] old) |
|||
{ |
|||
int i, j; |
|||
int[] tmp = new int[old.Length]; |
|||
for (int shift = 31; shift > -1; --shift) |
|||
{ |
|||
j = 0; |
|||
for (i = 0; i < old.Length; ++i) |
|||
{ |
|||
bool move = (old[i] << shift) >= 0; |
|||
if (shift == 0 ? !move : move) // shift the 0's to old's head |
|||
old[i-j] = old[i]; |
|||
else // move the 1's to tmp |
|||
tmp[j++] = old[i]; |
|||
} |
|||
Array.Copy(tmp, 0, old, old.Length-j, j); |
|||
} |
|||
} |
|||
static void Main(string[] args) |
|||
{ |
|||
int[] old = new int[] { 2, 5, 1, -3, 4 }; |
|||
Console.WriteLine(string.Join(", ", old)); |
|||
Sort(old); |
|||
Console.WriteLine(string.Join(", ", old)); |
|||
Console.Read(); |
|||
} |
|||
} |
|||
}</lang> |
|||
=={{header|C++}}== |
=={{header|C++}}== |
||
Line 349: | Line 384: | ||
Output: |
Output: |
||
<pre>-802 -90 2 24 45 66 75 170 </pre> |
<pre>-802 -90 2 24 45 66 75 170 </pre> |
||
=={{header|C sharp|C#}}== |
|||
{{works with|C sharp|C#|3.0+}} |
|||
<lang csharp>using System; |
|||
namespace RadixSort |
|||
{ |
|||
class Program |
|||
{ |
|||
static void Sort(int[] old) |
|||
{ |
|||
int i, j; |
|||
int[] tmp = new int[old.Length]; |
|||
for (int shift = 31; shift > -1; --shift) |
|||
{ |
|||
j = 0; |
|||
for (i = 0; i < old.Length; ++i) |
|||
{ |
|||
bool move = (old[i] << shift) >= 0; |
|||
if (shift == 0 ? !move : move) // shift the 0's to old's head |
|||
old[i-j] = old[i]; |
|||
else // move the 1's to tmp |
|||
tmp[j++] = old[i]; |
|||
} |
|||
Array.Copy(tmp, 0, old, old.Length-j, j); |
|||
} |
|||
} |
|||
static void Main(string[] args) |
|||
{ |
|||
int[] old = new int[] { 2, 5, 1, -3, 4 }; |
|||
Console.WriteLine(string.Join(", ", old)); |
|||
Sort(old); |
|||
Console.WriteLine(string.Join(", ", old)); |
|||
Console.Read(); |
|||
} |
|||
} |
|||
}</lang> |
|||
=={{header|D}}== |
=={{header|D}}== |
||
Line 1,296: | Line 1,294: | ||
true |
true |
||
true |
true |
||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
Line 1,401: | Line 1,398: | ||
<pre>{-802,-90,2,24,45,66,75,170} |
<pre>{-802,-90,2,24,45,66,75,170} |
||
{2,24,45,66,75,90,170,802}</pre> |
{2,24,45,66,75,90,170,802}</pre> |
||
=={{header|NetRexx}}== |
=={{header|NetRexx}}== |
||
Line 1,641: | Line 1,637: | ||
is_deeply([radix(@l)], [sort { $a <=> $b } @l]); |
is_deeply([radix(@l)], [sort { $a <=> $b } @l]); |
||
}</lang> |
}</lang> |
||
=={{header|Perl 6}}== |
|||
A base-10 radix sort, done on the string representation of the integers. Signs are handled by in-place reversal of the '-' bucket on the last iteration. (The sort in there is not cheating; it only makes sure we process the buckets in the right order, since <tt>classify</tt> might return the buckets in random order. It might be more efficient to create our own ordered buckets, but this is succinct.) |
|||
<lang perl6>sub radsort (@ints) { |
|||
my $maxlen = max @ints».chars; |
|||
my @list = @ints».fmt("\%0{$maxlen}d"); |
|||
for reverse ^$maxlen -> $r { |
|||
my @buckets = @list.classify( *.substr($r,1) ).sort: *.key; |
|||
@buckets[0].value = @buckets[0].value.reverse.List |
|||
if !$r and @buckets[0].key eq '-'; |
|||
@list = flat map *.value.values, @buckets; |
|||
} |
|||
@list».Int; |
|||
} |
|||
.say for radsort (-2_000 .. 2_000).roll(20);</lang> |
|||
{{out}} |
|||
<pre>-1585 |
|||
-1427 |
|||
-1228 |
|||
-1067 |
|||
-945 |
|||
-657 |
|||
-643 |
|||
-232 |
|||
-179 |
|||
-28 |
|||
37 |
|||
411 |
|||
488 |
|||
509 |
|||
716 |
|||
724 |
|||
1504 |
|||
1801 |
|||
1864 |
|||
1939</pre> |
|||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
Line 2,346: | Line 2,304: | ||
;; => #t, so all passed |
;; => #t, so all passed |
||
</lang> |
</lang> |
||
=={{header|Raku}}== |
|||
(formerly Perl 6) |
|||
A base-10 radix sort, done on the string representation of the integers. Signs are handled by in-place reversal of the '-' bucket on the last iteration. (The sort in there is not cheating; it only makes sure we process the buckets in the right order, since <tt>classify</tt> might return the buckets in random order. It might be more efficient to create our own ordered buckets, but this is succinct.) |
|||
<lang perl6>sub radsort (@ints) { |
|||
my $maxlen = max @ints».chars; |
|||
my @list = @ints».fmt("\%0{$maxlen}d"); |
|||
for reverse ^$maxlen -> $r { |
|||
my @buckets = @list.classify( *.substr($r,1) ).sort: *.key; |
|||
@buckets[0].value = @buckets[0].value.reverse.List |
|||
if !$r and @buckets[0].key eq '-'; |
|||
@list = flat map *.value.values, @buckets; |
|||
} |
|||
@list».Int; |
|||
} |
|||
.say for radsort (-2_000 .. 2_000).roll(20);</lang> |
|||
{{out}} |
|||
<pre>-1585 |
|||
-1427 |
|||
-1228 |
|||
-1067 |
|||
-945 |
|||
-657 |
|||
-643 |
|||
-232 |
|||
-179 |
|||
-28 |
|||
37 |
|||
411 |
|||
488 |
|||
509 |
|||
716 |
|||
724 |
|||
1504 |
|||
1801 |
|||
1864 |
|||
1939</pre> |
|||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
Line 2,522: | Line 2,519: | ||
end |
end |
||
end</lang> |
end</lang> |
||
=={{header|Scala}}== |
=={{header|Scala}}== |
||
<lang Scala>object RadixSort extends App { |
<lang Scala>object RadixSort extends App { |