User Tools

Site Tools


base:flagged_bucket_sort

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Next revision
Previous revision
base:flagged_bucket_sort [2017-08-12 11:30]
shrydar created
base:flagged_bucket_sort [2017-08-13 13:39] (current)
ftc Added main heading to article
Line 1: Line 1:
 +====== Flagged Bucket Sort ======
  
 +By Christopher Jam.
  
 The following was a run at a fast worst case perfect sort, as may be useful for a bullet hell shooter or other application with fast moving sprites. The following was a run at a fast worst case perfect sort, as may be useful for a bullet hell shooter or other application with fast moving sprites.
Line 19: Line 21:
 ;; ;;
 ;; ;;
-;; Takes at most 40 rasterlines per frame for 32 sprites, regardless of movement.+;; Takes at most 38.5 rasterlines per frame for 32 sprites, regardless of movement.
 ;; ;;
-;; Intended for use in fast random movement sprite multiplexors, but use at your +;; Intended for use in fast random movement sprite multiplexors, but be aware 
-;; peril, Doynax's radix sort is about 16% faster, and probably takes less RAM +;; that Doynax's radix sort is about 12% faster, and probably takes less RAM 
-;; This was a failed attempt to do better, but I wanted to document it in case +;; This was a failed attempt to do better, but I wanted to document it in 
-;; anyone else has ideas for improvement.+;; case anyone else has ideas for improvement.
 ;; ;;
 ;; ;;
Line 113: Line 115:
  
     ldx sort_flagset+flagindex                ;     ldx sort_flagset+flagindex                ;
-    beq .noflags                              ;         6     *27+    beq .noflags                              ;              *27
 .nextflag .nextflag
  
Line 125: Line 127:
     bpl .pn                                   ;  8     bpl .pn                                   ;  8
  
-    lda#255                                   ; +    sta bucket+YBASE+flagindex*8,           ;  5
-    sta bucket+YBASE+flagindex*8,           ;  7+
 .get_remaining_flags .get_remaining_flags
     ldx least_one_cleared                     ;     ldx least_one_cleared                     ;
     bne .nextflag                             ;  6      36      *32     bne .nextflag                             ;  6      36      *32
  
-    stx sort_flagset+flagindex                ;         4        *27+    stx sort_flagset+flagindex                ;               *27
 .noflags .noflags
  
  
     }     }
-    }       ; total 27*10+32*36+(32-27)=1427=32*44.59+    }       ; total 27*8+32*34+(32-27)=1309=32*40.91
  
  
base/flagged_bucket_sort.1502530210.txt.gz · Last modified: 2017-08-12 11:30 by shrydar