|
=={{header|REXX}}==
The REXX language has the advantage of supporting sparse arrays, so implementing a bead sort is trivial, the major
<br>major drawback is ''if'' the spread (difference between the lowest and highest values) is quite large will slow up the(if display.it's
<br>greater than a few million), it'll slow up the display (but not the sorting).
Negative and duplicate integers (values) can be handled.
<lang rexx>/*REXX program sorts a list of integers using the bead sort algorithm. */
grasshopper=, /* [↑] /*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
/* Green Grocer[↑] numbers these are also called hexagonal pyramidal numbers#s. */ ▼
▲ /*Green Grocer numbers are also called hexagonal pyramidal numbers.*/
greenGrocer= 0 4 16 40 80 140 224 336 480 660 880 1144 1456 1820 2240 2720 3264 3876 4560
/*define 23twenty-three Bernoulli numerator numbers . */ ▼
bernN= '1 -1 1 0 -1 0 1 0 -1 0 5 0 -691 0 7 0 -3617 0 43867 0 -174611 0 854513' ▼▲ /*define 23 Bernoulli numerator numbers*/
/* [↑] also called the Reduced Totient function, and say; exit 13is*/▼
▲bernN= '1 -1 1 0 -1 0 1 0 -1 0 5 0 -691 0 7 0 -3617 0 43867 0 -174611 0 854513'
/*also called Carmichael lambda, or the LAMBDA function*/
psi= 1 1 2 2 4 2 6 2 6 4 10 2 12 6 4 4 16 6 18 4 6 10 22 2 20 /*Psi12 is18 also6 called28 the4 Reduced30 Totient8 function,10 and is*/16
psiy=, gHopper greenGrocer bernN psi /*alsocombine calledthe Carmichaelfour lambda,lists into or the LAMBDAone functionlist.*/
call show 'before sort', y 1 1 2 2 4 2 6 2 6 4 10 2 12 6 4 4 16 6/*display 18the 4 6list 10 22before 2sorting. 20 12 18 6 28 4 30 8 10 16*/
say copies(' ─░', 7075) /*show a long separator line before sort.*/ ▼
#=call grasshoppershow greenGrocer bernN' psiafter sort', beadSort(y) /*combinedisplay the four listslist into one listafter sorting. */
call show 'before sort', # /*display the list before sorting. */
call show ' after sort', beadSort(#) /* " " " after " */
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
beadSort: procedure; parse arg low . 1 high . 1 z,$; @.=0 /*$: the list to be sorted. */
@.=0 do j=1 until z==''; parse var z x z /*setpick allthe beadsmeat (@.)off tothe zerobone.*/
x=x/1; do j=1 until z==''; parse var z @.x=@.x+1 z /*picknormalize the meatX; off thebump bonecounter.*/
low=min(low, x); if \datatype high=max(xhigh, 'W'x) then do; say/*track lowest '***error**and highest #.*'/
say 'element' j "in list isn't numeric:" x ▼ end /* [↑] exit pgm with RC=13. */
x=x/1 /*normalize: 4. 004 +4 .4e0 */
@.x=@.x+1 /*indicate this bead has a #.*/
low=min(low,x); high=max(high,x) /*track lowest and highest #.*/
/* [↓] now, collect beads and*/
do m=low to high; do @.m; $=$ m; end /*let them fall (to zero). */
end if @.m\==0 then do n=1 for @.m; $=$ m /*have we found a bead here? m*/
end /*n*/ /* [↑] add it to sorted list*/
end /*m*/
return $
/*──────────────────────────────────────────────────────────────────────────────────────*/
show: parse arg txt,y; w=length( _=leftwords('',y) 20)
w=length(words(y)); do k=1 for words(y) /* [↑] twenty pad blanks. */
say _ right('element',30) right(k, w) txt":" right(word(y, k), 9)
end /*k*/
▲ say copies('─', 70) /*show a long separator line.*/
return</lang>
'''{{out|output''' |text= when using the default (internal) numbersinput:}}
<pre style="height:60ex"> ▼<br>(Shown at three-quarter size.)
element 1 before sort: 1 ▼
element 2 before sort: 4
▲<pre style=" font-size:75%;height: 60ex90ex">
element 3 before sort: 10
element element 4 1 before sort: 12 1
element element 5 2 before sort: 22 4
element element 63 before sort: 2610
element element 74 before sort: 3012
element element 85 before sort: 4622
element element 96 before sort: 5426
element 107 before sort: 6230
element 118 before sort: 6646
element 129 before sort: 7854
element 13element 10 before sort: 9462
element 14element 11 before sort: 110 66
element 15element 12 before sort: 126 78
element 16element 13 before sort: 134 94
element 17element 14 before sort: 138110
element 18element 15 before sort: 158126
element 19element 16 before sort: 162134
element 20element 17 before sort: 186138
element 21element 18 before sort: 190158
element 22element 19 before sort: 222162
element 23element 20 before sort: 254186
element 24element 21 before sort: 270190
element 2522 before sort: 0222
element 2623 before sort: 4254
element 27element 24 before sort: 16270
element 28element 25 before sort: 40 0
element 29element 26 before sort: 80 4
element 30element 27 before sort: 140 16
element 31element 28 before sort: 224 40
element 32element 29 before sort: 336 80
element 33element 30 before sort: 480140
element 34element 31 before sort: 660224
element 35element 32 before sort: 880336
element 36element 33 before sort: 1144 480
element 37element 34 before sort: 1456 660
element 38element 35 before sort: 1820 880
element 39element 36 before sort: 22401144
element 40element 37 before sort: 27201456
element 41element 38 before sort: 32641820
element 42element 39 before sort: 38762240
element 43element 40 before sort: 45602720
element 4441 before sort: 13264
element 4542 before sort: -13876
element 4643 before sort: 14560
element 47element 44 before sort: 01
element 48element 45 before sort: -1
element 49element 46 before sort: 01
element 50element 47 before sort: 10
element 51element 48 before sort: 0-1
element 52element 49 before sort: -1 0
element 53element 50 before sort: 01
element 54element 51 before sort: 50
element 55element 52 before sort: 0-1
element 56element 53 before sort: -691 0
element 57element 54 before sort: 05
element 58element 55 before sort: 70
element 5956 before sort: 0-691
element 60element 57 before sort: -3617 0
element 61element 58 before sort: 07
element 62element 59 before sort: 43867 0
element 6360 before sort: 0-3617
element 64element 61 before sort: -174611 0
element 6562 before sort: 043867
element 66element 63 before sort: 854513 0
element 6764 before sort: 1-174611
element 68element 65 before sort: 10
element 69element 66 before sort: 21
element 70element 67 before sort: 21
element 71element 68 before sort: 42
element 72element 69 before sort: 2
element 73element 70 before sort: 64
element 74element 71 before sort: 2
element 75element 72 before sort: 6
element 76element 73 before sort: 42
element 77element 74 before sort: 10 6
element 78element 75 before sort: 24
element 79element 76 before sort: 1210
element 80element 77 before sort: 62
element 81element 78 before sort: 412
element 82element 79 before sort: 46
element 83element 80 before sort: 16 4
element 84element 81 before sort: 64
element 85element 82 before sort: 1816
element 86element 83 before sort: 46
element 87element 84 before sort: 618
element 88element 85 before sort: 10 4
element 89element 86 before sort: 22 6
element 90element 87 before sort: 210
element 91element 88 before sort: 2022
element 92element 89 before sort: 12 2
element 93element 90 before sort: 1820
element 94element 91 before sort: 612
element 95element 92 before sort: 2818
element 96element 93 before sort: 46
element 97element 94 before sort: 3028
element 98element 95 before sort: 84
element 99element 96 before sort: 1030
element 10097 before sort: 16 8
▲ say 'element ' 98 before jsort: "in list isn't numeric:" x10
──────────────────────────────────────────────────────────────────────
element element 199 afterbefore sort: -174611 16
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
element 2 after sort: -3617
element 31 after sort: -691174611
element 42 after sort: -13617
element 53 after sort: -1691
element element 64 after sort: -1
element element 7 5 after sort: 0-1
element element 8 6 after sort: 0-1
element element 97 after sort: 0
element 108 after sort: 0
element 119 after sort: 0
element 12element 10 after sort: 0
element 13element 11 after sort: 0
element 14element 12 after sort: 0
element 15element 13 after sort: 0
element 16element 14 after sort: 0
element 17element 15 after sort: 0
element 18element 16 after sort: 10
element 19element 17 after sort: 10
element 20element 18 after sort: 1
element 21element 19 after sort: 1
element 22element 20 after sort: 1
element 23element 21 after sort: 1
element 24element 22 after sort: 21
element 25element 23 after sort: 21
element 26element 24 after sort: 2
element 27element 25 after sort: 2
element 28element 26 after sort: 2
element 29element 27 after sort: 2
element 30element 28 after sort: 42
element 31element 29 after sort: 42
element 32element 30 after sort: 4
element 33element 31 after sort: 4
element 34element 32 after sort: 4
element 35element 33 after sort: 4
element 36element 34 after sort: 4
element 37element 35 after sort: 4
element 38element 36 after sort: 54
element 39element 37 after sort: 64
element 40element 38 after sort: 65
element 41element 39 after sort: 6
element 42element 40 after sort: 6
element 43element 41 after sort: 6
element 44element 42 after sort: 6
element 45element 43 after sort: 76
element 46element 44 after sort: 86
element 47element 45 after sort: 10 7
element 48element 46 after sort: 10 8
element 49element 47 after sort: 10
element 50element 48 after sort: 10
element 51element 49 after sort: 1210
element 52element 50 after sort: 1210
element 53element 51 after sort: 12
element 54element 52 after sort: 1612
element 55element 53 after sort: 1612
element 56element 54 after sort: 16
element 57element 55 after sort: 1816
element 58element 56 after sort: 1816
element 59element 57 after sort: 2018
element 60element 58 after sort: 2218
element 61element 59 after sort: 2220
element 62element 60 after sort: 2622
element 63element 61 after sort: 2822
element 64element 62 after sort: 3026
element 65element 63 after sort: 3028
element 66element 64 after sort: 4030
element 67element 65 after sort: 4630
element 68element 66 after sort: 5440
element 69element 67 after sort: 6246
element 70element 68 after sort: 6654
element 71element 69 after sort: 7862
element 72element 70 after sort: 8066
element 73element 71 after sort: 9478
element 74element 72 after sort: 110 80
element 75element 73 after sort: 126 94
element 76element 74 after sort: 134110
element 77element 75 after sort: 138126
element 78element 76 after sort: 140134
element 79element 77 after sort: 158138
element 80element 78 after sort: 162140
element 81element 79 after sort: 186158
element 82element 80 after sort: 190162
element 83element 81 after sort: 222186
element 84element 82 after sort: 224190
element 85element 83 after sort: 254222
element 86element 84 after sort: 270224
element 87element 85 after sort: 336254
element 88element 86 after sort: 480270
element 89element 87 after sort: 660336
element 90element 88 after sort: 880480
element 91element 89 after sort: 1144 660
element 92element 90 after sort: 1456 880
element 93element 91 after sort: 18201144
element 94element 92 after sort: 22401456
element 95element 93 after sort: 27201820
element 96element 94 after sort: 32642240
element 97element 95 after sort: 38762720
element 98element 96 after sort: 45603264
element 99element 97 after sort: 43867 3876
element 10098 after sort: 854513 4560
▲ element 99 1 beforeafter sort: 143867
──────────────────────────────────────────────────────────────────────
</pre>
|