;redcode-94 ;name Consortium ;kill Consortium ;author Randy Graham ;contact hp715!rgraham@peridot.spawar.navy.mil ;NSFCWT round 4 ;assert 1 ;strategy Use an iterative (non-recursive) quicksort to sort data ;strategy Uses lg n stack space and O(n lg n) average run-time ;strategy To speed up on sorted list, do a one pass bubble. Skip ;strategy to delete routine if no swaps or qsort if there are swaps. FLAGS equ (first+4000) DATA equ (FLAGS+1) STACK equ first CLEAROUT equ fini+1 first dat.f 0, DATA ;a - stack pointer, b - end of data dat_ptr dat.f DATA, first-1 ;contains start & end of partition bubl_ptr dat.f DATA, DATA-1 bubl_new sne.i (CLEAROUT-bubl_dwn2), @(bubl_ptr-bubl_dwn2) ;first get our data list size, then sort begin seq.i CLEAROUT, @first ;once we find end, don't change it bloop jmp.a begin, >first ;bubble sort check is written assuming a decreasing sort sortbubl jmn.b bubl_dwn, FLAGS mov.x bubl_ptr, bubl_ptr ;got to change - sort increasing ptr2 mov.i bubl_new, bubl_dwn2 bubl_dwn nop.a }bubl_ptr, >bubl_ptr bubl_dwn2 sne.i CLEAROUT, *bubl_ptr ptr1 jmp.a chk_del, bubl_new ;we got here if there were no swaps slt.b @bubl_ptr, *bubl_ptr jmp_bubl jmp.a 2, 0 jmp_bubl2 jmp.a qsort, 0 sne.b @bubl_ptr, *bubl_ptr slt.a @bubl_ptr, *bubl_ptr jmp.a bubl_dwn, 0 qsort add.b first, dat_ptr qsetup mov.i dat_ptr, {first ;start our stack jmn.b sorter, FLAGS mov.x checkline check_end sne.ab checkline, counter ;make sure not at end of list jmp.a setup, >checkline check_emp sne.i CLEAROUT, *checkline ;don't compare blank lines jmp.a check_end, }checkline check_dif seq.f *checkline,chk_del ;make sure still could match jmp.a setup, >checkline seq.i *checkline,chk_del ;clear out duplicates jmp.a check_end, }checkline matches mov.i CLEAROUT, *checkline jmp.a check_end, }checkline ;now close up holes in data closedat dat.f DATA, DATA closeup sub.ab #(closedat-checkline), counter ;pointer to end chk_close sne.ab closedat, counter ;end on time at_last jmp.a fini, 0 seq.i CLEAROUT, *closedat mov.i *closedat, >closedat jmp.a chk_close, }closedat fini mov.i CLEAROUT, @closedat end begin