Sorting algorithms/Radix sort: Difference between revisions

{{trans|Python}}

[Int] new_list

L(sub_list) some_list

V arr = [7, 6, 5, 9, 8, 4, 3, 1, 2, 0]

{{out}}

=={{header|AArch64 Assembly}}==

{{works with|as|Raspberry Pi 3B version Buster 64 bits}}

/* ARM assembly AARCH64 Raspberry PI 3B */

/* program radixSort64.s */

/* for this file see task include a file in language AArch64 assembly */

.include "../includeARM64.inc"

<pre>

Value : -154389710

radix_sort.adb:

procedure Radix_Sort is

type Integer_Array is array (Positive range <>) of Integer;

end loop;

Ada.Text_IO.New_Line;

output:

=={{header|ALGOL 68}}==

(

[UPB array]INT zero;

radixsort(a);

print(("After: ", a))

{{out}}

<pre>

=={{header|ARM Assembly}}==

{{works with|as|Raspberry Pi}}

/* ARM assembly Raspberry PI */

/* program radixSort1.s */

/***************************************************/

.include "../affichage.inc"

<pre>

Value : -25000

=={{header|Arturo}}==

base: 10

a: new items

]

{{out}}

=={{header|ATS}}==

Stable integer-keyed radix sorts for unsigned and signed integers

of the various typekinds.

end

{{out}}

=={{header|AutoHotkey}}==

loop, parse, data, `,

n := StrLen(A_LoopField)>n?StrLen(A_LoopField):n

}

return data

Outputs:<pre>2,24,45,66,75,90,170,802</pre>

=={{header|B4X}}==

Dim i, j As Int

Dim tmp(Old.Length) As Int

Log(i)

Next

'''Output:'''

<pre>

{{works with|BBC BASIC for Windows}}

The array index is assumed to start at zero. The third parameter of PROCradixsort() is the radix used.

test%() = 4, 65, 2, -31, 0, 99, 2, 83, 782, 1

PROCradixsort(test%(), 10, 10)

ENDWHILE

a%() += l%

'''Output:'''

<pre>

=={{header|C}}==

#include <limits.h>

#include <stdlib.h>

for (size_t i = 0; i < ARR_LEN(x); i++)

printf("%d%c", x[i], i + 1 < ARR_LEN(x) ? ' ' : '\n');

=={{header|C sharp|C#}}==

{{works with|C sharp|C#|3.0+}}

namespace RadixSort

}

}

=={{header|C++}}==

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.

#include <iostream>

#include <iterator>

return 0;

Output:

<pre>-802 -90 2 24 45 66 75 170 </pre>

=={{header|D}}==

===Shorter Version===

ElementType!R[] radixSort(size_t N=10, R)(R r)

items.radixSort().writeln();

items.map!q{1 - a}().radixSort().writeln();

{{out}}

<pre>[-802, -90, 2, 24, 45, 66, 75, 170]

===More Efficient Version===

// considered pure for this program

items.radixSort();

writeln(items);

{{out}}

<pre>[2, 24, 45, 66, 75, 170, 4294966494, 4294967206]</pre>

=={{header|EasyLang}}==

#

func sort . data[] .

data[] = [ 29 4 72 44 55 26 27 77 92 5 ]

call sort data[]

=={{header|Eiffel}}==

Works for positive integers. Splits up into two buckets according to the binary representation of the number.

class

RADIX_SORT

end

Test:

class

APPLICATION

end

{{out}}

<pre>

=={{header|Elixir}}==

{{trans|Ruby}}

def radix_sort(list), do: radix_sort(list, 10)

end

{{out}}

=={{header|Fortran}}==

SUBROUTINE VARRADIX(A , Siz)

END IF

END ! of test program

{{out}}

=={{header|Go}}==

LSD radix 256, negatives handled by flipping the high bit.

import (

}

fmt.Println("sorted: ", data)

Output:

<pre>

=={{header|Groovy}}==

This solution assumes the radix is a power of 2:

def fromBuckets = new TreeMap([0:list])

def toBuckets = new TreeMap()

final twosComplIndx = [] + (keys.findAll(neg)) + (keys.findAll(pos))

twosComplIndx.collect { fromBuckets[it] }.findAll { it != null }.flatten()

Test:

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]))

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]))

Output:

=={{header|Haskell}}==

import Data.List (partition)

aux (-1) list = list

aux bit list = aux (bit - 1) lower ++ aux (bit - 1) upper where

=={{header|Icon}} and {{header|Unicon}}==

contains a subtle inefficiency: subscripting a numeric value first coerces it into a string.

every writes((!rSort(A)||" ")|"\n")

end

}

return A

Sample run:

<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>.

radixSortR =: 3 : 0 NB. base radixSort data

16 radixSortR y

end.

x#.keys NB. restore the data

An alternate implementation is

This uses the maximum value of the list for the base, which allows the list to be sorted in one pass.

Example use:

Or, for negative number support:

Example:

=={{header|Java}}==

// Loop for every bit in the integers

for (int shift = Integer.SIZE - 1; shift > -1; shift--) {

return old;

{{trans|NetRexx}}

import java.util.ArrayList;

import java.util.Arrays;

}

}

{{out}}

<pre>

=={{header|jq}}==

# "base" must be an integer greater than 1

def radix_sort(base):

def radix_sort:

radix_sort(10);

'''Example'''

# Verify that radix_sort agrees with sort

( [1, 3, 8, 9, 0, 0, 8, 7, 1, 6],

[170, 45, 75, 90, 2, 24, -802, -66] )

| (radix_sort == sort)

{{Out}}

true

=={{header|Julia}}==

{{trans|Scala}}

arr = deepcopy(tobesorted)

for shift in 63:-1:0

testradixsort()

[-802, -90, 2, 24, 45, 66, 75, 170]

[-1837, -990, -26, -4, 5, 58, 331, 331, 990, 2028]

=={{header|Kotlin}}==

{{trans|Java}}

fun radixSort(original: IntArray): IntArray {

)

for (array in arrays) println(radixSort(array).contentToString())

{{out}}

=={{header|Mathematica}}/{{header|Wolfram Language}}==

SortByPos[data : {_List ..}, pos_Integer] := Module[{digs, order},

digs = data[[All, pos]];

digs += offset;

digs

Testing out the algorithm:

{{out}}

<pre>{-802,-90,2,24,45,66,75,170}

=={{header|Nim}}==

{{trans|Kotlin}}

result = @a

for a in arrays:

{{out}}

Limitations - Handles decimal digits only.

===Using the <tt>Rexx</tt> class===

options replace format comments java crossref symbols nobinary

end il

return

{{out}}

<pre>

</pre>

===Using <tt>Collection</tt> classes===

options replace format comments java crossref symbols nobinary

end il

return

=={{header|Perl}}==

Radix sort in base 10.

use warnings;

use strict;

$_ = 0 + $_ for @return; # Remove zeros.

return @return;

To test, add the following lines:

for (1 .. 1000) {

my @l = map int rand(2000) - 1000, 0 .. 20;

is_deeply([radix(@l)], [sort { $a <=> $b } @l]);

=={{header|Phix}}==

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<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>

{{out}}

<pre>

=={{header|PicoLisp}}==

This is a LSD base-2 radix sort using queues:

(let Mask 1

(while

Mask (* 2 Mask) )

Flg ) ) )

Output:

<pre>: (radixSort (make (do 12 (link (rand -999 999)))))

=={{header|PureBasic}}==

List i.i()

EndStructure

Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input()

CloseConsole()

Sample output:

<pre>0, 0, 1, 1, 3, 6, 7, 8, 8, 9

This is the Wikipedia example code extended with an extra pass to sort negative values correctly.

from math import log

new_list = merge(split(new_list, base, digit_num))

return merge(split_by_sign(new_list))

An alternate implementation using which works on Python 3:

def flatten(some_list):

"""

return flattened_result

That same example but more compact:

def flatten(l):

return [y for x in l for y in x]

return flatten([radix(b, p-1, s) for b in bins])

=={{header|QB64}}==

#lang QB64

'* don't be an a$$. Keep this credit notice with the source:

END SELECT

END SUB

=={{header|Quackery}}==

[ behead swap witheach min ] is smallest ( [ --> n )

100 < if sp

echo sp ] cr ]

{{out}}

=={{header|Racket}}==

#lang Racket

(define (radix-sort l r)

(sorted? (radix-sort (make-random-list) (+ 2 (random 98)))))

;; => #t, so all passed

=={{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.)

my $maxlen = max @ints».chars;

my @list = @ints».fmt("\%0{$maxlen}d");

}

{{out}}

<pre>-1585

=={{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.

call gen /*call subroutine to generate numbers. */

call radSort n, w /*invoke the radix sort subroutine. */

/*──────────────────────────────────────────────────────────────────────────────────────*/

show: do j=1 for n; say 'item' right(j, w) "after the radix sort:" right(@.j, w)

{{out|output|text=&nbsp; &nbsp; (with the middle section elided.)}}

=={{header|Ruby}}==

Negative number handling courtesy the Tcl solution.

def radix_sort(base=10)

ary = dup

p [170, 45, 75, 90, 2, 24, 802, 66].radix_sort

p [170, 45, 75, 90, 2, 24, -802, -66].radix_sort

running with $DEBUG on produces:

<pre>[0, [0, 0, 1, 1, 3, 6, 7, 8, 8, 9]]

another version (After sorting at the absolute value, it makes a negative order reverse.)

def radix_sort(base=10)

ary = dup

ary.partition{|n| n<0}.inject{|minus,plus| minus.reverse + plus}

end

=={{header|Rust}}==

fn merge(in1: &[i32], in2: &[i32], out: &mut [i32]) {

let (left, right) = out.split_at_mut(in1.len());

println!("After: {:?}", data);

}

{{out}}

<pre>

=={{header|Scala}}==

def sort(toBeSort: Array[Int]): Array[Int] = { // Loop for every bit in the integers

var arr = toBeSort

println(sort(Array(170, 45, 75, -90, -802, 24, 2, 66)).mkString(", "))

=={{header|Scheme}}==

;;; https://en.wikipedia.org/w/index.php?title=Radix_sort&oldid=1070890278#Least_significant_digit

(radix-sort data)

(write data)

{{out}}

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.

;;; https://en.wikipedia.org/w/index.php?title=Radix_sort&oldid=1070890278#Least_significant_digit

(radix-sort data)

(write data)

{{out}}

=={{header|Sidef}}==

{{trans|Ruby}}

method radix_sort(base=10) {

var arr = self.clone

] {

say arr.radix_sort

{{out}}

<pre>

=={{header|Tailspin}}==

templates radixsort&{base:}

sink bucketize

' -> !OUT::write

[170, 45, 75, -91, -90, -92, -802, 24, 2, 66] -> radixsort&{base:3} -> !OUT::write

{{out}}

<pre>

=={{header|Tcl}}==

{{trans|Python}}

proc splitByRadix {lst base power} {

# create a list of empty lists to hold the split by digit

}

return $lst

Demonstrations:

puts [radixSort {170 45 75 90 2 24 802 66}]

Output:

<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.

var countSort = Fn.new { |a, exp|

var n = a.count

radixSort.call(a)

System.print("Sorted : %(a)\n")

{{out}}

=={{header|zkl}}==

In place int sort, fairly light on garbage creation.

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|

}

ns

{{out}}

<pre>