Differences

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

--- base:flagged_bucket_sort [2017-08-12 11:30] – created shrydar
+++ base:flagged_bucket_sort [2017-08-13 13:39] (current) – Added main heading to article ftc
@@ 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.
@@ 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                ;
-    beq .noflags                              ;         6     *27
+    beq .noflags                              ;          5     *27
 .nextflag
@@ Line 125: / Line 127: @@
     bpl .pn                                   ;  8
-    lda#255                                   ;
+    sta bucket+YBASE+flagindex*8,y            ;  5
-    sta bucket+YBASE+flagindex*8,y            ;  7
 .get_remaining_flags
     ldx least_one_cleared                     ;
     bne .nextflag                             ;  6      36      *32
-    stx sort_flagset+flagindex                ;         4        *27
+    stx sort_flagset+flagindex                ;          3      *27
 .noflags
     }
-    }       ; total 27*10+32*36+(32-27)=1427=32*44.59
+    }       ; total 27*8+32*34+(32-27)=1309=32*40.91