Found another error on assigning space for TEMPX. Dec 13, 4:08 PST
I found an error. I forgot a loop I've fixed it.
OK. Here is the text ( corrected ) and some code I wrote. I believe it
to be bug free but one never knows with software.
If you find a bug, let me know, please?
Radix 256 Distribution Sort
allocate some page zero pointers
and temportrary TEMP of 2 bytes
Arrays needed for the data to be sorted:
allocate in RAM
Data 1Kx2 The data starts and ends here
Buff 1Kx2 This is used to hold the intermediate sort
MSBCntrPntr 256x2 bytes These locatins will be used for both
LSBCntrPntr 256x2 bytes counter and then pointers to outputs.
Set MSBCntrPntr and LSBCntrPntr to all zeros
Make one pass through the data and update counters both LSBCntrPntr
and MSBCntrPntr.
Scan each word in the DATA array. Using the LSB and the MSB
as indexes into the LSBCntrPntr and MSBCntrPntr arrays
( note these are 16 bit locations )
increment the value at that location.
Doing this for eash value from the DATA array you will now have
counter of each value of bytes in the two CntrPntr arrays.
As an example the number of LSBs that were $55 would be in the
LSBCntrPntr($55).
Now we know the distribution of the parts to sort ( hense the name ).
We will now convert the counts to address to point into the arrays
BUFF and DATA.
For each value in the LSBCntrPntr array starting at LSBCntrPntr(0),
take the count out and save it to TEMP.
Replace it with the BUFF address.
Add the value from TEMP to the address of BUFF.
For all the rest of the locations replace the value there with the
running total of counts and the address of BUFF
Repeat this for MSBCntrPntr using DATA as the first address but
start at LSBCntrPntr($80) and rap around from LSBCntrPntr($FF)
to LSBCntrPntr($00) and complete the array.
As am example: If LSBCntrPntr(0)=3, LSBCntrPntr(1)=2, LSBCntrPntr(2)=6
and the address of BUFF were $4000, the locations would be
LSBCntrPntr(0)=$4000
LSBCntrPntr(1)=$4003
LSBCntrPntr(2)=$4005
and the next total is $400B for the next cell.
We now are ready to do an insertion of the data.
Start by moving things from the DATA to the BUFF based on
the LSB of the DATA value as an index into LSBCntrPntr().
Each time you use that pointer in LSBCntrPntr(), increment
that pointer in LSBCntrPntr().
When all the values have been moved from DATA to BUFF,
repeat, the similar steps of moving by using MSBCntrPntr()
in the same way.
That is it. DATA has been sorted!
QuickSort is a knLogn while this sort is kn+c type sort.
That means that for some size of data this distribution sort
will beat QuictSort. My experience is that for sorting integers,
someplace between 30 and 100, QuickSort falls behind. The Logn
starts to dominate. For the distribution sort, the +c overhead
is constant and even though K is large, Logn, of QuickSort, catches up
and overtakes the +c.
Dwight
Code:
; I have macros to deal with short branches so I don't have
; a lot of meaninless labels.
; 'BEGIN' is a marker, useally useless label
; 'UNTIL ZERO' is the same as BNE
; 'IF CARRY' is the same as BNC
; 'ENDIF' The place the IF skips to
;
; My array pointers are split so that accessing the low and high part
; doesn't take any fiddling. The data is all normal 16 bits in two
; consecutive bytes. My pointers are the same offset in the two
; arrays so Y is always the same. It is a little confusing but I like it.
; There are several places where the code could be optimized but
; this gives one the general idea and is still quite fast.
; I've written this code without a machine to test it on but have
; made several passes through and believe it is mostly bugless.
; These arrays should all be assigned on $100 boundaries!!!!!
DATA EQU $1000 ; 1k words of unsorted data input and sorted output
BUFF EQU $1800 ; 1k words for intermediate storage
DSIZE EQU $400 ; words
; counter arrays are split for convenience
LCPLoc EQU $2000 ; LSBs counter and pointer
LCPLocH EQU $2100 ; LSBs counter and pointer high
MCPLoc EQU $2200 ; MSBs counter and pointer
MCPLocH EQU $2300 ; MSBs counter and pointer high
CNTZ EQU #100 ; number of words in pointers
; ZERO PAGE ASSIGNMENTS
$20 EQU FROMPNTR ; fetch pointer
$22 EQU TOPNTR ; to pointer for moves
$24 EQU LPNTR ; pointer to LSB counter and output pointers
$26 EQU LPNTRH
$28 EQU MPNTR ; pointer to MSB counter and output pointers
$2A EQU MPNTRH
$2C EQU PNTRL ; General purpose
$2E EQU PNTRH ; General purpose
$30 EQU TEMPY
$31 EQU TEMP ; 16 BIT IF NEEDED
$33 EQU TOTAL ; 16 BIT
$35 EQU TEMPX
; next available $36
ORG $4000
DISP_SORT
INITS
LDX # 0 ; assumes $100 aligned and consecutive
STX PNTR
LDX # LCPLocL/$100
STX PNTR+1
JSR ZEROS100
JSR ZEROS100
JSR ZEROS100
JSR ZEROS100
DOCNTS LDX # 0 ; setup from DATA as input values
STX FROMPNTR
LDY # DATA/$100
STY FROMPNTR+1
STX LPNTR
LDY # LCPLocH
STY LPNTRH
STX MPNTR
LDY # MCPLocH
STY MPNTRH
LDX DSIZE*2/$100 ; How many $80 16 bit value loops to do
CLC
LDY $0 ; is the to index
STY TEMPY
BEGIN ; needs 8 loop to do $400 words or $800
BEGIN ; Over $100 but only $80 words
CLC
LDY TEMPY ; Y is even for LSBs
LDA (FROMPNTR),Y ; first LSBs value
TAY
LDA # 1
ADC (LPNTR),Y
STA (LPNTR),Y
IF CARRY
LDA # 0
ADC (LPNTRH),Y ; notice how these arrays are split. It reduces the amount of Y fiddling
STA (LPNTRH),Y ; at no extra cost in space
ENDIF
INC TEMPY
LDY TEMPY ; Y is odd for MSBs
LDA (FROMPNTR),Y ; now MSB
TAY
LDA # 1
ADC (MPNTR),Y
STA (MPNTR),Y
IF CARRY
LDA # 0
ADC (MPNTRH),Y
STA (MPNTRH),Y
ENDIF
INC TEMPY ; Y is even
UNTIL ZER0
; ONLY DID 1/4 of DATA for each loop
INC FROMPNTR+1
DEX
UNTIL ZERO ; do the rest
; COUNTS ARE DONE
; now change the counters to pointers
CONVRT2PNTRS
; LSB counters to pointers
LDX # 0
STX PNTRL
LDY # LCPLoc/$100
STY PNTRL+1
STX PNTRH
LDY # LCPLocH/$100
STY PNTRH+1
STX TOTAL
LDY # BUFF/$100
STY TOTAL+1
LDY # 0 ; no sign offset for LSBs
JSR MKPNTR
; Now MSB counter to pointers
LDX # 0
STX PNTRL
LDY # MCPLoc/$100
STY PNTRL+1
STX PNTRH
LDY # MCPLocH/$100
STY PNTRH+1
STX TOTAL
LDY # DATA/$100
STY TOTAL+1
LDY # $80 ; does signed by starting at the center
JSR MKPNTR
; Now LCPLoc and MCPLoc have the pointers to move data.
LDX # 0
STX PNTRL
LDY # LCPLoc/$100
STY PNTRL+1
STX PNTRH
LDY # LCPLocH/$100
STY PNTRH+1
STX FROMPNTR
LDY # DATA/$100
STY FROMPNTR+1
STX TOPNTR
LDY # BUFF/$100
STY TOPNTR+1
LDY # 0 ; DATA OFFSET FOR MSB AND LSB
JSR MOVEIT
LDX # 0
STX PNTRL
LDY # MCPLoc/$100
STY PNTRL+1
STX PNTRH
LDY # MCPLocH/$100
STY PNTRH+1
STX FROMPNTR
LDY # BUFF/$100
STY FROMPNTR+1
STX TOPNTR
LDY # DATA/$100
STY TOPNTR
LDY # 1 ; DATA OFFSET FOR MSB AND LSB
JSR MOVEIT
DONE JMP DONE ; replace with RTS if called from someplace
; subroutines
MOVEIT ; used to move items from DATA to BUFF and back
LDX # DSIZE*2/$100
BEGIN ; 8 times
; FETCH POINTER AND PUT IN TOPNTR
; INCREMENT THE POINTER BY 2
; MOVE THE @ FROMPNTR TO @ TOPNTR
STX TEMPX
LDX # $80
BEGIN ; $80 times over $100 address
STY TEMPY
LDA (FROMPNTR),Y ; Y is 0 or 1 depending on LSB or MSB pointers
TAY
LDA (PNTRL),Y
STA TOPNTR
LDA (PNTRH),Y
STA TOPNTR+1
; INCREMENT THAT POINTER LOCATION BY 2
CLC
LDA (PNTRL),Y
ADC # 2 ; ALWAYS EVEN SO ONLY SECOND ADD MAKES CARRY
STA (PNTRL),Y
IF CARRY
LDA (PNTRH),Y
ADC # 0
STA (PNTRH),Y
ENDIF
; MOVE THE @ FROMPNTR TO @ TOPNTR
LDY # 0
LDA (FROMPNTR),Y
STA (TOPNTR),Y
INY
LDA (FROMPNTR),Y
STA (TOPNTR),Y
LDA FROMPNTR
ADC # 2
IF CARRY
INC FROMPNTR+1
THEN
LDY TEMPY
INX
UNTIL ZERO
LDX TEMPX
DEX
UNTIL ZERO
RTS
MKPNTR ; X IS NUMBER TO DO Y IS FIRST ADDRESS, 0 OR $80
CLC
BEGIN ; $100 times
LDA (PNTRH),Y
STA TEMP+1
LDA TOTAL+1
STA (PNTRH),Y
LDA (PNTRL),Y
STA TEMP
LDA TOTAL
STA (PNTRL),Y
ADC TEMP ; 2 TIMES VALUE IS ALWAYS EVEN
ADC TEMP ; CAN ONLY CREATE CARRY ON SECOND ADD
STA TOTAL
LDA TOTAL+1
ADC TEMP+1 ; never carries as max address is less than 64K
ADC TEMP+1 ;
STA TOTAL+1
INY
INX
UNTIL ZERO
RTS
ZEROS100 ; ZEROS $100 bytes at PNTR for begining counts
LDA # 0
TAY
BEGIN \ ASSUMES CNTZ MODULO 4 = 0
STA(PNTR),Y
INY
UNTIL ZERO
INC PNTR+1
RTS
Login
Register
FAQ
Search
