We had fun last month twiddling bits in 6502 assembly, so here is another programming challenge. Write the shortest 6502 program that will sort the 256-byte table from \$1000 to \$10FF. Numbers in the table are interpreted as unsigned values from 0 to 255. The sorted table (in nondecreasing order) should be written to \$2000-20FF, with the original table still intact at \$1000-10FF. The goal is to minimize the number of bytes in the executable code, not execution speed. Paul Guertin pg@sff.net On Thu, 22 Apr 2004 22:24:07 -0400, Paul Guertin wrote: > We had fun last month twiddling bits in 6502 assembly, so here is > another programming challenge. > > Write the shortest 6502 program that will sort the 256-byte table > from \$1000 to \$10FF. Numbers in the table are interpreted as > unsigned values from 0 to 255. The sorted table (in nondecreasing > order) should be written to \$2000-20FF, with the original table > still intact at \$1000-10FF. > > The goal is to minimize the number of bytes in the executable > code, not execution speed. > > Paul Guertin > pg@sff.net Ok, here's my first entry, a selection sort, at 41 bytes: * must execute in page zero org \$b0 * copy \$1000-10ff to \$2000.\$20ff ldx #0 mov lda \$1000 dst sta (vgl+1,x) inc mov+1 inc vgl+1 bne mov * sort in place cur ldy \$2000 vgl cpy \$2000 bcc les lda (vgl+1,x) ;swap current and compare locations sta (cur+1,x) tya sta (vgl+1,x) les inc vgl+1 ;increment compare address bne cur ; and see if it is better inc cur+1 ;current location is correct so, lda cur+1 ; increment current address and copy sta vgl+1 ; into compare address for next round bne cur I hope it can be improved upon In article <38vg80l9dvp7oijp3f0opul9aguntihb43@4ax.com>, Paul Guertin wrote: >Write the shortest 6502 program that will sort the 256-byte table >from \$1000 to \$10FF. Numbers in the table are interpreted as >unsigned values from 0 to 255. The sorted table (in nondecreasing >order) should be written to \$2000-20FF, with the original table >still intact at \$1000-10FF. My entry takes 22 bytes. It also takes almost a second to run. org \$300 lda #0 ;2 tax ;1 tay ;1 Loop1 cmp \$1000,y ;3 bne Skip ;2 sta \$2000,x ;3 inx ;1 Skip iny ;1 bne Loop1 ;2 clc ;1 adc #1 ;2 bne Loop1 ;2 rts ;1 This is 4+9+9 = 22 bytes. It basically loops over all possible values 00-FF in the accumulator, looking across the whole \$1000 with a Y-loop, storing any matches to \$2000,x. So it loops over the Loop1 code 256*256 times. I calculated the run time as: (((4+3+2+3)*256 + 2+2+3)*256 + (-1+5+2)*256 + -1 + 6 = 789765 clocks. I tested the code and it seems to work, but I didn't test it much. It's along the lines of a stupid radix sort. Kent Dickey On 23 Apr 2004 21:26:28 GMT, kadickey@alumni.princeton.edu (Kent Dickey) wrote: > In article <38vg80l9dvp7oijp3f0opul9aguntihb43@4ax.com>, Paul Guertin wrote: > >Write the shortest 6502 program that will sort the 256-byte table > >from \$1000 to \$10FF. Numbers in the table are interpreted as > >unsigned values from 0 to 255. The sorted table (in nondecreasing > >order) should be written to \$2000-20FF, with the original table > >still intact at \$1000-10FF. > > My entry takes 22 bytes. It also takes almost a second to run. Almost line-for-line identical with my proposed solution, and with the same timing. Congratulations. Anyone have a better one? What if we require the sorted array to be written to \$1000-10FF, overwriting the original? It can be done trivially by adding the following 9 bytes just before the rts: loop2 lda \$2000,y sta \$1000,y iny bne loop2 for a total of 31 bytes including the rts, but I have a solution in 30 bytes. Paul Guertin pg@sff.net Sheldon Simms wrote: > On Fri, 23 Apr 2004 23:20:28 -0400, Paul Guertin wrote: > > What if we require the sorted array to be written to \$1000-10FF, > > overwriting the original? It can be done trivially > ... > > for a total of 31 bytes including the rts, but I have a > > solution in 30 bytes. > > In that case, my entry is 30 bytes when you simply delete > the lines that move \$1000-\$10ff to \$2000-\$20ff Indeed it is. Well done. Here is mine: ldx #0 ldy #0 .2 lda \$1000,x cmp \$1000,y bcc .1 pha lda \$1000,y sta \$1000,x pla sta \$1000,y .1 inx bne .2 iny bne .2 rts It can be reduced to 27 bytes by putting it in page zero and using self-mods, similar to your routine. Paul Guertin pg@sff.net