Sorting algorithms/Bead sort: Difference between revisions
m
syntax highlighting fixup automation
(Sorting algorithms/Bead sort en FreeBASIC) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 17:
{{trans|Nim}}
<
V maxv = max(a)
V beads = [0] * (maxv * a.len)
Line 42:
V a = [5, 3, 1, 7, 4, 1, 1, 20]
bead_sort(&a)
print(a)</
{{out}}
Line 53:
For maximum compatibility, this program uses only the basic instruction set (S/360)
and two ASSIST macros (XDECO,XPRNT) to keep it as short as possible.
<
BEADSORT CSECT
USING BEADSORT,R13 base register
Line 151:
BEADS DC 4096X'00' beads
YREGS
END BEADSORT</
{{out}}
<pre>
Line 160:
=={{header|AArch64 Assembly}}==
{{works with|as|Raspberry Pi 3B version Buster 64 bits}}
<syntaxhighlight lang="aarch64 assembly">
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program beadSort64.s */
Line 396:
.include "../includeARM64.inc"
</syntaxhighlight>
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
<syntaxhighlight lang="arm assembly">
/* ARM assembly Raspberry PI */
Line 628:
.include "../affichage.inc"
</syntaxhighlight>
=={{header|Arturo}}==
<
a: new items
m: neg infinity
Line 667:
]
print beadSort [3 1 2 8 5 7 9 4 6]</
{{out}}
Line 674:
=={{header|AutoHotkey}}==
<
Pole:=[] , TempObj:=[], Result:=[]
for, i, v in data {
Line 697:
}
return Result
}</
Examples:<
res := val (res?",":"") res
MsgBox % res</
{{out}}
<pre>12,36,54,56,87</pre>
=={{header|BCPL}}==
<
let max(A, len) = valof
Line 744:
beadsort(array, length)
write("After: ", array, length)
$)</
{{out}}
<pre>Before: 10 1 5 5 9 2 20 6 8 4
Line 753:
Requires (max * length) bytes for beads; if memory is of concern, bytes can be replaced by bits.
<
#include <stdlib.h>
Line 799:
return 0;
}</
=={{header|C++}}==
<
//O(2n) time complexity where n is the summation of the whole list to be sorted.
//O(3n) space complexity.
Line 850:
for(unsigned int i=0; i<sorted.size(); i++)
cout << sorted[i] << ' ';
}</
=={{header|Clojure}}==
{{trans|Haskell}}
<
(loop [ret [], remain xs]
(if (empty? remain)
Line 870:
;; This algorithm does not work if collection has zero
(-> [5 2 4 1 3 3 9] bead-sort println)
</syntaxhighlight>
{{out}}
Line 877:
=={{header|COBOL}}==
{{works with|GnuCOBOL}}
<
*> This code is dedicated to the public domain
*> This is GNUCOBOL 2.0
Line 974:
end-perform
.
end program beadsort.</
{{out}}
Line 1,007:
=={{header|Common Lisp}}==
{{trans|Clojure}}
<
(defun transpose (remain &optional (ret '()))
(if (null remain)
Line 1,018:
(bead-sort '(5 2 4 1 3 3 9))
</syntaxhighlight>
{{out}}
<pre>(9 5 4 3 3 2 1)</pre>
Line 1,024:
=={{header|D}}==
A functional-style solution.
<
alias repeat0 = curry!(repeat, 0);
Line 1,043:
void main() {
[5, 3, 1, 7, 4, 1, 1].beadSort.writeln;
}</
{{out}}
<pre>[7, 5, 4, 3, 1, 1, 1]</pre>
Line 1,049:
=={{header|Delphi}}==
{{trans|C}}
<
{$APPTYPE CONSOLE}
Line 1,114:
readln;
end.</
--[[User:Davidizadar|DavidIzadaR]] 18:12, 7 August 2011 (UTC)
=={{header|Eiffel}}==
<syntaxhighlight lang="eiffel">
class
BEAD_SORT
Line 1,202:
end
</syntaxhighlight>
Test:
<syntaxhighlight lang="eiffel">
class
Line 1,239:
end
</syntaxhighlight>
{{out}}
<pre>
Line 1,250:
=={{header|Elixir}}==
{{trans|Erlang}}
<
def bead_sort(list) when is_list(list), do: dist(dist(list))
Line 1,259:
defp dist([], n, acc), do: dist([], n-1, [1 |acc])
defp dist([h|t], n, acc), do: dist(t, n-1, [h+1|acc])
end</
Example:
Line 1,268:
=={{header|Erlang}}==
<
-export([sort/1]).
Line 1,285:
dist(T, 0, [H | Acc]);
dist([], 0, Acc) ->
lists:reverse(Acc).</
Example;
<
[734,432,324,324,42,32,24,4,3,3,1,1,1]</
=={{header|F_Sharp|F#}}==
{{trans|Haskell}}
<
let removeEmptyLists lists = lists |> List.filter (not << List.isEmpty)
Line 1,305:
// Using the forward composition operator ">>" ...
let beadSort2 = List.map (flip List.replicate 1) >> transpose >> transpose >> List.map List.sum</
Usage: beadSort [2;4;1;3;3] or beadSort2 [2;4;1;3;3]
Line 1,314:
=={{header|Factor}}==
<
: fill ( seq len -- newseq ) [ dup length ] dip swap - 0 <repetition> append ;
Line 1,322:
[ ] [ v+ ] map-reduce ;
: beadsort ( seq -- newseq ) bead bead ;</
<
{ 9 5 4 3 3 2 1 }</
=={{header|Fortran}}==
Line 1,337:
very same code would run fine even with large integers.
<
use iso_fortran_env
! for ERROR_UNIT; to make this a F95 code,
Line 1,377:
end subroutine beadsort
end program BeadSortTest</
=={{header|FreeBASIC}}==
<
Sub beadSort(bs() As Long)
Line 1,418:
Print !"\n--- terminado, pulsa RETURN---"
Sleep</
{{out}}
<pre>unsort 5 3 1 7 4 1 1 20
Line 1,425:
=={{header|Go}}==
Sorts non-negative integers only. The extension to negative values seemed a distraction from this fun task.
<
import (
Line 1,498:
a[len(a)-1-row] = x
}
}</
=={{header|Groovy}}==
Solution:
<
final nPoles = list.max()
list.collect {
Line 1,513:
beadTally.findAll{ it }.size()
}
}</
Annotated Solution (same solution really):
<
final nPoles = list.max()
// each row is a number tally-arrayed across the abacus
Line 1,534:
def beadTalliesDrop = abacusPolesDrop.transpose()
beadTalliesDrop.collect{ beadTally -> beadTally.findAll{ it }.size() }
}</
Test:
<
println beadSort([88,18,31,44,4,0,8,81,14,78,20,76,84,33,73,75,82,5,62,70,12,7,1])</
{{out}}
Line 1,549:
=={{header|Haskell}}==
<
beadSort :: [Int] -> [Int]
beadSort = map sum. transpose. transpose. map (flip replicate 1)</
Example;
<
[4,3,3,2,1]</
=={{header|Icon}} and {{header|Unicon}}==
The program below handles integers and not just whole numbers. As are so many others, the solution is limited by the lack of sparse array or list compression.
<
write("Sorting Demo using ",image(beadsort))
writes(" on list : ")
Line 1,584:
}
return X
end</
Note: This example relies on [[Sorting_algorithms/Bubble_sort#Icon| the supporting procedures 'writex' in Bubble Sort]].
Line 1,598:
{{eff note|J|\:~}}
<
Example use:
<syntaxhighlight lang="text"> bead bead 2 4 1 3 3
4 3 3 2 1
bead bead 5 3 1 7 4 1 1
7 5 4 3 1 1 1</
Extending to deal with sequences of arbitrary integers:
<
Example use:
<syntaxhighlight lang="text"> bball 2 0 _1 3 1 _2 _3 0
3 2 1 0 0 _1 _2 _3</
=={{header|Java}}==
<syntaxhighlight lang="java">
public class BeadSort
Line 1,700:
}
}
</syntaxhighlight>
{{out}}
<pre>
Line 1,732:
'''Part 2: Gravity'''
<
def column_sums(ncols):
. as $abacus
Line 1,738:
([];
. + [reduce $abacus[] as $row
(0; if $row > $col then .+1 else . end)]) ;</
'''Part 3: read the answer in order of largest-to-smallest'''
<
def count(stream): reduce stream as $i (0; .+1);
Line 1,747:
| .[0] as $n
| reduce range(0;$n) as $i
([]; . + [count( $sums[] | select( . > $i) )]);</
'''"Bead Sort":'''
<
'''Example:'''
<
{{out}}
<
[734,432,324,324,42,32,24,4,3,3,1,1,1]</
=={{header|Julia}}==
{{works with|Julia|0.6}}
Implement <code>beadsort</code> on a <code>BitArray</code> ''abacus''. The function should work for any integer type. It throws a <code>DomainError</code> if the input array contains a non-positive integer.
<
lo, hi = extrema(a)
if lo < 1 throw(DomainError()) end
Line 1,781:
println("# unsorted bytes: $v\n -> sorted bytes: $(beadsort(v))")
v = rand(1:2 ^ 10, 20)
println("# unsorted integers: $v\n -> sorted integers: $(beadsort(v))")</
{{out}}
Line 1,791:
=={{header|Kotlin}}==
{{trans|C}}
<
fun beadSort(a: IntArray) {
Line 1,826:
beadSort(a)
println("After sorting : ${a.contentToString()}")
}</
{{out}}
Line 1,835:
=={{header|Lua}}==
<
function show (msg, t)
io.write(msg .. ":\t")
Line 1,871:
-- Main procedure
math.randomseed(os.time())
beadSort(randList(10, 1, 10))</
{{out}}
<pre>Before sort: 9 5 3 9 4 1 3 8 1 2
Line 1,878:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
sorted = a; m = Max[a]; t=ConstantArray[0, {m,m} ];
If[ Min[a] < 0, Print["can't sort"]];
Line 1,887:
Print[sorted];
]
beadsort[{2,1,5,3,6}]</
{{out}}
<pre>{6,3,2,1,0}</pre>
=={{header|NetRexx}}==
<
options replace format comments java crossref symbols nobinary
Line 1,940:
end vv
return '['list.space(1, ',')']'
</syntaxhighlight>
{{out}}
<pre>
Line 1,948:
=={{header|Nim}}==
<
var max = low(T)
var sum = 0
Line 1,977:
var a = @[5, 3, 1, 7, 4, 1, 1, 20]
beadSort a
echo a</
{{out}}
<pre>@[1, 1, 1, 3, 4, 5, 7, 20]</pre>
Line 1,983:
=={{header|OCaml}}==
{{trans|Haskell}}
<
match List.filter ((<>) []) l with
[] -> []
Line 1,991:
let bead_sort l =
List.map List.length (columns (columns (List.map (fun e -> replicate e 1) l)))</
usage
<pre>
Line 2,000:
=={{header|Octave}}==
{{trans|Fortran}}
<
sorted = a;
m = max(a);
Line 2,020:
endfunction
beadsort([5, 7, 1, 3, 1, 1, 20])</
=={{header|ooRexx}}==
===version 1===
<
Do i=1 To words(in)
z.i=word(in,i)
Line 2,070:
End
Say ol
Return </
{{out}}
<pre> Input: 10 -12 1 0 999 8 2 2 4 4
Line 2,078:
{{trans|REXX}}
'''Note:''' The only changes needed were to substitute '''<tt>_</tt>''', '''<tt>!</tt>''' and '''<tt>?</tt>''' characters for the "deprecated" <tt>'''$'''</tt>, <tt>'''#'''</tt> and '''<tt>@</tt>''' characters within variable names; as per <cite>The REXX Language, Second Edition</cite> by M. F. Cowlishaw. (See a description [http://www.rexxla.org/rexxlang/mfc/trl.html here]).
<
/*get some grassHopper numbers. */
Line 2,160:
say copies('─',80) /*show a separator line. */
return
</syntaxhighlight>
{{out}}
Line 2,370:
=={{header|OpenEdge/Progress}}==
Sorting algorithms are not the kind of thing you need / want to do in OpenEdge. If you want to sort simply define a temp-table with one field, populate it and get sorted results with FOR EACH temp-table DESCENDING.
<
i_c AS CHAR
):
Line 2,420:
"5,3,1,7,4,1,1 -> " beadSort( "5,3,1,7,4,1,1" ) SKIP(1)
beadSort( "88,18,31,44,4,0,8,81,14,78,20,76,84,33,73,75,82,5,62,70,12,7,1" )
VIEW-AS ALERT-BOX.</
{{out}}
<pre>---------------------------
Line 2,435:
=={{header|PARI/GP}}==
This implementation uses the counting sort to order the beads in a given row.
<
my(sz=vecmax(v),M=matrix(#v,sz,i,j,v[i]>=j)); \\ Set up beads
for(i=1,sz,M[,i]=countingSort(M[,i],0,1)~); \\ Let them fall
Line 2,458:
);
left
};</
=={{header|Pascal}}==
<
program BDS;
const MAX = 1000;
Line 2,560:
end.
</syntaxhighlight>
{{out}}
Line 2,577:
Instead of storing the bead matrix explicitly, I choose to store just the number of beads in each row and column, compacting on the fly. At all times, the sum of the row widths is equal to the sum column heights.
<
my @data = @_;
Line 2,593:
beadsort 5, 7, 1, 3, 1, 1, 20;
</syntaxhighlight>
=={{header|Phix}}==
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
Line 2,612:
<span style="color: #0000FF;">?</span><span style="color: #000000;">beadsort</span><span style="color: #0000FF;">({</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">7</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">20</span><span style="color: #0000FF;">})</span>
<!--</
{{out}}
<pre>
Line 2,620:
=={{header|PHP}}==
{{trans|Haskell}}
<
function columns($arr) {
if (count($arr) == 0)
Line 2,640:
print_r(beadsort(array(5,3,1,7,4,1,1)));
?></
{{out}}
Line 2,657:
The following implements a direct model of the bead sort algorithm.
Each pole is a list of 'T' symbols for the beads.
<
(let Abacus (cons NIL)
(for N Lst # Thread beads on poles
Line 2,665:
(make
(while (gt0 (cnt pop (cdr Abacus))) # Drop and count beads
(link @) ) ) ) )</
{{out}}
<pre>: (beadSort (5 3 1 7 4 1 1 20))
Line 2,672:
=={{header|PL/I}}==
===version 1===
<syntaxhighlight lang="pl/i">
/* Handles both negative and positive values. */
Line 2,745:
if offset < 0 then z = a + offset; else z = a;
end beadsort;</
===version 2===
{{trans|ooRexx}}
PL/I supports negative array indices!
<
/* Handles both negative and positive values. */
Beadsort: Proc Options(main);
Line 2,795:
End;
End;</
{{out}}
<pre> Input: 10 -12 1 0 999 8 2 2 4 4
Line 2,801:
=={{header|PowerShell}}==
<
{
if( $indata.length -gt 1 )
Line 2,840:
}
$l = 100; BeadSort ( 1..$l | ForEach-Object { $Rand = New-Object Random }{ $Rand.Next( -( $l - 1 ), $l - 1 ) } )</
=={{header|PureBasic}}==
<
Dim MyData(Random(15)+5)
Line 2,914:
Next
PrintN(#CRLF$+"And its sum= "+Str(sum))
EndProcedure</
<pre>
The array is;
Line 2,925:
=={{header|Python}}==
<
#!/bin/python3
from itertools import zip_longest
Line 2,936:
# Demonstration code:
print(beadsort([5,3,1,7,4,1,1]))
</syntaxhighlight>
{{out}}
Line 2,942:
=={{header|QB64}}==
<syntaxhighlight lang="qb64">
#lang QB64
'***************************************************
Line 3,002:
END IF
END SUB
</syntaxhighlight>
=={{header|Racket}}==
{{trans|Haskell}}
<
#lang racket
(require rackunit)
Line 3,022:
(bead-sort '(5 3 1 7 4 1 1))
'(7 5 4 3 1 1 1))
</syntaxhighlight>
=={{header|Raku}}==
Line 3,028:
{{Works with|rakudo|2016-05}}
{{trans|Haskell}}
<syntaxhighlight lang="raku"
sub transpose(@list is copy) {
gather {
Line 3,046:
my @list = 2,1,3,5;
say beadsort(@list).perl;</
{{out}}
<pre>(5, 3, 2, 1)</pre>
Here we simulate the dropping beads by using the <tt>push</tt> method.
<syntaxhighlight lang="raku"
my @rods;
for words ^«@list -> $x { @rods[$x].push(1) }
Line 3,059:
}
say beadsort 2,1,3,5;</
The <tt>^</tt> is the "upto" operator that gives a range of 0 up to (but not including) its endpoint. We use it as a hyperoperator (<tt>^«</tt>) to generate all the ranges of rod numbers we should drop a bead on, with the result that <tt>$x</tt> tells us which rod to drop each bead on. Then we use <tt>^</tt> again on the first rod to see how deep the beads are stacked, since they are guaranteed to be the deepest there. The <tt>[+]</tt> adds up all the beads that are found at level <tt>$y</tt>. The <tt>last</tt> short circuits the map so we don't have to look for all the missing beads at a given level, since the missing beads are all guaranteed to come after the existing beads at that level (because we always dropped left to right starting at rod 0).
Line 3,068:
Zero, negative, and duplicate integers (values) can be handled.
<
/* [↓] define two dozen grasshopper numbers. */
gHopper= 1 4 10 12 22 26 30 46 54 62 66 78 94 110 126 134 138 158 162 186 190 222 254 270
Line 3,097:
do k=1 for z; say right('element',30) right(k,w) txt":" right(word(y,k),9)
end /*k*/
return</
{{out|output|text= when using the default input:}}
Line 3,305:
=={{header|Ruby}}==
{{trans|Haskell}}
<
def beadsort
map {|e| [1] * e}.columns.columns.map(&:length)
Line 3,320:
# Demonstration code:
p [5,3,1,7,4,1,1].beadsort</
{{out}}
Line 3,326:
=={{header|Seed7}}==
<
const proc: beadSort (inout array integer: a) is func
Line 3,371:
end for;
writeln;
end func;</
{{out}}
Line 3,380:
=={{header|Sidef}}==
{{trans|Perl}}
<
var rows = []
Line 3,395:
}
say beadsort([5,3,1,7,4,1,1])</
{{out}}
Line 3,404:
=={{header|Standard ML}}==
{{trans|Haskell}}
<
case List.filter (not o null) l of
[] => []
Line 3,412:
fun bead_sort l =
map length (columns (columns (map (fn e => replicate (e, 1)) l)))</
usage
<pre>
Line 3,420:
=={{header|Tcl}}==
<
proc beadsort numList {
Line 3,442:
# Demonstration code
puts [beadsort {5 3 1 7 4 1 1}]</
{{out}}
<pre>7 5 4 3 1 1 1</pre>
=={{header|VBA}}==
{{trans|Phix}}<
Private Function sq_add(arr As Variant, x As Double) As Variant
Line 3,479:
Public Sub main()
Debug.Print Join(beadsort([{5, 3, 1, 7, 4, 1, 1, 20}]), ", ")
End Sub</
<pre>20, 7, 5, 4, 3, 1, 1, 1</pre>
=={{header|Wren}}==
A translation of the Python code in the Wikipedia article. Only works properly for lists of non-negative integers.
<
var res = []
var max = a.reduce { |acc, i| (i > acc) ? i : acc }
Line 3,504:
System.print("After : %(a)")
System.print()
}</
{{out}}
Line 3,516:
=={{header|XPL0}}==
<
proc BeadSort(Array, Length); \Sort Array into increasing order
Line 3,542:
BeadSort(A, 10);
for I:= 0 to 10-1 do [IntOut(0, A(I)); ChOut(0, ^ )];
]</
{{out}}
Line 3,551:
=={{header|zkl}}==
{{trans|D}}
<
m
.apply("len") // (0,0,0)-->3
Line 3,561:
fcn beadSort(data){
data.apply("pump",List,0):columns(_):columns(_).apply("len");
}</
<
T(4,3,3,2,1):beadSort(_).println();</
{{out}}
<pre>
|