From news-rocq.inria.fr!univ-lyon1.fr!in2p3.fr!oleane!jussieu.fr!math.ohio-state.edu!uwm.edu!chi-news.cic.net!newsfeed.internetmci.com!in1.uu.net!spcuna!news.stormking.com!stst@idnsun.gpct.Vanderbilt.Edu Tue Nov 7 13:40:46 1995 Article: 2815 of rec.games.corewar Path: news-rocq.inria.fr!univ-lyon1.fr!in2p3.fr!oleane!jussieu.fr!math.ohio-state.edu!uwm.edu!chi-news.cic.net!newsfeed.internetmci.com!in1.uu.net!spcuna!news.stormking.com!stst@idnsun.gpct.Vanderbilt.Edu From: stst@idnsun.gpct.Vanderbilt.Edu (Stefan Strack) Newsgroups: rec.games.corewar Subject: NSFCWT round 4: the good, the bad and the ugly Date: 6 Nov 1995 18:20:18 -0500 Organization: Storm King Ind. Inc. Lines: 363 Sender: server@news.stormking.com Distribution: world Message-ID: <9511062254.AA02816@idnsun.gpct.Vanderbilt.Edu.noname> Reply-To: stst@idnsun.gpct.Vanderbilt.Edu NNTP-Posting-Host: valhalla.stormking.com Originator: corewar-l@stormking.com Actually, it's more like the smallest, the fastest, and the best overall :-) Smallest sorter was Magnus Paulsson's "myKindOfSort" with a mere 33 instructions, which brought him up to rank 5 in the overall rating. The algorithm is bubble-sort. ;name myKindOfSort ;author Paulsson ;strategy Bubble sort, short -> fast (hopefully) ;startegy v3, works (hopefully) ;contact mpn@ifm.liu.se ;NSFCWT Round 4 org start temp equ count-2 ;temporary store eot equ count-1 ;used to get end of data count dat 4002,4001 ;counters in bubble sort. compb1 slt.b @count-comp1,*count-comp1 compb2 slt.a @count-comp2,*count-comp2 start jmz.a start2,count+4000 ;take away equals? seq.i eot,>last last jmp -1,count+4001 nop count dat 0 samei jmz.a 2,count+4000 ; check for equal seq.i @count,*count jmp next,}count mov.i Pointer, *Pointer check SEQ.f @Pointer, *Pointer JMP copy, }Pointer ; if .f!=, copy on. SNE.i last+1, @Pointer DAT #0, #0 ; if blank, finished. SNE.i @Pointer, *Pointer JMP check, >Pointer ; if .i==, nudge pointer and check next. MOV.f Pointer, Pointer+1 ; make temp pointer to possible repeats. replace SNE.i @Pointer+1, *Pointer MOV.i @Pointer, @Pointer+1 ; Replaces any subsequent .i==*Pointer with @Pointer, which ; I can deal with later. Eg 1,1 1,<1 1,1 => 1,1 1,<1 1,<1 ADD.ab #1, Pointer+1 ; Oh! The shame... SNE.f @Pointer+1, *Pointer JMP replace ; Continue replacing until no more are .f== JMP copy, }Pointer last END start ; I have made various assumptions, notably that numbers are treated ; as mod 8000, so -1 > 1 > 0 ; "start" uses flag to disable deldups and determine direction of sort. ; "findend" uses a binary search to find the first blank after the data. ; "findstep" finds a sensible step for the first pass of the Shell Sort. ; "pass" conducts one insertion-sort pass treating the data as interleaved ; lists each with spacing of Step. Each successive pass uses a smaller ; step, finishing with a plain step=1 insertion sort. ; "deldups" deletes duplicates. "copy" handles most cases, but "replace" is ; needed to deal with duplicates which are not adjacent. ; Pascal below was used to guide the sort above and explains the algorithm ; better than my comments. I like the compactness of this code; operations ; go as n^1.25 (according to Numerical Recipes, the original source) which ; by my calculation should only be 30-50% slower than n log n sorts up to ; n=1000... This program started in Fortran, was machine translated to Pascal, ; had C improvements incorporated and ended in Redcode. Unusual. program Shell5; { Sorts an array using shell algorithm as given in C version; note improved step-choice. Version 5 is modified to use red-like constructs. } uses WinCRT; CONST Start=4001; Length=19; TYPE glnarray = ARRAY [Start..Start+Length] OF extended; VAR Pass,Step,Log2Len,New,NumNews, ListEnd,LastListEnd,Old: longint; temp: extended; arr : glnarray; LABEL 3; BEGIN randomize; FOR New := Start to Start+Length do arr[New] := random; Step := 1093; repeat Step := Step div 3; { 4,13,40,121,364 are alternatives in our case. } until Step= Start) THEN GOTO 3 END END; inc(ListEnd); { loop through rest of ListEnds } until ListEnd = LastListEnd; Step := Step DIV 3; { reduce step and re-sort. } until Step = 0; FOR New := Start to Start+Length do write (arr[New]:8:4, ' '); end. Finally, overall winner of round 4 was Steven Morrell's "Sort of" which implements quick-sort (or does it?). With a length of 54 instructions and a speed index of 0.144 it scored #6 in size and #2 in speed. ;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 ------------------ Nandor & Stefan