How to resolve the algorithm Sorting algorithms/Counting sort step by step in the 360 Assembly programming language
How to resolve the algorithm Sorting algorithms/Counting sort step by step in the 360 Assembly programming language
Table of Contents
Problem Statement
Implement the Counting sort. This is a way of sorting integers when the minimum and maximum value are known.
The min and max can be computed apart, or be known a priori.
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 232 elements may be needed. I.E.: we need to hold a count value up to 232-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. (However, as a counterexample, 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.)
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Sorting algorithms/Counting sort step by step in the 360 Assembly programming language
Source code in the 360 programming language
* 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
You may also check:How to resolve the algorithm Distributed programming step by step in the D programming language
You may also check:How to resolve the algorithm Fork step by step in the Toka programming language
You may also check:How to resolve the algorithm Binary search step by step in the CLU programming language
You may also check:How to resolve the algorithm HTTP step by step in the REALbasic programming language
You may also check:How to resolve the algorithm Floyd's triangle step by step in the OxygenBasic programming language