Sorting algorithms/Radix sort
You are encouraged to solve this task according to the task description, using any language you may know.
Sorting Algorithm
This is a sorting algorithm. It may be applied to a set of data in order to sort it.
For comparing various sorts, see compare sorts.
For other sorting algorithms, see sorting algorithms, or:
Heap sort | Merge sort | Patience sort | Quick sort
O(n log2n) sorts
Shell Sort
O(n2) sorts
Bubble sort |
Cocktail sort |
Cocktail sort with shifting bounds |
Comb sort |
Cycle sort |
Gnome sort |
Insertion sort |
Selection sort |
Strand sort
other sorts
Bead sort |
Bogo sort |
Common sorted list |
Composite structures sort |
Custom comparator sort |
Counting sort |
Disjoint sublist sort |
External sort |
Jort sort |
Lexicographical sort |
Natural sorting |
Order by pair comparisons |
Order disjoint list items |
Order two numerical lists |
Object identifier (OID) sort |
Pancake sort |
Quickselect |
Permutation sort |
Radix sort |
Ranking methods |
Remove duplicate elements |
Sleep sort |
Stooge sort |
[Sort letters of a string] |
Three variable sort |
Topological sort |
Tree sort
In this task, the goal is to sort an integer array with the radix sort algorithm. The primary purpose is to complete the characterization of sort algorithms task.
D
<lang d>import std.stdio, std.math, std.conv, std.traits, std.range, std.algorithm ;
auto rdxsort(int N = 10 , R)(R r)
if(hasLength!R && isRandomAccessRange!R && isIntegral!(ElementType!R)) { alias ElementType!R E ;
static if(isDynamicArray!R) { writeln("input is array => in place sort") ; alias r res ; E absMax = reduce!max(map!abs(r)) ; } else { writeln("input is Range => return a newly sorted array") ; E[] res ; E absMax ;
foreach(v;r) { res ~= v ; if(absMax < abs(v)) absMax = abs(v) ; } }
immutable passes = 1 + to!int(log(absMax)/log(N)) ;
auto pBucket = new E[][](N,0) ; auto nBucket = new E[][](N,0) ;
void split(int pass) { foreach(v;res) { auto bIdx = abs(v / (N^^pass)) % N ; if(v < 0) nBucket[ bIdx ] ~= v ; else pBucket[ bIdx ] ~= v ; } }
void merge() { int idx = 0 ; foreach_reverse(ref b;nBucket) { // order revrsed for negative foreach(v;b) res[idx++] = v ; // reorder from bucket b.length = 0 ; // reset this bucket } foreach(ref b;pBucket) { foreach(v;b) res[idx++] = v ; // reorder from bucket b.length = 0 ; // reset this bucket } }
foreach(p;0..passes) { split(p) ; merge() ; }
return res ;
}
void main() {
auto a = [170, 45, 75, -90, 2, 24, -802, 66] ; writeln(rdxsort(a)) ; writeln(rdxsort(map!"1-a"(a))) ;
}</lang> Output :
input is array => in place sort [-802, -90, 2, 24, 45, 66, 75, 170] input is Range => return a newly sorted array [-169, -74, -65, -44, -23, -1, 91, 803]
J
keys f/. data
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 }.
.
<lang j>NB. queue implementation of LSB radix sort. radixSort =: 3 : 0 NB. base radixSort data 16 radixSort y
keys =. x #.^:_1 y NB. compute keys length =. {:#{.keys extra =. (x,-length) {. ,. buckets =. i.x for_pass. 0{i.-length do.
keys =. ,&:>/ (buckets,keys{~"1<pass) <@:}./.extra,keys extra =. 1 |. extra
end. x#.keys NB. restore the data )</lang>
Sort 10 small numbers in base 3.
(,: 3&radixSort) ?@#~10 1 3 8 9 0 0 8 7 1 6 0 0 1 1 3 6 7 8 8 9
Another implementation would be:
<lang j>radixsort=: (] #~ +/@([ =/ ])) i.@(>./)</lang>
Example use:
<lang j> radixsort ?.@#~10 4 5 6 6 6 6 6 8 8</lang>
Python
The wikipedia article cited in the introduction includes a python implementation of LSB radix sort.
Tcl
<lang tcl>package require Tcl 8.5 proc splitByRadix {lst base power} {
# create a list of empty lists to hold the split by digit set out [lrepeat [expr {$base*2}] {}] foreach item $lst {
# pulls the selected digit set digit [expr {($item / $base ** $power) % $base + $base * ($item >= 0)}] # append the number to the list selected by the digit lset out $digit [list {*}[lindex $out $digit] $item]
} return $out
}
- largest abs value element of a list
proc tcl::mathfunc::maxabs {lst} {
set max [abs [lindex $lst 0]] for {set i 1} {$i < [llength $lst]} {incr i} {
set v [abs [lindex $lst $i]] if {$max < $v} {set max $v}
} return $max
}
proc radixSort {lst {base 10}} {
# there are as many passes as there are digits in the longest number set passes [expr {int(log(maxabs($lst))/log($base) + 1)}] # For each pass... for {set pass 0} {$pass < $passes} {incr pass} {
# Split by radix, then merge back into the list set lst [concat {*}[splitByRadix $lst $base $pass]]
} return $lst
}</lang> Demonstrations: <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}]</lang> Output:
0 0 1 1 3 6 7 8 8 9 2 24 45 66 75 90 170 802 -802 -66 2 24 45 75 90 170