From news-rocq.inria.fr!jussieu.fr!univ-lyon1.fr!in2p3.fr!swidir.switch.ch!scsing.switch.ch!news.dfn.de!Germany.EU.net!howland.reston.ans.net!vixen.cso.uiuc.edu!newsrelay.iastate.edu!dunix.drake.edu!acad.drake.edu!pk6811s Mon Nov 6 15:09:30 1995 Article: 2804 of rec.games.corewar Path: news-rocq.inria.fr!jussieu.fr!univ-lyon1.fr!in2p3.fr!swidir.switch.ch!scsing.switch.ch!news.dfn.de!Germany.EU.net!howland.reston.ans.net!vixen.cso.uiuc.edu!newsrelay.iastate.edu!dunix.drake.edu!acad.drake.edu!pk6811s From: pk6811s@acad.drake.edu Newsgroups: rec.games.corewar Subject: Re: Sorts Date: 5 Nov 95 22:16:47 CST Organization: Drake University, Des Moines, Iowa Lines: 171 Distribution: world Message-ID: <1995Nov5.221647@acad.drake.edu> NNTP-Posting-Host: acad.drake.edu My first thought was to write a split-merge sort, mostly because I like the symmetry in the algorithm. But, like most sorts, a split- merge has a weakness for reverse-ordered lists. To overcome this a preliminary pass seemed appropriate, in which any section of reversed elements would be swapped first with last, second with next-to-last, etc. Just about the most efficient way to deal with reversed elements, and a super way to handle a completely reveresed list. So I wrote that part - about 20 lines. The split-merge proved to be a tough case, you have to keep track of several pointers and have the ability to compare pairs of elements from several different locations. Redcode's lack of true indirect addressing means you have to do a mov/add combination to create a pointer to each element before you can compare them, or have a compare routine for every combination of pointers. When I saw how big it was getting it didn't seem realistic given the competition. That was before I saw Myer's and Beppe's sorts :-) A tree-sort is another fun kind of program, which can be very fast especially when you are deleting identical elements, because you can identify and throw them out as you go, saving lots of handling time. But they are a little too complex given the time frame. So I settled on a Quick-sort. A quick-sort is basically a souped-up bubble, which we know works great for short and nearly-sorted lists, but struggles against large unordered ones. To make a bubbler quicker start by dividing the list into a lot of short ones and sort them. Say your list looks something like this: uiroew1870-5jhkl;fjf780-4321yiuoptrdhaopf7805321il;ui984793 Divide it into say, 5 lists like: (read horizontally) u w - l 7 3 u d f 3 ; 4 i 1 5 ; 8 2 o h 7 2 u 7 r 8 j f 0 1 p a 8 1 i 9 o 7 h j - y t o 0 i 9 3 e 0 k f 4 i r p 5 l 8 Now you have 5 short lists which can each be sorted very fast with the standard bubble routine. More importantly, with just a few exchanges most of the highest and lowest elements are moved to the high and low ends of the list, respectively, a feat which takes the standard bubble an enormous amount of time. >From here you could have a simple bubble routine finish the job, or, if the list was really long to start with, you might divide the list again into 2 lists taking every second element, and sort those before finishing with a bubble. In general terms, a quick-sort works thusly: 1. subdivide the list by taking every Nth element 2. sort each sublist 3. reduce N 4. if N is greater than zero, go to 1 5. when N equals zero, you are done There must be algorithms for choosing good values of N for different list sizes, but I don't remember any. My routine goes 264->64->16->4->1 by starting with 1024 and dividing by 4 each time through. It also checks first to make sure that N is not greater than the list size which would waste time. (Did anyone else include a check for list-size = zero?) Anyway, here's my sorter, which if I didn't make any stupid mistakes or assumptions about the challenge, should do all right (at least from what I've seen so far :-) 'incr' holds the N value, two instructions are modified if the sort is descending, and the flag instruction at location 4000 is used as a convenient pointer but restored at finish. Guess I didn't need that last, but too late to change it now. It never really holds the length of the list, but depends on there being dat-zeros out past the end of the last element (core-size > 4264). Using a single instruction's a/b operands to hold pointers to I and I+N elements saves a lot of messing around, since you can just add DAT N,N to get the next pair. It also makes descending sorts simple, you just MOV.X that instruction to swap pointers and run it through your regular compare routine. Improvements I did not have time to investigate are numerous :-( For example, after one bubble-pass the highest element has been moved to the end of the (sub)list and does not need to be checked again. ;redcode-94 quiet ;name PaulSort ;kill PaulSort ;author P.Kline ;contact pk6811s@acad.drake.edu ;NSFCWT Round 4 ;strategy quick-sort - step increments 256/64/16/4/1 ;strategy - skip too-large starting steps on short lists ;strategy - use same code for ascending and descending sorts ;strategy - squeeze duplicates after sorting ;strategy - use flag location as convenient pointer org start ptr equ (start+4000) ; flag used as convenient pointer saveopts equ (start+200) ; stored flag datzero equ (start+202) ; for comparison swapper equ (start+203) ; temporary storage initptr equ (start+204) ; holds current N value ; ** more data at end ** start mov ptr,saveopts ; put flag in a safe location firstinc mov incr,ptr ; div factor,ptr ; find best starting incr sne @ptr,datzero ; jmp -2 jmz.f alldone,ptr ; check for zero-length list mov ptr,incr ;****************************************************************** nextincr jmz.f postsort,incr ; when finished go to squeeze mov.b incr,srtfrom add1 add #1,srtfrom ; 1,1 operands used elsewhere srtfrom djn setptr,#0 ; select next sublist div factor,incr ; next step size N jmp nextincr setptr mov.ba srtfrom,initptr ; set ptr a/b values mov.b srtfrom,initptr ; ptr.a -> element I add.b incr ,initptr ; ptr.b -> element I+incr sub incr ,initptr ; jmz.b fwdpass,saveopts ; if descending order mov.x initptr,initptr ; swap a and b mov compinvt,compdone; adjust end-of-list check jmp fwdpass ; forward sne swapper,datzero ; if swapper is still null sortrtrn jmp srtfrom ; then sublist is sorted fwdpass mov initptr,ptr mov datzero,swapper ; set swapper to null comp add.f incr,ptr ; next pair in sublist compdone sne @ptr,datzero ; if end of sublist jmp forward ; then -> check if it is sorted slt.b @ptr,*ptr ; jmp 2 ; jmp swap ; compare two elements slt.b *ptr,@ptr ; slt.a @ptr,*ptr ; jmp comp ; swap mov @ptr,swapper ; mov *ptr,@ptr ; swap two elements and mark swapper mov swapper,*ptr ; jmp comp ; ;****************************************************************** postsort jmz.a alldone,saveopts ; if dups are allowed go to finish mov.f add1,ptr squeeze mov >ptr,*ptr ; remove duplicates sne *ptr,datzero jmp alldone ; they're gone sne *ptr,@ptr ; find 'em jmp -1,>ptr ; skip 'em jmp squeeze,}ptr ;****************************************************************** compinvt sne *ptr-compdone,datzero-compdone factor dat 4, 4 incr dat 1024,1024 alldone mov saveopts,ptr ; restore flag instruction and die BTW, everyone who writes a working program in this round deserves a big CONGRATULATIONS. This is a standard exercise which stumps even students working from textbook examples. Paul Kline pk6811s@acad.drake.edu How about a round with a limited instruction set? No ADD/SUB or no predecrement/postincrement.