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

14,332 bytes added ,  3 months ago
Added uBasic/4tH version
imported>Thebeez
(Added uBasic/4tH version)
 
(11 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}}==
Line 3,464 ⟶ 3,869:
 
 
<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,510 ⟶ 3,915:
(radix-sort data)
(write data)
(newline)</langsyntaxhighlight>
 
{{out}}
Line 3,517 ⟶ 3,922:
#(2 2 45 66 75 90 170 802)</pre>
 
===An implementation using 9's-complementslexicographic order to support negative integers===
{{works with|R7RS}}
 
 
The following implementation doesconverts notsigned supportintegers numbersto ofa arbitrarylexicographically ordered representation magnitude(specifically, butunsigned itnumbers ''does''in workthe bycorrect convertingorder). signedIt integersthen tosorts athe lexicographically ordered representation, thenand finally converts revertingback to the original representation.
 
<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
;;;
;;; This version sorts 9's-complements of the additive inverses of the
;;; integers, when converts the numbers back.
 
(cond-expand
Line 3,535 ⟶ 3,937:
(import (scheme base))
(import (scheme write))
 
(define *max-magnitude* (make-parameter 999999))
 
(define (nines-complement x)
(let ((nines (+ (* 10 (*max-magnitude*)) 9)))
(- nines x)))
 
(define (sort-by-decimal-digit data power-of-10)
Line 3,568 ⟶ 3,964:
 
(define (radix-sort data)
(define max-magnitudeoffset (*max-magnitude*)0)
 
(do ((i 0 (+ i 1)))
((<= i (vector-length data) i))
(let ((x (vector-ref data i)))
(ifwhen (negative? x)
(vector-set! dataoffset i(max offset (+- x max-magnitude))))))
 
(vector-set! data i (nines-complement
(do ((i 0 (+ i 1)))
(- max-magnitude x))))))
((= 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)))))
(if (<= x max-magnitude)
(vector-set! data i (- x max-magnitude))
(vector-set! data i (- max-magnitude
(nines-complement x)))))))
 
(define data (vector-copy #(170 45 75 90 2 802 2 66)))
Line 3,601 ⟶ 3,999:
(radix-sort data)
(write data)
(newline)</langsyntaxhighlight>
 
{{out}}
Line 3,613 ⟶ 4,011:
=={{header|Sidef}}==
{{trans|Ruby}}
<langsyntaxhighlight lang="ruby">class Array {
method radix_sort(base=10) {
var arr = self.clone
Line 3,638 ⟶ 4,036:
] {
say arr.radix_sort
}</langsyntaxhighlight>
{{out}}
<pre>
Line 3,648 ⟶ 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,663 ⟶ 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,686 ⟶ 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,697 ⟶ 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,729 ⟶ 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,741 ⟶ 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,784 ⟶ 4,245:
radixSort.call(a)
System.print("Sorted : %(a)\n")
}</langsyntaxhighlight>
 
{{out}}
Line 3,797 ⟶ 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,808 ⟶ 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/170222...350525"