;redcode-94 ;name Sort of ;author Steven Morrell ;contact morrell@math.utah.edu ;NSCWT Round 4 ;assert VERSION>=63 ;strategy Use quicksort algorithm found in K&R II, p.87 org begin data equ (first+3994) key equ (first+3995) fsame equ (first+3996) leftright equ (first+3997) ;left,right lasti equ (first+3998) ;last,i temp equ (first+3999) flag equ (first+4000) sortdata equ (first+4001) first dat sortdata-leftright,sortdata-leftright stack dat 0,-1 begin mov.f range,leftright getend seq.i data,@leftright jmp getend,>leftright nop lasti if mov.i @lasti,temp mov.i *lasti,@lasti mov.i temp,}lasti jmp loop,>lasti decrease1 slt.b key-increase1,@lasti-increase1 decrease2 slt.a key-increase2,@lasti-increase2 endloop mov.i {lasti,*leftright mov.i key,*lasti mov.a lasti,stack,leftright slt.ab leftright,leftright jmn.b pop,stack jmn.b qsort,stack jmz.a data,flag mov.i data,flag ;mark the left boundary squish mov.i *leftright,>leftright nocopy seq.f }leftright,*leftright jmp squish mov.ba leftright,fsame matches sne.i *leftright,*fsame jmp finish sne.f *leftright,{fsame jmp matches jmp squish finish seq.i *leftright,data jmp nocopy ; dat 0,0 end