I wondered how small a sort program one can write in C. The best result to date, after investigating several distinctly different algorithms, tweaking a lot, and getting major help from others, is a 61-byte function at step 23. Can you beat it? Or tie it, with subexponential running time?
<big> s(a,n)int*a;{n-->1?s(a,n),s(a+1,n),n=*a,*a=a[1],a[n>*a]=n:0;} </big>
HTML warning. To preserve verbatim C source, naked > symbols have been left in function definitions instead of the proper HTML escape sequence. Internet Explorer, Safari, and Firefox tolerate the lapse.
My original intuition was that something really short would be really cryptic; and much of the code below is. But the current winner, while unconventional in using a conditional expression instead of if , is very clean, with only one deep-C trick—the conditional subscript. The code is "oblivious", doing comparisons in the same order on every input of a given length; and its running time is extraordinary!
]. Code that suffers from this defect is marked CF.
One example of what could go wrong is that if the array address a happens to be 0, then a-1 may compare high to a . However, the situation of an array being allocated at address 0 won't happen in implementations of C that take address 0 to be the null pointer. Trouble could also arise for pointers represented as base plus (nonnegative) offset.
In some cases the flaw only affects empty arrays and can be dispelled by the classic maneuver of declaring it a feature, not a bug: change the precondition to require n>0 .
<big>void sort(int*a,int n){int*b,*c,t;for(b=a+n;--b>a;) for(c=b;--c>=a;)if(*c>*b)t=*b,*b=*c,*c=t;} </big>
<big>void sort(int*a,int n){for(int*b=a+n,*c;--b>a;) for(c=b;c-->a;)if(*c>*b)n=*b,*b=*c,*c=n;} </big>
<big>void sort(int*a,int*b){for(int*c,t;--b>a;) for(c=b;c-->a;)if(*c>*b)t=*b,*b=*c,*c=t;} </big>
<big>void sort(int*a,int*b){while(--b>a) for(int*c=b,t;c-->a;)if(*c>*b)t=*b,*b=*c,*c=t;} </big>
<big>void sort(int*a,int*b){for(int*c=a,t;c-->a ||(c=--b)>a;)if(*c>*b)t=*b,*b=*c,*c=t;} </big>
<big>void sort(int*a,int*b){for(int*c=a,t;c-->a ||(c=--b)>a;)if(*c>(t=*b))*b=*c,*c=t;} </big>
<big>void sort(int*a,int*b){for(int*c=b,t;--c>a;) if(t=c[-1],t>*c)c[-1]=*c,*c=t,c=b;} </big>
<big>void s(int*a,int*b){for(int*c=b,t;--c>a;) if(t=c[-1],t>*c)c[-1]=*c,*c=t,c=b;} </big>
<big>void s(int*a,int*b){for(int*c=b,t;c>a;) if(t=*c--,*c>t)c[1]=*c,*c=t,c=b;} </big>
<big>s(a,b)int*a,*b;{for(int*c=b,t;c>a;) if(t=*c--,*c>t)c[1]=*c,*c=t,c=b;} </big>
<big>s(int*a,int*b){for(int*c=b,t;c>a;) if(t=*c--,*c>t)c[1]=*c,*c=t,c=b;} </big>
The if had no else , so the second branch ( :0 ) in the conditional is useless code. Still the trick saves a byte.
The nesting of commas illustrates an asymmetry of the two branches of a conditional: only the first can contain commas.
<big>s(int*a,int*b){for(int*c=b,t;c>a;) t=*c--,*c>t?c[1]=*c,*c=t,c=b:0;} </big>
<big>s(int*a,int*b){for(int*c=b,t;c>a; *c>t?c[1]=*c,*c=t,c=b:0)t=*c--;} </big>
<big>*c,t;s(int*a,int*b){for(c=b;c>a; *c>t?c[1]=*c,*c=t,c=b:0)t=*c--;} </big>
With two recursive calls in the body, the code may look as if its running time is O(2 ^{N} ), but more detailed analysis reveals it's O(N ^{3} ), the same as for the previous program.
Flaw: one element is accessed even if the array is empty.
<big>s(int*a,int*b){int t=*a;b>++a?s(a,b), t>*a?a[-1]=*a,*a=t,s(a,b):0:0;} </big>
<big>s(a,n,t)int*a;{t=*a++;--n?s(a,n,0), t>*a?a[-1]=*a,*a=t,s(a,n,0):0:0;} </big>
<big>s(a,n,t)int*a;{t=*a;n--?s(a+1,n,0), *a=a[1],a[t>*a]=t,s(a+1,n,0):0;} </big>
The trick was pioneered by a blog commenter who put the first recursive call in the dummy argument of the second:
s(a,n,t)int*a;{n--&&s(a,n,a[t>(*a=1[s(a+1,n),a])]=t=*a);} Alas, this valiant offering overreaches and stumbles into severely undefined behaviors: calling with the wrong number of arguments, order of side-effects in an expresssion. As the code happened to compile for me, it propagated a[n] throughout the array.
Flaw (below): accesses one element beyond end of nonempty array.<big>s(a,n,t)int*a;{n--?s(a+1,n,t=*a),s(a+1,n,a[t>(*a=a[1])]=t):0;} </big>
<big>s(a,n,t)int*a;{n-->1?s(a+1,n,t=*a),s(a+1,n,a[t>(*a=a[1])]=t):0;} </big>
<big>s(int*a,int*b){int t;if(b>a)t=*a,t>*b?*a=*b,*b=t:0, s(a++,b-1),s(a,b);} </big>
<big>s(int*a,int*b){for(int t;b>a;t>*b?*a=*b,*b=t:0,s(a++,b-1))t=*a;} </big>
<big>s(int*a,int*b){for(int t;b>a;t>*b?*a=*b,*b=t:s(a++,b-1))t=*a;} </big>
<big>s(a,n)int*a;{n-->1?s(a,n),s(a+1,n),n=*a,*a=a[1],a[n>*a]=n:0;} </big>
<big>s(*a,n){n-->1?s(a,n),s(a+1,n),n=*a,*a=a[1],a[n>*a]=n:0;} </big>
Originally written March 2008. "Recursion" section soon shortened, and corrected with regard to asymptotic running time.
Steps 12,13,14,16,17 added January 2010.
Steps 18 and 19 added October 2010.
Steps 20-23 and special treatment of "Comparison flaw" added November 2010.
Step 24 added and some words tweaked April 2017.
我来评几句
登录后评论已发表评论数()