Sorting algorithms/Counting sort: Difference between revisions
→{{header|360 Assembly}}: Section added
Langurmonkey (talk | contribs) |
PatGarrett (talk | contribs) (→{{header|360 Assembly}}: Section added) |
||
Line 29:
'''Note''': we know that, given an array of integers, its maximum and minimum values can be always found; but if we imagine the worst case for an array that can hold up to 32 bit integers, we see that in order to hold the counts, an array of up to '''2<sup>32</sup>''' elements may be needed. I.E.: we need to hold a count value up to '''2<sup>32</sup>-1''', which is a little over 4.2 Gbytes. So the counting sort is more practical when the range is (very) limited, and minimum and maximum values are known ''a priori''. (The use of ''sparse arrays'' minimizes the impact of the memory usage, as well as removing the need of having to know the minimum and maximum values ''a priori''.)
<br><br>
=={{header|360 Assembly}}==
<lang 360asm>* Counting sort - 18/04/2020
COUNTS CSECT
USING COUNTS,R13 base register
B 72(R15) skip savearea
DC 17F'0' savearea
SAVE (14,12) save previous context
ST R13,4(R15) link backward
ST R15,8(R13) link forward
LR R13,R15 set addressability
LA R6,A i=1
DO WHILE=(C,R6,LE,=A(N)) do i=1 to hbound(a)
L R8,0(R6) a(i)
S R8,MIN k=a(i)-min
LR R1,R8 k
SLA R1,2 ~
L R3,COUNT(R1) count(k+1)
LA R3,1(R3) +1
ST R3,COUNT(R1) count(k+1)+=1
LA R6,4(R6) i++
ENDDO , enddo i
LA R7,A j=1
L R6,MIN i=min
DO WHILE=(C,R6,LE,MAX) do i=min to max
LR R8,R6 i
S R8,MIN k=i-min
WHILEC LR R1,R8 while k
SLA R1,2 ..... ~
L R2,COUNT(R1) ..... count(k+1)
LTR R2,R2 ..... test
BNP WHENDC ..... count(k+1)>0
ST R6,0(R7) a(j)=i
LA R7,4(R7) j++
LR R1,R8 k
SLA R1,2 ~
L R3,COUNT(R1) count(k+1)
BCTR R3,0 -1
ST R3,COUNT(R1) count(k+1)-=1
B WHILEC end while
WHENDC AH R6,=H'1' i++
ENDDO , enddo i
LA R9,PG @buffer
LA R6,A i=1
DO WHILE=(C,R6,LE,=A(N)) do i=1 to hbound(a)
L R2,0(R6) a(i)
XDECO R2,XDEC edit a(i)
MVC 0(3,R9),XDEC+9 output a(i)
LA R9,3(R9) @buffer++
LA R6,4(R6) i++
ENDDO , enddo i
XPRNT PG,L'PG print buffer
L R13,4(0,R13) restore previous savearea pointer
RETURN (14,12),RC=0 restore registers from calling save
MIN DC F'-9' min
MAX DC F'99' max
A DC F'98',F'35',F'15',F'46',F'6',F'64',F'92',F'44'
DC F'53',F'21',F'56',F'74',F'13',F'11',F'92',F'70'
DC F'43',F'2',F'-7',F'89',F'22',F'82',F'41',F'91'
DC F'28',F'51',F'0',F'39',F'29',F'34',F'15',F'26'
N DC A((N-A)/L'A) hbound(a)
PG DC CL96' ' buffer
XDEC DS CL12 temp fo xdeco
COUNT DC 200F'0' count
REGEQU
END COUNTS </lang>
{{out}}
<pre>
-7 0 2 6 11 13 15 15 21 22 26 28 29 32 34 35 39 41 43 44 46 51 53 56 64 70 74 82 89 91 92 92
</pre>
=={{header|ActionScript}}==
| |||