Sorting algorithms/Radix sort: Difference between revisions

{{task|Sorting Algorithms}}

{{Sorting Algorithm}}

 

The primary purpose is to complete the characterization of sort algorithms task.

<br><br>

 

=={{header|Ada}}==

 

radix_sort.adb:

procedure Radix_Sort is

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

end loop;

Ada.Text_IO.New_Line;

 

output:

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

 

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

(

[UPB array]INT zero;

radixsort(a);

print(("After: ", a))

{{out}}

<pre>

After: +129 +160 +263 +328 +386 +459 +554 +623 +766 +941

</pre>

 

=={{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|BBC BASIC}}==

{{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++}}==

 

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

 

.

.

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

 

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

*=======================================================================

* RSORT - sort a list of integers by the Radix Sort algorithm

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:

..........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................[0, 1, 4, 5, 7, 8, 12, 14, 18, 20, 31, 33, 44, 62, 70, 73, 75, 76, 78, 81, 82, 84, 88]

..........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................[-9223372036854775808, -6755399441055744, -990, -76, 4, 12, 14, 23, 24, 38, 46, 51, 57, 57, 78, 89, 92, 97, 580, 350000, 133143986176, 26740122787512320, 9223372036854775807]

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

true

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

</pre>

 

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}

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

 

 

=={{header|NetRexx}}==

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

{{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):

"""

result = []

for b in bins:

# Make the recursive call

# Sort each of the sub-lists in our bins

 

return flattened_result

 

That same example but more compact:

 

def flatten(l):

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

bins[int(str(e).zfill(s)[i])] += [e]

 

 

=={{header|QB64}}==

#lang QB64

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

END SELECT

END SUB

 

=={{header|Racket}}==

#lang Racket

(define (radix-sort l r)

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

;; => #t, so all passed

 

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

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

gen: ILF= 0 2 3 4 5 5 7. 6 6 7 11 7 13 9 8 8 17 8 19 9 10 13 23 9 10 15 ,

end /*m*/; return /*W: is the maximum width ↑ of numbers*/

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

 

if ctr._==1 & _\=='' then do; if _<<L then L=_; if _>>H then H=_

end /* ↑↑ */

L= c2d(L); H= c2d(H); ?= ctr._ + low; top._= ?; ts= mote

max= L

if c>ts then parse value c k with ts max; ?= ?+c; top._= ?

end /*k*/

if piv>=c then leave; top._= c; ?= @.c; @.c= it; it= ?

end /*forever*/

end /*while piv<low+n */

i= max

end /*while #\==0 */

#= 0 /* [↓↓↓] handle neg. and pos. arrays. */

end /*i*/

do j=1 for size; if @.j>=0 then do; #= #+1; @@.#= @.j; end; @.j= @@.j+0

{{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|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|Sidef}}==

{{trans|Ruby}}

method radix_sort(base=10) {

var arr = self.clone

] {

say arr.radix_sort

{{out}}

<pre>

 

=={{header|Tailspin}}==

sink bucketize

def value: $;

..|@radixsort.positives: $value;

..|@radixsort.buckets($bucket): $value;

@radixsort.done: 0;

$... -> !bucketize

$@.done -> #

def previous: $@.buckets;

..|@.negatives: [];

$previous... ... -> !bucketize

end radixsort

 

'

' -> !OUT::write

'

' -> !OUT::write

'

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

2 24 45 66 75 90 170 802

-802 -66 2 24 45 75 90 170

</pre>

 

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