Sorting algorithms/Bead sort: Difference between revisions

 

 

=={{header|AutoHotkey}}==

Pole:=[] , TempObj:=[], Result:=[]

for, i, v in data {

}

return Result

res := val (res?",":"") res

 

=={{header|C}}==

 

#include <stdlib.h>

 

 

return 0;

 

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

//O(2n) time complexity where n is the summation of the whole list to be sorted.

//O(3n) space complexity.

for(unsigned int i=0; i<sorted.size(); i++)

cout << sorted[i] << ' ';

 

=={{header|Clojure}}==

{{trans|Haskell}}

(loop [ret [], remain xs]

(if (empty? remain)

(defn bead-sort [xs]

(->> xs

transpose

transpose

(map #(reduce + %))))

(-> [5 2 4 1 3 3 9] bead-sort println)

 

 

 

<pre>(9 5 4 3 3 2 1)</pre>

 

=={{header|Delphi}}==

{{trans|C}}

 

{$APPTYPE CONSOLE}

 

readln;

--[[User:Davidizadar|DavidIzadaR]] 18:12, 7 August 2011 (UTC)

 

=={{header|Eiffel}}==

class

BEAD_SORT

feature

 

local

max, count, i, j, k: INTEGER

do

from

until

loop

from

until

loop

if ar.item (k) >= i then

end

end

from

until

loop

end

end

 

ensure

 

 

Test:

class

APPLICATION

create

feature

end

{{out}}

<pre>

sorted:

99 95 7 7 5 2 1

</pre>

 

=={{header|Erlang}}==

 

-export([sort/1]).

dist(T, 0, [H | Acc]);

dist([], 0, Acc) ->

Example;

 

=={{header|F_Sharp|F#}}==

{{trans|Haskell}}

 

let removeEmptyLists lists = lists |> List.filter (not << List.isEmpty)

 

// Using the forward composition operator ">>" ...

Usage: beadSort [2;4;1;3;3] or beadSort2 [2;4;1;3;3]

 

<pre>

val it : int list = [4; 3; 3; 2; 1]

 

=={{header|Factor}}==

: fill ( seq len -- newseq ) [ dup length ] dip swap - 0 <repetition> append ;

 

[ ] [ v+ ] map-reduce ;

 

 

=={{header|Fortran}}==

very same code would run fine even with large integers.

 

use iso_fortran_env

! for ERROR_UNIT; to make this a F95 code,

end subroutine beadsort

 

 

=={{header|Go}}==

Sorts non-negative integers only. The extension to negative values seemed a distraction from this fun task.

 

import (

a[len(a)-1-row] = x

}

 

=={{header|Groovy}}==

Solution:

final nPoles = list.max()

list.collect {

beadTally.findAll{ it }.size()

}

 

Annotated Solution (same solution really):

final nPoles = list.max()

// each row is a number tally-arrayed across the abacus

def beadTalliesDrop = abacusPolesDrop.transpose()

beadTalliesDrop.collect{ beadTally -> beadTally.findAll{ it }.size() }

 

Test:

 

<pre>........................................................................................................................[4, 12, 14, 23, 24, 24, 31, 35, 38, 46, 51, 57, 57, 58, 76, 78, 89, 92, 95, 97, 99]

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

 

=={{header|Haskell}}==

 

beadSort :: [Int] -> [Int]

Example;

 

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

}

return X

 

Note: This example relies on [[Sorting_algorithms/Bubble_sort#Icon| the supporting procedures 'writex' in Bubble Sort]].

Note: min and max are available in the Icon Programming Library (IPL).

 

on list : [ 3 14 1 5 9 2 6 3 ]

with op = &null: [ 1 2 3 3 5 6 9 14 ] (0 ms)</pre>

{{eff note|J|\:~}}

 

 

Example use:

 

4 3 3 2 1

bead bead 5 3 1 7 4 1 1

 

Extending to deal with sequences of arbitrary integers:

 

 

Example use:

 

 

=={{header|Java}}==

 

 

public class BeadSort

int[] beadSort(int[] arr)

{

if(arr[i]>max)

max=arr[i];

}

}

<pre>

Unsorted: 9 4 7 0 4 3 0 5 3 8 7 9 8 7 0

</pre>

 

 

sorted = a; m = Max[a]; t=ConstantArray[0, {m,m} ];

If[ Min[a] < 0, Print["can't sort"]];

For[ i = 1, i < Length[a], i++, t[[i,1;;a[[i]]]]=1 ]

For[ i = 1 ,i <= m, i++, s = Total[t[[;;,i]]];

t[[ ;; , i]] = 0; t[[1 ;; s , i]] = 1; ]

For[ i=1,i<=Length[a],i++, sorted[[i]] = Total[t[[i,;;]]]; ]

Print[sorted];

 

=={{header|NetRexx}}==

options replace format comments java crossref symbols nobinary

 

end vv

return '['list.space(1, ',')']'

<pre>

[734,3,1,24,324,-1024,-666,-1,0,324,32,0,432,42,3,4,1,1]

</pre>

 

var max = low(T)

var sum = 0

var beads = newSeq[int](max * a.len)

 

beads[i * max + j] = 1

 

sum = 0

sum += beads[i * max + j]

beads[i * max + j] = 0

 

beads[i * max + j] = 1

 

var j = 0

while j < max and beads[i * max + j] > 0: inc j

var a = @[5, 3, 1, 7, 4, 1, 1, 20]

beadSort a

<pre>@[1, 1, 1, 3, 4, 5, 7, 20]</pre>

 

=={{header|OCaml}}==

{{trans|Haskell}}

match List.filter ((<>) []) l with

[] -> []

 

let bead_sort l =

usage

<pre>

=={{header|Octave}}==

{{trans|Fortran}}

sorted = a;

m = max(a);

endfunction

 

 

=={{header|ooRexx}}==

{{trans|REXX}}

'''Note:''' The only changes needed were to substitute '''<tt>_</tt>''', '''<tt>!</tt>''' and '''<tt>?</tt>''' characters for the &quot;deprecated&quot; <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. */

say copies('─',80) /*show a separator line. */

return

 

<pre style="height:30ex;overflow:scroll">

element 1 before sort: 1

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

):

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

<pre>---------------------------

Message

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

);

left

 

=={{header|Pascal}}==

 

=={{header|Perl}}==

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 = @_;

 

 

beadsort 5, 7, 1, 3, 1, 1, 20;

 

 

=={{header|PHP}}==

{{trans|Haskell}}

function columns($arr) {

return array();

 

array_unshift($arr, NULL);

 

print_r(beadsort(array(5,3,1,7,4,1,1)));

 

<pre>Array

(

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

(make

(while (gt0 (cnt pop (cdr Abacus))) # Drop and count beads

<pre>: (beadSort (5 3 1 7 4 1 1 20))

-> (20 7 5 4 3 1 1 1)</pre>

 

=={{header|PL/I}}==

/* Handles both negative and positive values. */

 

if offset < 0 then z = a + offset; else z = a;

 

 

=={{header|PowerShell}}==

{

if( $indata.length -gt 1 )

}

 

 

=={{header|PureBasic}}==

 

Dim MyData(Random(15)+5)

Next

PrintN(#CRLF$+"And its sum= "+Str(sum))

<pre>

The array is;

 

=={{header|Python}}==

 

def beadsort(l):

 

 

# Demonstration code:

 

<pre>[7, 5, 4, 3, 1, 1, 1]</pre>

 

=={{header|Racket}}==

{{trans|Haskell}}

#lang racket

(require rackunit)

(bead-sort '(5 3 1 7 4 1 1))

'(7 5 4 3 1 1 1))

 

 

 

 

 

 

 

</pre>

 

=={{header|Ruby}}==

{{trans|Haskell}}

def beadsort

end

def columns

y = length

Array.new(x) do |row|

Array.new(y) { |column| self[column][row] }.compact # Remove nils.

 

# Demonstration code:

 

{{out}}

 

=={{header|Seed7}}==

 

const proc: beadSort (inout array integer: a) is func

for i range 1 to length(a) do

sum +:= ord(j in beads[i]);

end for;

end for;

end for;

end func;

local

var array integer: a is [] (5, 3, 1, 7, 4, 1, 1, 20);

begin

beadSort(a);

end for;

writeln;

 

{{out}}

<pre>

1 1 1 3 4 5 7 20

</pre>

 

=={{header|Standard ML}}==

{{trans|Haskell}}

case List.filter (not o null) l of

[] => []

 

fun bead_sort l =

usage

<pre>

 

=={{header|Tcl}}==

 

proc beadsort numList {

 

# Demonstration code

<pre>7 5 4 3 1 1 1</pre>

 

=={{header|XPL0}}==

 

proc BeadSort(Array, Length); \Sort Array into increasing order

BeadSort(A, 10);

for I:= 0 to 10-1 do [IntOut(0, A(I)); ChOut(0, ^ )];

 

{{out}}

0 1 1 2 3 4 5 6 9 25

</pre>

 

{{omit from|GUISS}}