Linear time bucket sort
From Retrosoftware
m |
m |
||
| Line 45: | Line 45: | ||
LDX buckets__1 : LDY #0 : TXA : AND #1 : BEQ odd | LDX buckets__1 : LDY #0 : TXA : AND #1 : BEQ odd | ||
.reset_buckets : STY buckets,X : DEX : .odd : STY buckets,X : DEX : BPL reset_buckets | .reset_buckets : STY buckets,X : DEX : .odd : STY buckets,X : DEX : BPL reset_buckets | ||
| - | \ A= | + | \ A=? X=255 Y=0 Z=0 N=1 |
LDY count__1 | LDY count__1 | ||
.size_buckets : LDX src,Y : INC buckets,X : DEY : BPL size_buckets | .size_buckets : LDX src,Y : INC buckets,X : DEY : BPL size_buckets | ||
| - | \ A= | + | \ A=? X=? Y=255 Z=0 N=1 |
LDX buckets__1 : LDA #0 : CLC | LDX buckets__1 : LDA #0 : CLC | ||
.offset_buckets : ADC buckets,X : STA buckets,X : DEX : BPL offset_buckets | .offset_buckets : ADC buckets,X : STA buckets,X : DEX : BPL offset_buckets | ||
| Line 54: | Line 54: | ||
LDA count__1 : SEC | LDA count__1 : SEC | ||
.write_results : TAY : LDX src,Y : DEC buckets,X : LDY buckets,X : STA dst,Y : SBC #1 : BPL write_results | .write_results : TAY : LDX src,Y : DEC buckets,X : LDY buckets,X : STA dst,Y : SBC #1 : BPL write_results | ||
| - | \ X=? Y= | + | \ A=255 X=? Y=? Z=0 N=1 C=0 |
RTS | RTS | ||
] | ] | ||
Revision as of 23:27, 19 April 2011
Sample Code Library > Linear time bucket sort
Linear time bucket sort
I have been going through some of the old stuff on my BBC disks and found this - I used it for some demos to sort sprites to allow them to be rendered top-down to chase/run ahead of the raster.
It is a linear time bucket sort <60 bytes that takes <2k cycles for 32 sprites indexed by character line and <6k cycles for 128 sprites. I am happy to discuss it on the forums.
I have tidied the code and added a few lines of basic to help see how it works. I don't think I have broken it. This is the generic version, I tailored it for each demo by changing the way each bucket index is calculated eg ignoring hidden sprites when iterating the two src lists.
The algorithm is very simple and probably has a great explanation on the web now!
The fast version here only supports up to 127 numbers in up to 255 buckets - I think - anyway 32 buckets fits nicely even for BASIC use and sorting over 100 items doesn't happen very often in real time.
The fast version here will only work with the buckets in ZeroPage, but with a few more cycles per bucket and per item could be moved elsewhere. If you need to have multiple src and dst sets, you can self-mod the code (6 stores - 3 if src and dst are page aligned).
I would be happy to hear comments / improvements etc on the forums. [1]
Richard (tricky) Broadhurst.
REM sorts (descending) source data producing an index list at REM (write_results+9) in [32i + 32B] = 1932c ~ 1ms REM in: (size_buckets+1) and (write_results+1) have the source REM address written to (16bit), (written by caller) has the REM output addr written to it (16bit), REM ?count__1 = data_count-1, ?buckets__1 = bucket_count-1 REM the input data must be in the range 0 to max_buckets__1 or REM a custom version of this function will be required REM out: A=255 X=? Y=255 Z=0 N=1 C=0 : count__1 = &F8 : REM contains num to sort - 1 buckets__1 = &F9 : REM contains num buckets - 1 buckets = &70 : REM address in zp of buckets : REM B=buckets, N=numbers (20.5B + 41N + ~22) (B=32 N=128 ~ 5926) REM (32/32) RESET 250 + SIZE 482 + OFFSET 422 + WRITE 772 + RTS 6 = 1990 : DIM linear_sort 200, src 128, dst 128 FOR pass = 0 TO 3 STEP 2 P% = linear_sort [OPT pass \ use odd/even to reduce branch tests - break even B=4 faster B=6+ LDX buckets__1 : LDY #0 : TXA : AND #1 : BEQ odd .reset_buckets : STY buckets,X : DEX : .odd : STY buckets,X : DEX : BPL reset_buckets \ A=? X=255 Y=0 Z=0 N=1 LDY count__1 .size_buckets : LDX src,Y : INC buckets,X : DEY : BPL size_buckets \ A=? X=? Y=255 Z=0 N=1 LDX buckets__1 : LDA #0 : CLC .offset_buckets : ADC buckets,X : STA buckets,X : DEX : BPL offset_buckets \ A=number count X=255 Y=Y C=0 Z=0 N=1 LDA count__1 : SEC .write_results : TAY : LDX src,Y : DEC buckets,X : LDY buckets,X : STA dst,Y : SBC #1 : BPL write_results \ A=255 X=? Y=? Z=0 N=1 C=0 RTS ] PRINT P%-linear_sort NEXT pass : ?buckets__1 = 31 FOR m = 1 TO 128 ?count__1 = m-1 FOR n = 0 TO m-1 : src?n = RND AND 31 : NEXT PRINT "src: "; : FOR n = 0 TO m-1 : PRINT ;src?n;" "; : NEXT : PRINT CALL linear_sort PRINT "bkt: "; : FOR B = 0 TO 31 : PRINT ;buckets?B;" "; : NEXT : PRINT PRINT "dst: "; : FOR n = 0 TO m-1 : PRINT ;dst?n;" "; : NEXT : PRINT PRINT "ord: "; : FOR n = 0 TO m-1 : PRINT ;?(src+dst?n);" "; : NEXT : PRINT NEXT