Rosetta Code

Sorting algorithms/Radix sort: Difference between revisions

Page Discussion

Sorting algorithms/Radix sort (view source)

Revision as of 14:25, 9 February 2024

17,330 bytes added ,  3 months ago
Added uBasic/4tH version
imported>Thebeez
(Added uBasic/4tH version)
 
(13 intermediate revisions by 6 users not shown)
Line 12:
{{trans|Python}}
 
<langsyntaxhighlight lang="11l">F flatten(some_list)
[Int] new_list
L(sub_list) some_list
Line 36:
 
V arr = [7, 6, 5, 9, 8, 4, 3, 1, 2, 0]
print(radix_sort(arr))</langsyntaxhighlight>
 
{{out}}
Line 45:
=={{header|AArch64 Assembly}}==
{{works with|as|Raspberry Pi 3B version Buster 64 bits}}
<syntaxhighlight lang="aarch64 assembly">
<lang AArch64 Assembly>
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program radixSort64.s */
Line 214:
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
</syntaxhighlight>
</lang>
<pre>
Value : -154389710
Line 234:
 
radix_sort.adb:
<langsyntaxhighlight Adalang="ada">with Ada.Text_IO;
procedure Radix_Sort is
type Integer_Array is array (Positive range <>) of Integer;
Line 316:
end loop;
Ada.Text_IO.New_Line;
end Radix_Sort;</langsyntaxhighlight>
 
output:
Line 322:
 
=={{header|ALGOL 68}}==
<langsyntaxhighlight lang="algol68">PROC radixsort = (REF []INT array) VOID:
(
[UPB array]INT zero;
Line 371:
radixsort(a);
print(("After: ", a))
)</langsyntaxhighlight>
{{out}}
<pre>
Line 380:
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
<syntaxhighlight lang="arm assembly">
<lang ARM Assembly>
/* ARM assembly Raspberry PI */
/* program radixSort1.s */
Line 544:
/***************************************************/
.include "../affichage.inc"
</syntaxhighlight>
</lang>
<pre>
Value : -25000
Line 563:
=={{header|Arturo}}==
 
<langsyntaxhighlight lang="rebol">radixSort: function [items][
base: 10
a: new items
Line 581:
]
 
print radixSort [3 1 2 8 5 7 9 4 6]</langsyntaxhighlight>
 
{{out}}
 
<pre>1 2 3 4 5 6 7 8 9</pre>
 
=={{header|ATS}}==
 
<syntaxhighlight lang="ats">(*
Stable integer-keyed radix sorts for unsigned and signed integers
of the various typekinds.
 
The radix is 256.
*)
 
(*------------------------------------------------------------------*)
 
#include "share/atspre_staload.hats"
staload UN = "prelude/SATS/unsafe.sats"
 
(*------------------------------------------------------------------*)
 
extern fn {a : vt@ype}
{tk : tkind}
g0uint_radix_sort
{n : int}
(arr : &array (a, n) >> _,
n : size_t n)
:<!wrt> void
 
extern fn {a : vt@ype}
{tk : tkind}
g0uint_radix_sort$key
{n : int}
{i : nat | i < n}
(arr : &RD(array (a, n)),
i : size_t i)
:<> g0uint tk
 
(*------------------------------------------------------------------*)
 
extern fn {a : vt@ype}
{tki, tku : tkind}
g0int_radix_sort
{n : int}
(arr : &array (a, n) >> _,
n : size_t n)
:<!wrt> void
 
extern fn {a : vt@ype}
{tki : tkind}
g0int_radix_sort$key
{n : int}
{i : nat | i < n}
(arr : &RD(array (a, n)),
i : size_t i)
:<> g0int tki
 
(*------------------------------------------------------------------*)
 
(* WARNING: Much of the following code does NOT take into account
the linearity of array entries. But this unsafeness is
hidden from the user. *)
 
fn {}
bin_sizes_to_indices
(bin_indices : &array (size_t, 256) >> _)
:<!wrt> void =
let
fun
loop {i : int | i <= 256}
{accum : int}
.<256 - i>.
(bin_indices : &array (size_t, 256) >> _,
i : size_t i,
accum : size_t accum)
:<!wrt> void =
if i <> i2sz 256 then
let
prval () = lemma_g1uint_param i
val elem = bin_indices[i]
in
if elem = i2sz 0 then
loop (bin_indices, succ i, accum)
else
begin
bin_indices[i] := accum;
loop (bin_indices, succ i, accum + g1ofg0 elem)
end
end
in
loop (bin_indices, i2sz 0, i2sz 0)
end
 
fn {a : vt@ype}
{tk : tkind}
count_entries
{n : int}
{shift : nat}
(arr : &RD(array (a, n)),
n : size_t n,
bin_indices : &array (size_t?, 256)
>> array (size_t, 256),
all_expended : &bool? >> bool,
shift : int shift)
:<!wrt> void =
let
fun
loop {i : int | i <= n}
.<n - i>.
(arr : &RD(array (a, n)),
bin_indices : &array (size_t, 256) >> _,
all_expended : &bool >> bool,
i : size_t i)
:<!wrt> void =
if i <> n then
let
prval () = lemma_g1uint_param i
val key : g0uint tk = g0uint_radix_sort$key<a><tk> (arr, i)
val key_shifted = key >> shift
val digit = ($UN.cast{uint} key_shifted) land 255U
val [digit : int] digit = g1ofg0 digit
extern praxi set_range :
() -<prf> [0 <= digit; digit <= 255] void
prval () = set_range ()
val count = bin_indices[digit]
val () = bin_indices[digit] := succ count
in
all_expended := all_expended * iseqz key_shifted;
loop (arr, bin_indices, all_expended, succ i)
end
 
prval () = lemma_array_param arr
in
array_initize_elt<size_t> (bin_indices, i2sz 256, i2sz 0);
all_expended := true;
loop (arr, bin_indices, all_expended, i2sz 0)
end
 
fn {a : vt@ype}
{tk : tkind}
sort_by_digit
{n : int}
{shift : nat}
(arr1 : &RD(array (a, n)),
arr2 : &array (a, n) >> _,
n : size_t n,
all_expended : &bool? >> bool,
shift : int shift)
:<!wrt> void =
let
var bin_indices : array (size_t, 256)
in
count_entries<a><tk> (arr1, n, bin_indices, all_expended, shift);
if all_expended then
()
else
let
fun
rearrange {i : int | i <= n}
.<n - i>.
(arr1 : &RD(array (a, n)),
arr2 : &array (a, n) >> _,
bin_indices : &array (size_t, 256) >> _,
i : size_t i)
:<!wrt> void =
if i <> n then
let
prval () = lemma_g1uint_param i
val key = g0uint_radix_sort$key<a><tk> (arr1, i)
val key_shifted = key >> shift
val digit = ($UN.cast{uint} key_shifted) land 255U
val [digit : int] digit = g1ofg0 digit
extern praxi set_range :
() -<prf> [0 <= digit; digit <= 255] void
prval () = set_range ()
val [j : int] j = g1ofg0 bin_indices[digit]
 
(* One might wish to get rid of this assertion somehow,
to eliminate the branch, should it prove a
problem. *)
val () = $effmask_exn assertloc (j < n)
 
val p_dst = ptr_add<a> (addr@ arr2, j)
and p_src = ptr_add<a> (addr@ arr1, i)
val _ = $extfcall (ptr, "memcpy", p_dst, p_src,
sizeof<a>)
val () = bin_indices[digit] := succ (g0ofg1 j)
in
rearrange (arr1, arr2, bin_indices, succ i)
end
 
prval () = lemma_array_param arr1
in
bin_sizes_to_indices<> bin_indices;
rearrange (arr1, arr2, bin_indices, i2sz 0)
end
end
 
fn {a : vt@ype}
{tk : tkind}
g0uint_sort {n : pos}
(arr1 : &array (a, n) >> _,
arr2 : &array (a, n) >> _,
n : size_t n)
:<!wrt> void =
let
fun
loop {idigit_max, idigit : nat | idigit <= idigit_max}
.<idigit_max - idigit>.
(arr1 : &array (a, n) >> _,
arr2 : &array (a, n) >> _,
from1to2 : bool,
idigit_max : int idigit_max,
idigit : int idigit)
:<!wrt> void =
if idigit = idigit_max then
begin
if ~from1to2 then
let
val _ =
$extfcall (ptr, "memcpy", addr@ arr1, addr@ arr2,
sizeof<a> * n)
in
end
end
else if from1to2 then
let
var all_expended : bool
in
sort_by_digit<a><tk> (arr1, arr2, n, all_expended,
8 * idigit);
if all_expended then
()
else
loop (arr1, arr2, false, idigit_max, succ idigit)
end
else
let
var all_expended : bool
in
sort_by_digit<a><tk> (arr2, arr1, n, all_expended,
8 * idigit);
if all_expended then
let
val _ =
$extfcall (ptr, "memcpy", addr@ arr1, addr@ arr2,
sizeof<a> * n)
in
end
else
loop (arr1, arr2, true, idigit_max, succ idigit)
end
in
loop (arr1, arr2, true, sz2i sizeof<g1uint tk>, 0)
end
 
#define SIZE_THRESHOLD 256
 
extern praxi
unsafe_cast_array
{a : vt@ype}
{b : vt@ype}
{n : int}
(arr : &array (b, n) >> array (a, n))
:<prf> void
 
implement {a} {tk}
g0uint_radix_sort {n} (arr, n) =
if n <> 0 then
let
prval () = lemma_array_param arr
 
fn
sort {n : pos}
(arr1 : &array (a, n) >> _,
arr2 : &array (a, n) >> _,
n : size_t n)
:<!wrt> void =
g0uint_sort<a><tk> (arr1, arr2, n)
in
if n <= SIZE_THRESHOLD then
let
var arr2 : array (a, SIZE_THRESHOLD)
prval @(pf_left, pf_right) =
array_v_split {a?} {..} {SIZE_THRESHOLD} {n} (view@ arr2)
prval () = view@ arr2 := pf_left
prval () = unsafe_cast_array{a} arr2
 
val () = sort (arr, arr2, n)
 
prval () = unsafe_cast_array{a?} arr2
prval () = view@ arr2 :=
array_v_unsplit (view@ arr2, pf_right)
in
end
else
let
val @(pf_arr2, pfgc_arr2 | p_arr2) = array_ptr_alloc<a> n
macdef arr2 = !p_arr2
prval () = unsafe_cast_array{a} arr2
 
val () = sort (arr, arr2, n)
 
prval () = unsafe_cast_array{a?} arr2
val () = array_ptr_free (pf_arr2, pfgc_arr2 | p_arr2)
in
end
end
 
(*------------------------------------------------------------------*)
 
fn {a : vt@ype}
{tki, tku : tkind}
g0int_sort {n : int}
(arr : &array (a, n) >> _,
n : size_t n)
:<!wrt> void =
let
macdef get_key = g0int_radix_sort$key<a><tki>
prval () = lemma_array_param arr
in
if n = 0 then
()
else
let
val () = $effmask_exn
assertloc (sizeof<g0int tki> = sizeof<g0uint tku>)
 
fn
find_least_key (arr : &RD(array (a, n)))
:<> g0int tki =
let
fun
loop {i : int | i <= n}
.<n - i>.
(arr : &RD(array (a, n)),
least_key : g0int tki,
i : size_t i)
:<> g0int tki =
if i <> n then
let
prval () = lemma_g1uint_param i
val key = get_key (arr, i)
in
loop (arr, min (least_key, key), succ i)
end
else
least_key
in
if n = 0 then
get_key (arr, i2sz 0)
else
let
val first_key = get_key (arr, i2sz 0)
in
loop (arr, first_key, i2sz 1)
end
end
 
val least_key = find_least_key arr
 
(* The offset is the two's complement of the least key. Thus the
least key is mapped to zero and the order of keys is
preserved. *)
val offset = succ (lnot ($UN.cast{g1uint tku} least_key))
 
implement
g0uint_radix_sort$key<a><tku> (arr, i) =
let
val keyi = get_key (arr, i)
in
g0i2u keyi + offset
end
in
g0uint_radix_sort<a><tku> (arr, n)
end
end
 
implement {a} {tki, tku}
g0int_radix_sort (arr, n) =
g0int_sort<a><tki, tku> (arr, n)
 
(*------------------------------------------------------------------*)
 
implement
main0 () =
let
implement
g0int_radix_sort$key<int><intknd> (arr, i) =
arr[i]
 
var arr : array (int, 10)
val () =
array_initize_list<int>
(arr, 10, $list (1, 2, 1, ~2, 330, 5000, 16, ~20000, 1, 2))
val () = g0int_radix_sort<int><intknd, uintknd> (arr, i2sz 10)
val () = println! (list_vt2t (array2list (arr, i2sz 10)))
in
end
 
(*------------------------------------------------------------------*)</syntaxhighlight>
 
{{out}}
<pre>$ patscc -O3 -DATS_MEMALLOC_LIBC radix_sort_task.dats && ./a.out
-20000, -2, 1, 1, 1, 2, 2, 16, 330, 5000</pre>
 
=={{header|AutoHotkey}}==
<langsyntaxhighlight AutoHotkeylang="autohotkey">Radix_Sort(data){
loop, parse, data, `,
n := StrLen(A_LoopField)>n?StrLen(A_LoopField):n
Line 600 ⟶ 1,001:
}
return data
}</langsyntaxhighlight>
Examples:<langsyntaxhighlight AutoHotkeylang="autohotkey">d = 170,45,75,90,802,2,24,66
MsgBox, 262144, , % Radix_Sort(d)</langsyntaxhighlight>
Outputs:<pre>2,24,45,66,75,90,170,802</pre>
 
=={{header|B4X}}==
<langsyntaxhighlight lang="b4x">Sub RadixSort (Old() As Int)
Dim i, j As Int
Dim tmp(Old.Length) As Int
Line 630 ⟶ 1,031:
Log(i)
Next
End Sub</langsyntaxhighlight>
'''Output:'''
<pre>
Line 644 ⟶ 1,045:
{{works with|BBC BASIC for Windows}}
The array index is assumed to start at zero. The third parameter of PROCradixsort() is the radix used.
<langsyntaxhighlight lang="bbcbasic"> DIM test%(9)
test%() = 4, 65, 2, -31, 0, 99, 2, 83, 782, 1
PROCradixsort(test%(), 10, 10)
Line 680 ⟶ 1,081:
ENDWHILE
a%() += l%
ENDPROC</langsyntaxhighlight>
'''Output:'''
<pre>
Line 687 ⟶ 1,088:
 
=={{header|C}}==
Radix sort, "digits" are most significant bits.<langsyntaxhighlight lang="c">#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
Line 752 ⟶ 1,153:
for (size_t i = 0; i < ARR_LEN(x); i++)
printf("%d%c", x[i], i + 1 < ARR_LEN(x) ? ' ' : '\n');
}</langsyntaxhighlight>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+}}
<langsyntaxhighlight lang="csharp">using System;
 
namespace RadixSort
Line 789 ⟶ 1,190:
}
}
}</langsyntaxhighlight>
 
=={{header|C++}}==
Line 795 ⟶ 1,196:
 
Note: the LSD radix sort uses the standard library '''std::stable_partition''' algorithm. This algorithm is guaranteed to preserve relative order and has a higher runtime cost. The MSD radix sort uses '''std::partition''' and can be significantly faster.
<langsyntaxhighlight lang="cpp">#include <algorithm>
#include <iostream>
#include <iterator>
Line 847 ⟶ 1,248:
 
return 0;
}</langsyntaxhighlight>
Output:
<pre>-802 -90 2 24 45 66 75 170 </pre>
Line 853 ⟶ 1,254:
=={{header|D}}==
===Shorter Version===
<langsyntaxhighlight lang="d">import std.stdio, std.math, std.traits, std.range, std.algorithm;
 
ElementType!R[] radixSort(size_t N=10, R)(R r)
Line 885 ⟶ 1,286:
items.radixSort().writeln();
items.map!q{1 - a}().radixSort().writeln();
}</langsyntaxhighlight>
{{out}}
<pre>[-802, -90, 2, 24, 45, 66, 75, 170]
Line 891 ⟶ 1,292:
 
===More Efficient Version===
<langsyntaxhighlight lang="d">import std.array, std.traits;
 
// considered pure for this program
Line 948 ⟶ 1,349:
items.radixSort();
writeln(items);
}</langsyntaxhighlight>
{{out}}
<pre>[2, 24, 45, 66, 75, 170, 4294966494, 4294967206]</pre>
Line 956 ⟶ 1,357:
=={{header|EasyLang}}==
 
<syntaxhighlight lang="text">
<lang># Radix sort - sorts positive integers
proc sort . d[] .
#
# radix = 10
func sort . data[] .
radix = 10256
for dmax in= data[]0
for maxdi = higher1 dto maxlen d[]
if d[di] > max
.
max = d[di]
len buck[][] radix
pos = 1
while pos <= max
for i range radix
buck[i][] = [ ]
.
for d in data[]
h = d / pos mod radix
buck[h][] &= d
.
di = 0
for i range radix
for d in buck[i][]
data[di] = d
di += 1
.
.
len pos *=buck[][] radix
pos = 1
.
while pos <= max
for i = 1 to radix
len buck[i][] 0
.
for di = 1 to len d[]
h = d[di] div pos mod radix + 1
buck[h][] &= d[di]
.
di = 1
for i = 1 to radix
for j = 1 to len buck[i][]
d[di] = buck[i][j]
di += 1
.
.
pos *= radix
.
.
data[] = [ 29 4 72 44 55 26 27 77 92 5 ]
call sort data[]
print data[]</lang>
</syntaxhighlight>
 
=={{header|Eiffel}}==
Works for positive integers. Splits up into two buckets according to the binary representation of the number.
<syntaxhighlight lang="eiffel">
<lang Eiffel>
class
RADIX_SORT
Line 1,082 ⟶ 1,487:
 
end
</syntaxhighlight>
</lang>
Test:
<syntaxhighlight lang="eiffel">
<lang Eiffel>
class
APPLICATION
Line 1,118 ⟶ 1,523:
 
end
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 1,129 ⟶ 1,534:
=={{header|Elixir}}==
{{trans|Ruby}}
<langsyntaxhighlight lang="elixir">defmodule Sort do
def radix_sort(list), do: radix_sort(list, 10)
Line 1,152 ⟶ 1,557:
end
 
IO.inspect Sort.radix_sort([-4, 5, -26, 58, -990, 331, 331, 990, -1837, 2028])</langsyntaxhighlight>
 
{{out}}
Line 1,160 ⟶ 1,565:
 
=={{header|Fortran}}==
<syntaxhighlight lang="fortran">
<lang Fortran>
 
SUBROUTINE VARRADIX(A , Siz)
Line 1,616 ⟶ 2,021:
END IF
END ! of test program
</syntaxhighlight>
</lang>
 
{{out}}
Line 1,627 ⟶ 2,032:
=={{header|Go}}==
LSD radix 256, negatives handled by flipping the high bit.
<langsyntaxhighlight lang="go">package main
 
import (
Line 1,671 ⟶ 2,076:
}
fmt.Println("sorted: ", data)
}</langsyntaxhighlight>
Output:
<pre>
Line 1,680 ⟶ 2,085:
=={{header|Groovy}}==
This solution assumes the radix is a power of 2:
<langsyntaxhighlight lang="groovy">def radixSort = { final radixExponent, list ->
def fromBuckets = new TreeMap([0:list])
def toBuckets = new TreeMap()
Line 1,703 ⟶ 2,108:
final twosComplIndx = [] + (keys.findAll(neg)) + (keys.findAll(pos))
twosComplIndx.collect { fromBuckets[it] }.findAll { it != null }.flatten()
}</langsyntaxhighlight>
 
Test:
<langsyntaxhighlight lang="groovy">println (radixSort(3, [23,76,99,58,97,57,35,89,51,38,95,92,24,46,31,24,14,12,57,78,4]))
println (radixSort(3, [88,18,31,44,4,0,8,81,14,78,20,76,84,33,73,75,82,5,62,70,12,7,1]))
println (radixSort(3, [23,-76,-990,580,97,57,350000,Long.MAX_VALUE,89,Long.MIN_VALUE,51,38,95*2**48,92,-24*2**48,46,31*2**32,24,14,12,57,78,4]))
Line 1,724 ⟶ 2,129:
println (radixSort(32, [23,76,99,58,97,57,35,89,51,38,95,92,24,46,31,24,14,12,57,78,4]))
println (radixSort(32, [88,18,31,44,4,0,8,81,14,78,20,76,84,33,73,75,82,5,62,70,12,7,1]))
println (radixSort(32, [23,-76,-990,580,97,57,350000,Long.MAX_VALUE,89,Long.MIN_VALUE,51,38,95*2**48,92,-24*2**48,46,31*2**32,24,14,12,57,78,4]))</langsyntaxhighlight>
 
Output:
Line 1,750 ⟶ 2,155:
=={{header|Haskell}}==
 
<langsyntaxhighlight lang="haskell">import Data.Bits (Bits(testBit, bitSize))
import Data.List (partition)
 
Line 1,771 ⟶ 2,176:
aux (-1) list = list
aux bit list = aux (bit - 1) lower ++ aux (bit - 1) upper where
(lower, upper) = partition (not . flip testBit bit) list</langsyntaxhighlight>
 
=={{header|Icon}} and {{header|Unicon}}==
Line 1,778 ⟶ 2,183:
contains a subtle inefficiency: subscripting a numeric value first coerces it into a string.
 
<langsyntaxhighlight lang="unicon">procedure main(A)
every writes((!rSort(A)||" ")|"\n")
end
Line 1,791 ⟶ 2,196:
}
return A
end</langsyntaxhighlight>
 
Sample run:
Line 1,805 ⟶ 2,210:
<code>keys f/. data </code> 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 <code>}.</code>.
 
<syntaxhighlight lang="j">
<lang j>
radixSortR =: 3 : 0 NB. base radixSort data
16 radixSortR y
Line 1,816 ⟶ 2,221:
end.
x#.keys NB. restore the data
)</langsyntaxhighlight>
 
An alternate implementation is
<langsyntaxhighlight lang="j">radixsort=: (] #~ [: +/ =/) i.@(>./)</langsyntaxhighlight>
 
This uses the maximum value of the list for the base, which allows the list to be sorted in one pass.
Line 1,825 ⟶ 2,230:
Example use:
 
<langsyntaxhighlight lang="j"> radixsort ?.@#~10
4 5 6 6 6 6 6 8 8</langsyntaxhighlight>
 
Or, for negative number support:
 
<langsyntaxhighlight lang="j">rsort=: (] + radixsort@:-) <./</langsyntaxhighlight>
 
Example:
 
<langsyntaxhighlight lang="j"> rsort _6+?.@#~10
_2 _1 0 0 0 0 0 2 2</langsyntaxhighlight>
 
=={{header|Java}}==
<langsyntaxhighlight lang="java">public static int[] sort(int[] old) {
// Loop for every bit in the integers
for (int shift = Integer.SIZE - 1; shift > -1; shift--) {
Line 1,871 ⟶ 2,276:
 
return old;
}</langsyntaxhighlight>
 
{{trans|NetRexx}}
<syntaxhighlight lang="java">
<lang Java>
import java.util.ArrayList;
import java.util.Arrays;
Line 1,993 ⟶ 2,398:
}
}
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 2,019 ⟶ 2,424:
 
=={{header|jq}}==
<langsyntaxhighlight lang="jq"># Sort the input array;
# "base" must be an integer greater than 1
def radix_sort(base):
Line 2,042 ⟶ 2,447:
def radix_sort:
radix_sort(10);
</syntaxhighlight>
</lang>
'''Example'''
<syntaxhighlight lang="jq">
<lang jq>
# Verify that radix_sort agrees with sort
( [1, 3, 8, 9, 0, 0, 8, 7, 1, 6],
Line 2,050 ⟶ 2,455:
[170, 45, 75, 90, 2, 24, -802, -66] )
| (radix_sort == sort)
</syntaxhighlight>
</lang>
{{Out}}
true
Line 2,058 ⟶ 2,463:
=={{header|Julia}}==
{{trans|Scala}}
<langsyntaxhighlight lang="julia">function radixsort(tobesorted::Vector{Int64})
arr = deepcopy(tobesorted)
for shift in 63:-1:0
Line 2,085 ⟶ 2,490:
 
testradixsort()
</langsyntaxhighlight>{{output}}<pre>
[-802, -90, 2, 24, 45, 66, 75, 170]
[-1837, -990, -26, -4, 5, 58, 331, 331, 990, 2028]
Line 2,092 ⟶ 2,497:
=={{header|Kotlin}}==
{{trans|Java}}
<langsyntaxhighlight lang="scala">// version 1.1.2
 
fun radixSort(original: IntArray): IntArray {
Line 2,127 ⟶ 2,532:
)
for (array in arrays) println(radixSort(array).contentToString())
}</langsyntaxhighlight>
 
{{out}}
Line 2,136 ⟶ 2,541:
 
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<langsyntaxhighlight Mathematicalang="mathematica">ClearAll[SortByPos, RadixSort]
SortByPos[data : {_List ..}, pos_Integer] := Module[{digs, order},
digs = data[[All, pos]];
Line 2,152 ⟶ 2,557:
digs += offset;
digs
]</langsyntaxhighlight>
Testing out the algorithm:
<langsyntaxhighlight Mathematicalang="mathematica">RadixSort[{170,45,75,-90,-802,24,2,66}]
RadixSort[{170,45,75,90,802,2,24,66}]</langsyntaxhighlight>
{{out}}
<pre>{-802,-90,2,24,45,66,75,170}
Line 2,162 ⟶ 2,567:
=={{header|Nim}}==
{{trans|Kotlin}}
<langsyntaxhighlight Nimlang="nim">func radixSort[T](a: openArray[T]): seq[T] =
 
result = @a
Line 2,185 ⟶ 2,590:
tmp[i] = result[i - j]
# And now the tmp array gets switched for another round of sorting.
result.shallowCopy =move(tmp)
 
 
Line 2,194 ⟶ 2,599:
 
for a in arrays:
echo radixSort(a)</langsyntaxhighlight>
 
{{out}}
Line 2,205 ⟶ 2,610:
Limitations - Handles decimal digits only.
===Using the <tt>Rexx</tt> class===
<langsyntaxhighlight NetRexxlang="netrexx">/* NetRexx */
options replace format comments java crossref symbols nobinary
 
Line 2,277 ⟶ 2,682:
end il
return
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 2,308 ⟶ 2,713:
</pre>
===Using <tt>Collection</tt> classes===
<langsyntaxhighlight NetRexxlang="netrexx">/* NetRexx */
options replace format comments java crossref symbols nobinary
 
Line 2,394 ⟶ 2,799:
end il
return
</syntaxhighlight>
</lang>
 
=={{header|Perl}}==
Radix sort in base 10.
<langsyntaxhighlight lang="perl">#!/usr/bin/perl
use warnings;
use strict;
Line 2,430 ⟶ 2,835:
$_ = 0 + $_ for @return; # Remove zeros.
return @return;
}</langsyntaxhighlight>
To test, add the following lines:
<langsyntaxhighlight lang="perl">use Test::More tests => 1000;
 
for (1 .. 1000) {
my @l = map int rand(2000) - 1000, 0 .. 20;
is_deeply([radix(@l)], [sort { $a <=> $b } @l]);
}</langsyntaxhighlight>
 
=={{header|Phix}}==
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
Line 2,494 ⟶ 2,899:
<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>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
Line 2,505 ⟶ 2,910:
=={{header|PicoLisp}}==
This is a LSD base-2 radix sort using queues:
<langsyntaxhighlight PicoLisplang="picolisp">(de radixSort (Lst)
(let Mask 1
(while
Line 2,519 ⟶ 2,924:
Mask (* 2 Mask) )
Flg ) ) )
Lst )</langsyntaxhighlight>
Output:
<pre>: (radixSort (make (do 12 (link (rand -999 999)))))
Line 2,525 ⟶ 2,930:
 
=={{header|PureBasic}}==
<langsyntaxhighlight PureBasiclang="purebasic">Structure bucket
List i.i()
EndStructure
Line 2,610 ⟶ 3,015:
Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input()
CloseConsole()
EndIf</langsyntaxhighlight>
Sample output:
<pre>0, 0, 1, 1, 3, 6, 7, 8, 8, 9
Line 2,621 ⟶ 3,026:
This is the Wikipedia example code extended with an extra pass to sort negative values correctly.
 
<langsyntaxhighlight lang="python">#python2.6 <
from math import log
Line 2,668 ⟶ 3,073:
new_list = merge(split(new_list, base, digit_num))
return merge(split_by_sign(new_list))
</syntaxhighlight>
</lang>
 
An alternate implementation using which works on Python 3:
 
<langsyntaxhighlight lang="python">#python3.7 <
def flatten(some_list):
"""
Line 2,745 ⟶ 3,150:
 
return flattened_result
</syntaxhighlight>
</lang>
 
That same example but more compact:
 
<langsyntaxhighlight lang="python">#python3.7 <
def flatten(l):
return [y for x in l for y in x]
Line 2,770 ⟶ 3,175:
 
return flatten([radix(b, p-1, s) for b in bins])
</syntaxhighlight>
</lang>
 
=={{header|QB64}}==
<syntaxhighlight lang="qb64">
<lang QB64>
#lang QB64
'* don't be an a$$. Keep this credit notice with the source:
Line 3,078 ⟶ 3,483:
END SELECT
END SUB
</syntaxhighlight>
</lang>
 
=={{header|Quackery}}==
 
<langsyntaxhighlight Quackerylang="quackery"> [ stack ] is digit ( --> s )
 
[ behead swap witheach min ] is smallest ( [ --> n )
Line 3,127 ⟶ 3,532:
100 < if sp
echo sp ] cr ]
drop</langsyntaxhighlight>
 
{{out}}
Line 3,150 ⟶ 3,555:
 
=={{header|Racket}}==
<syntaxhighlight lang="racket">
<lang Racket>
#lang Racket
(define (radix-sort l r)
Line 3,176 ⟶ 3,581:
(sorted? (radix-sort (make-random-list) (+ 2 (random 98)))))
;; => #t, so all passed
</syntaxhighlight>
</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.)
<syntaxhighlight lang="raku" perl6line>sub radsort (@ints) {
my $maxlen = max @ints».chars;
my @list = @ints».fmt("\%0{$maxlen}d");
Line 3,194 ⟶ 3,599:
}
 
.say for radsort (-2_000 .. 2_000).roll(20);</langsyntaxhighlight>
{{out}}
<pre>-1585
Line 3,219 ⟶ 3,624:
=={{header|REXX}}==
This REXX version also works with malformed integers. &nbsp; &nbsp; &nbsp; '''7''', &nbsp; '''007''', &nbsp; '''+7''', &nbsp; '''.7e1''', &nbsp; '''7.0''' &nbsp; are all treated as equal.
<langsyntaxhighlight lang="rexx">/*REXX program performs a radix sort on an integer array (can be negative/zero/positive)*/
call gen /*call subroutine to generate numbers. */
call radSort n, w /*invoke the radix sort subroutine. */
Line 3,284 ⟶ 3,689:
/*──────────────────────────────────────────────────────────────────────────────────────*/
show: do j=1 for n; say 'item' right(j, w) "after the radix sort:" right(@.j, w)
end /*j*/; return /* [↑] display sorted items ───► term.*/</langsyntaxhighlight>
{{out|output|text=&nbsp; &nbsp; (with the middle section elided.)}}
 
Line 3,336 ⟶ 3,741:
=={{header|Ruby}}==
Negative number handling courtesy the Tcl solution.
<langsyntaxhighlight lang="ruby">class Array
def radix_sort(base=10)
ary = dup
Line 3,361 ⟶ 3,766:
p [170, 45, 75, 90, 2, 24, 802, 66].radix_sort
p [170, 45, 75, 90, 2, 24, -802, -66].radix_sort
p [100000, -10000, 400, 23, 10000].radix_sort</langsyntaxhighlight>
running with $DEBUG on produces:
<pre>[0, [0, 0, 1, 1, 3, 6, 7, 8, 8, 9]]
Line 3,382 ⟶ 3,787:
 
another version (After sorting at the absolute value, it makes a negative order reverse.)
<langsyntaxhighlight lang="ruby">class Array
def radix_sort(base=10)
ary = dup
Line 3,394 ⟶ 3,799:
ary.partition{|n| n<0}.inject{|minus,plus| minus.reverse + plus}
end
end</langsyntaxhighlight>
 
=={{header|Rust}}==
<langsyntaxhighlight lang="rust">
fn merge(in1: &[i32], in2: &[i32], out: &mut [i32]) {
let (left, right) = out.split_at_mut(in1.len());
Line 3,423 ⟶ 3,828:
println!("After: {:?}", data);
}
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 3,431 ⟶ 3,836:
 
=={{header|Scala}}==
<langsyntaxhighlight Scalalang="scala">object RadixSort extends App {
def sort(toBeSort: Array[Int]): Array[Int] = { // Loop for every bit in the integers
var arr = toBeSort
Line 3,456 ⟶ 3,861:
 
println(sort(Array(170, 45, 75, -90, -802, 24, 2, 66)).mkString(", "))
}</langsyntaxhighlight>
 
=={{header|Scheme}}==
 
===An implementation for non-negative integers only===
{{works with|R7RS}}
 
 
<langsyntaxhighlight Schemelang="scheme">;;; An illustrative implementation of the radix-10 example at
;;; https://en.wikipedia.org/w/index.php?title=Radix_sort&oldid=1070890278#Least_significant_digit
 
Line 3,508 ⟶ 3,915:
(radix-sort data)
(write data)
(newline)</langsyntaxhighlight>
 
{{out}}
Line 3,514 ⟶ 3,921:
#(170 45 75 90 2 802 2 66)
#(2 2 45 66 75 90 170 802)</pre>
 
===An implementation using lexicographic order to support negative integers===
{{works with|R7RS}}
 
 
The following implementation converts signed integers to a lexicographically ordered representation (specifically, unsigned numbers in the correct order). It then sorts the lexicographically ordered representation, and finally converts back to the original representation.
 
<syntaxhighlight lang="scheme">;;; An illustrative implementation of the radix-10 example at
;;; https://en.wikipedia.org/w/index.php?title=Radix_sort&oldid=1070890278#Least_significant_digit
 
(cond-expand
(r7rs)
(chicken (import (r7rs))))
 
(import (scheme base))
(import (scheme write))
 
(define (sort-by-decimal-digit data power-of-10)
(define bins (make-vector 10 '()))
(do ((i (- (vector-length data) 1) (- i 1)))
((= i -1))
(let* ((element (vector-ref data i))
(digit (truncate-remainder
(truncate-quotient element power-of-10)
10)))
(vector-set! bins digit
(cons element (vector-ref bins digit)))))
(let ((non-zero-found
(let loop ((i 1))
(cond ((= i (vector-length bins)) #f)
((pair? (vector-ref bins i)) #t)
(else (loop (+ i 1)))))))
(when non-zero-found
(let ((i 0))
(do ((j 0 (+ j 1)))
((= j (vector-length bins)))
(do ((p (vector-ref bins j) (cdr p)))
((null? p))
(vector-set! data i (car p))
(set! i (+ i 1))))))
(not non-zero-found)))
 
(define (radix-sort data)
(define offset 0)
 
(do ((i 0 (+ i 1)))
((<= (vector-length data) i))
(let ((x (vector-ref data i)))
(when (negative? x)
(set! offset (max offset (- x))))))
 
(do ((i 0 (+ i 1)))
((= i (vector-length data)))
(vector-set! data i (+ (vector-ref data i) offset)))
 
(let loop ((power-of-10 1))
(let ((done (sort-by-decimal-digit data power-of-10)))
(unless done
(loop (* 10 power-of-10)))))
 
(do ((i 0 (+ i 1)))
((= i (vector-length data)))
(let ((x (vector-ref data i)))
(vector-set! data i (- (vector-ref data i) offset)))))
 
(define data (vector-copy #(170 45 75 90 2 802 2 66)))
(write data)
(newline)
(radix-sort data)
(write data)
(newline)
 
(newline)
(set! data (vector-copy #(170 -45 75 -90 2 -802 2 -66)))
(write data)
(newline)
(radix-sort data)
(write data)
(newline)</syntaxhighlight>
 
{{out}}
<pre>$ chibi radix_sort_task-2.scm
#(170 45 75 90 2 802 2 66)
#(2 2 45 66 75 90 170 802)
 
#(170 -45 75 -90 2 -802 2 -66)
#(-802 -90 -66 -45 2 2 75 170)</pre>
 
=={{header|Sidef}}==
{{trans|Ruby}}
<langsyntaxhighlight lang="ruby">class Array {
method radix_sort(base=10) {
var arr = self.clone
Line 3,542 ⟶ 4,036:
] {
say arr.radix_sort
}</langsyntaxhighlight>
{{out}}
<pre>
Line 3,552 ⟶ 4,046:
 
=={{header|Tailspin}}==
<langsyntaxhighlight lang="tailspin">
templates radixsort&{base:}
sink bucketize
def value: $;
$::raw ~/ $@radixsort.digit::raw -> #
when <=0 ?($value::raw <0..>)> do
..|@radixsort.positives: $value;
when <=0> do
Line 3,567 ⟶ 4,061:
end bucketize
// Negatives get completed in wrong length-order, we need to collect by length and correct at the end
@: { done: 1, digit: 1"1", positives: [], negatives: [[]], buckets: [1..$base -> []]};
$... -> !bucketize
$@.done -> #
when <=done´1> do
[$@.negatives(last..1:-1)... ..., $@.positives...] !
otherwise
def previous: $@.buckets;
..|@: {done: 1, digit: $@.digit::raw * $base, buckets:[1..$base -> []]};
..|@.negatives: [];
$previous... ... -> !bucketize
$@.done -> #
end radixsort
 
[170, 45, 75, 91, 90, 92, 802, 24, 2, 66] -> radixsort&{base:10} -> !OUT::write
'
Line 3,590 ⟶ 4,084:
' -> !OUT::write
[170, 45, 75, -91, -90, -92, -802, 24, 2, 66] -> radixsort&{base:3} -> !OUT::write
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 3,601 ⟶ 4,095:
=={{header|Tcl}}==
{{trans|Python}}
<langsyntaxhighlight lang="tcl">package require Tcl 8.5
proc splitByRadix {lst base power} {
# create a list of empty lists to hold the split by digit
Line 3,633 ⟶ 4,127:
}
return $lst
}</langsyntaxhighlight>
Demonstrations:
<langsyntaxhighlight lang="tcl">puts [radixSort {1 3 8 9 0 0 8 7 1 6}]
puts [radixSort {170 45 75 90 2 24 802 66}]
puts [radixSort {170 45 75 90 2 24 -802 -66}]</langsyntaxhighlight>
Output:
<pre>
Line 3,645 ⟶ 4,139:
</pre>
 
=={{header|uBasic/4tH}}==
{{Trans|BBC BASIC}}
In uBasic/4tH you can't pass an array as a parameter. All arrays are global.
<syntaxhighlight lang="qbasic">Dim @t(10)
 
Push 4, 65, 2, -31, 0, 99, 2, 83, 782, 1
 
For i = 0 Step 1 While Used()
@t(i) = Pop()
Next
 
Proc _Radixsort(10, 10)
 
For i = 0 TO 9
Print @t(i),
Next
 
Print
End
_Radixsort
Param (2)
Local (5)
Dim @b(a@)
Dim @u(b@)
 
For e@ = 0 TO a@-1
If @t(e@) < f@ Then f@ = @t(e@)
If @t(e@) > g@ Then g@ = @t(e@)
Next
For e@ = 0 To a@-1 : @t(e@) = @t(e@) - f@ : Next
g@ = g@ - f@
d@ = 1
Do While g@ / d@
For e@ = 0 to a@-1 : @u(e@) = 0 : Next
For e@ = 0 TO a@-1
@u(@t(e@) / d@ % b@) = @u(@t(e@) / d@ % b@) + 1
Next
For e@ = 1 TO b@-1
@u(e@) = @u(e@) + @u(e@ - 1)
Next
For e@ = a@-1 TO 0 Step -1
c@ = @t(e@) / d@ % b@
@u(c@) = @u(c@)-1
@b(@u(c@)) = @t(e@)
Next
For e@ = 0 To a@-1 : @t(e@) = @b(e@) : Next
d@ = d@ * b@
Loop
For e@ = 0 To a@-1 : @t(e@) = @t(e@) + f@ : Next
Return</syntaxhighlight>
{{Out}}
<pre>-31 0 1 2 2 4 65 83 99 782
 
0 OK, 0:177</pre>
=={{header|Wren}}==
This is based on the approach used [https://www.geeksforgeeks.org/radix-sort/ here] which I've adjusted to deal with negative elements.
<langsyntaxhighlight ecmascriptlang="wren">// counting sort of 'a' according to the digit represented by 'exp'
var countSort = Fn.new { |a, exp|
var n = a.count
Line 3,688 ⟶ 4,245:
radixSort.call(a)
System.print("Sorted : %(a)\n")
}</langsyntaxhighlight>
 
{{out}}
Line 3,701 ⟶ 4,258:
=={{header|zkl}}==
In place int sort, fairly light on garbage creation.
<langsyntaxhighlight lang="zkl">fcn radixSort(ns){ // ints only, inplace, ns is mutable
b:=(0).pump(20,List,List().copy); // 20 [empty] buckets: -10..10
z:=ns.reduce(fcn(a,b){ a.abs().max(b.abs()) },0); // |max or min of input|
Line 3,712 ⟶ 4,269:
}
ns
}</langsyntaxhighlight>
<langsyntaxhighlight lang="zkl">radixSort(T(170, 45, 75, 90, 802, 2, 24, 66)).println();
radixSort(T(170, 45, 75, -90, -802, 24, 2, 66)).println();</langsyntaxhighlight>
{{out}}
<pre>
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/170220...350525"