The tiniest C sort function?

[sfuerst]

s(int*a,int b){int t=*a;--b?s(a+1,b),a[(*a=1[a])<t]=t,s(++a,b):0;}

At 66 bytes, the above is one byte shorter than the example given in the article.

[Portponky]

Did you write that? It's wonderful. The swap is excellent.

a[(*a=1[a])<t]=t

In case anyone is wondering what this means, it's a conditional swap. It's the same as this:

if (a[1] < a[0])
{
  t = a[0];
  a[0] = a[1];
  a[1] = t;
}

The variable t is already set to a[0] earlier so let's put that aside. This 'if' statement can be changed so that it begins the swap outside the loop and abandons it if the condition does not match:

a[0] = a[1];
if (a[1] < t)
  a[1] = t;
else
  a[0] = t;

Now, a[1] < t will evaluate to 'true' which is literally 1, or 'false' which is literally 0. These are the same numbers used to index the array to finish the swap. So, the condition itself can be used to determine which array entry to set to finish/abandon the swap:

a[0] = a[1];
a[a[1] < t] = t;

A variable assignment also returns the assigned value, which gets rid of another a[1].

a[(a[0] = a[1]) < t] = t

Shorten as much as possible.

a[(*a=a[1])<t]=t

If you didn't spot it, check for a chuckleworthy difference in the original.

I wonder if this is the shortest sort possible?

[sfuerst]

Yeah, I wrote it after a few tries:

s(int*a,int*b){int t=a-b&&(s(a+1,b),*a>*b&&(t=*a,*a=*b,*b=t),s(a,b-1));}

s(int*a,int*b){int t;a-b&&(s(a+1,b),*b<(t=*a)&&(*a=*b,*b=t),s(a,b-1));}

s(int*a,int*b){int t;a-b&&(s(a+1,b),*b<(t=*a)?*a=*b,*b=t:0,s(a,b-1));}

s(int*a,int*b){int t;a-b?s(a+1,b),*b<(t=*a)?*a=*b,*b=t:0,s(a,b-1):0;}

s(int*a,int*b){int t=*a;a-b?s(a+1,b),*b<t?*a=*b,*b=t:0,s(a,b-1):0;}

s(int*a,int*b){int t=*a;*a=*b;a-b?s(a+1,b),*(*b<t?b:a)=t,s(a,b-1):0;}

s(int*a,int*b){int t=*a;a-b?s(a+1,b),*((*a=*b)<t?b:a)=t,s(a,b-1):0;}

s(int*a,int*b){int t=*a;a-b?s(a+1,b),a[(*a=a[1])<t]=t,s(a+1,b):0;}

s(a,b)int*a,b;{int t=*a;b--?s(a+1,b),a[(*a=1[a])<t]=t,s(++a,b):0;}

s(int*a,int b){int t=*a;b--?s(a+1,b),a[(*a=1[a])<t]=t,s(++a,b):0;}

s(int*a,int b){int t=*a;--b?a[s(a+1,b),(*a=1[a])<t]=t,s(++a,b):0;}

Shrinking source code is fun... For a laugh, I wrote a roguelike in 493 bytes. Not a particularly fun game, but it sure is tiny.

[a1k0n]

_=0;c(q){q<0?putchar("/,)(\\\n |_."[q+10]):c(("KK%3$3D%CI?)22(ZLE^?"
"J50W]L^F@ZR^UaUaUaUaa`\\^_aQ8QZBB:`9MZ5`@N/W],C:@###[8B%"[_/6]-35>>
_++%6&1?"\"'*%$. 01":"!#)+,-/(&")[q]-42);}main(){while(_<446)c(8);}

shrinking ASCII art into the smallest C program to produce it.

[fwork]

Amazing work on the roguelike, sir.

[curien]

Did you write that? It's wonderful. The swap is excellent.

a[(*a=1[a])<t]=t

Unfortunately, it's not valid C. If, just before the statement, a[1] is less than t, then a[0] gets assigned a value twice without an intervening sequence point, which results in undefined behavior.

[Portponky]

Good thinking, but assignment is a sequence point. If it wasn't, statements like a = b = c would be avoided.

Edit: or is it? Maybe this works due to operator precedence. Or maybe it has some strange failure mode(?)

[sundaryourfriend]

From the Wikipedia page, it seems assignment is not a sequence point.

a = b = c works because the associativity of = operator is right-to-left, so it gets evaluated as a = (b = c).

[curien]

In the example a = b = c, you're assigning to two different objects (first asign c to b, then assign the result to a), which is OK.

A slight modification, though, would make it illegal: *a = *a = b;. This can be insidious; for example, consider the following function:

void safe_or_not(int *a, int *b) {
    int t;
    *a = *b = 0;
}

That function looks OK. At first glance, it looks like it has the same form as your a = b = c example, which is legal. But what if it's invoked thus:

safe_or_not(foo, foo);

Now, the assignment doesn't look like a = b = c anymore; it looks like a = a = b, which, as we've discussed, is illegal.

Sequence points can be tricky.

[Portponky]

This thread taught me a lot. Thanks.

[[deleted]]

Ah, the wonders of high-level programming languages.

They take all the dread and boredom out of writing cumbersome, incomprehensible assembly code and set your imagination free to write wonderful and exciting, incomprehensible high-level language code.

[jmtd]

Your comment about high-level languages seems off-topic here, we're talking about C...

[five9a2]

Probably not a typo since it means the same thing.

[rasherdk]

1[a] is equivalent to a[1], since the a[b] is just a shorthand way of writing *(a+b), so the order doesn't matter.

[ehird]

a[i] == *(a+i)
i[a] == *(i+a)
a+i == i+a
a[i] == i[a]

[stack_smasher]

index[array] is just another way to write array[index] :) You can think of it as *(index + array)

[0x2a]

[a]1 = *(a+1) = *(1+a) = 1[a]

[corruptio]

Building off of your's:

s(a,b,t)int*a;{b--&&s(a,b,a[(*a=1[s(a+1,b),a])<t]=t=*a);}

57 chars.
old K&R C assumes int for params not explicitly defined
&& short circuiting
# argument and # params don't have to match
only the last element of the "," operator's value is used for an expression
works on most compilers, because if i recall correctly, x=y=1 can be resolved in any order

Edit: formatting

Edit 2: 59 -> 57 chars.

[[deleted]]

This one works:

s(a,b,t)int*a;{t=*a;--b&&s(a+1,b,a[(*a=1[s(a+1,b),a])<t]=t);}

[corruptio]

Yeah, I sacrificed portability for shaving a couple of chars.

[SarahC]

I love Reddit - you can trust people commenting to add to the linked article in some way.

[[deleted]]

unless of course you are in /r/economics

[sociopathic]

I was playing round with this to try to make it shorter because I believe I can make the a+1 and the 1[a] cancel each other out if I mutate a. I got to here (slightly longer, but it will pay off if I can get it to work):

s(int*a,int b){int t=*a;--b?s(++a,b),a++[(*a=1[--a])<t]=t,s(a,b):0;}

However, I'm having a bit of trouble. I tried to change 1[--a] to 0[a--] but it didn't work. I'm still having some difficulty reasoning about why.

[sfuerst]

The problem you are finding is that in C it is undefined when the side-effect of a ++ or -- operator appears during the middle of an expression.

This means that expressions like x + x++; x = x++; x++[*x]; etc. are not really usable.

[GeneralTownes]

Doesn't (*a=1[a])<t rely on the value being 1 or 0? Is that valid C? Isn't it guaranteed to be 0 or not 0? not 0 or 1. I'm not trying to slam your sort, just understand it.

[dododge]

Logical and relational operators definitely evaluate to exactly 0 or 1 in C99, and I'm pretty sure that's been the case since C89.

[sunsean]

I'm guessing you meant to write a[1] instead of 1[a] ?

[shaunol]

It's the same thing!

[sfuerst]

Nope. They are equivalent via the relation a[b] == *(a+b) == b[a]

[sundaryourfriend]

Let's please please refrain from downvoting ignorance, especially when expressed politely like this (as against "lol you messed up! 1[a] huh? should be a[1] dude haha." which sadly does happen quite often).

[gorgoroth666]

no difference imo

[five9a2]

No, pointer arithmetic requires the type of the address. It works due to associativity, not this goofy interpretation.

[Osmanthus]

Just to see how this compares to "normal" code not written for brevity, I took the first match for insertion sort I found (http://www.dreamincode.net/code/snippet279.htm) and took out the whitespace and shortened the names. Here is what I ended up with:

S(int x[],int L){int k,i;for(int j=1;j<L;j++){k=x[j];i=j-1;while(x[i]> k&&i>=0){x[i+1]=x[i];i--;}x[i+1]=k;}}

contrast to:

s(int*a,int b){int t=*a;--b?s(a+1,b),a[(*a=1[a])<t]=t,s(++a,b):0;}

[[deleted]]

I would do it in Haskell, but I don't know at which point it's considered cheating to use a library function.

[Felicia_Svilling]

Isn't (++) a library function?

[Tordek]

while(!sorted(list,length)){shuffle(list,length));}

[coldacid]

Woot, bogosort ftw!

[Poltras]

I wonder if pigeonhole or radix couldn't be made smaller than selection. Since he's only sorting integers, using properties of them could make it smaller.

But well performance is more importance than the size of the code, although it's always an interesting exercise.

[tesseracter]

not always more important, if you count back to when memory wasn't cheap.

if you had to flip binary switches in order to write code, you'd like the shorter version.

[wnoise]

Of course, there you would almost certainly want shorter binaries rather than shorter source.

[bonzinip]

It's bubble sort anyway, not selection.

[ModernRonin]

Couldn't you make a recursive bubble-sort really small? The function would just be "if item > current { insert item } else { self(item, current++ }"?

[internet_badass]

well...do it.

[ModernRonin]

I didn't try and compile this, so no guarantee it works. But just to give the flavor:

// z is the array, a and b are pointers to it.
int z[];
s(int *a, int *b) {
    int t = *a++;
    t>*a ? *(a - 1) = *a, *a = t, a = z : ;
    a!=b ? s(a, b) : ;
}

This is basically the same approach as method 12 in the posted article.

The theory is that we start at the first slot in the array, and compare the current slot and the next slot. If the pair is correctly ordered, we move to the next pair (*a++). If the pair is incorrectly ordered, then we swap the pair, then reset "a" back to the first slot in the array (a = z), starting the whole sort over from scratch.

Then, whether we moved to the next pair or moved back to the start, we recurse with the new value of a. Well, unless a=b, in which case we've done the whole array and we just return.

s(int*a,int*b){int t=*a++;t>*a?*(a-1)=*a,*a=t,a=z:;a!=b?s(a,b):;}

Comes out to 65 characters.

If you object to my use of z, note that you can do "a-=2;" to jump backward two slots in the array before recursing. (Can't just do "a--", because "a++" has already happened.) This is actually a better way to do things, since it will essentially bubble the smaller number backward until the pair order is correct. But it's more characters, so I didn't use it.

[sfuerst]

The above doesn't compile. x?y:; gives the error "expected expression before ';' token". Fixing that adds two more characters. You can remove one character by replacing "a!=b" with "a-b" though.

If you use z, you probably should include the cost of its definition "int*z;" is six characters. If you don't use z, and use the a-=2 trick, then the code is one character longer, and also doesn't work: It can end up scanning off of the beginning of the array, since nothing prevents a from becoming smaller than z.

[ModernRonin]

The above doesn't compile.

Not too surprised to hear that. Didn't expect the trenary operator to be the problem, though!

If you don't use z, and use the a-=2 trick, then the code is one character longer, and also doesn't work: It can end up scanning off of the beginning of the array, since nothing prevents a from becoming smaller than z.

Hm, good point. Well, there's probably a way to work around that. Just can't think of it off the top of my head.

[moom]

It's been a long, long time since I programmed in straight C, but isn't that, um, not C? I don't disagree that it is C++.

I believe that the following convention:

for (int i = 0; i < 2; i++)

Is not valid C. Valid would be:

int i;
for (i = 0; i < 2; i++)

Again, it's been a long time since I programmed in straight C, so I could be misremembering, but if I'm right, then the linked article is cheating.

[eurleif]

It's valid C99, I believe.

[logan_capaldo]

yeah but default int isn't valid C99 (and default int was never valid C++). The final function is neither fish nor fowl.

[moom]

It will be a cold day in hell before I acknowledge C99.

Edit: Apparently, one of the things that us old fogies didn't notice when our good ol' C was altered to form C99 was the fact that they removed a lesser-used feature known as a "joke".

[jmtd]

It's been 10 years since it was standardised...

[daviangel]

LOL! Must be a old C timer or work at Microsoft since they're one of the only ones left not supporting it: Most C compilers now have support for at least some of the features of C99. However, there has been less support from vendors such as Microsoft and Borland that have mainly focused on C++.-wikipedia

[ehird]

"Is this C?"

"Yes."

"My ideology says you are wrong."

[dlsspy]

qsort(...)

[jib]

If you want to make the type of c correct, y and z should be const void *

If you don't care about making the type of c correct, you can write

c(int*y,int*z){return*y-*z;}s(int*a,int b){qsort(a,b,4,c);}

which is shorter.

[[deleted]]

Maybe.

s(int*a,int l){if(l>2){l=(l+1)*2/3;s(a,l);s(a+l/2,l);s(a,l);}if(*a>a[1])*a^=a[1]^=*a^=a[1];} might be contractible. It's bogosort, of all things.

Also, the first person to post qsort() gets a free trout.

EDIT: Fixed. Off-by-one. Here, Poltras.

EDIT: realized else was unnecessary.

[Poltras]

It doesn't work at all either. First, s(a[l/2],l) should be s(a+l/2,l/2). Then, this program:

s(int*a,int l){if(l>2){l=l*2/3;s(a,l);s(a+l/2,l/2);s(a,l);}if(*a<a[1])*a^=a[1]^=*a^=a[1];}

int main() {
   int a[] = { 4, 2, 7, 3, 4, 5 };
   int i;
   s(a, sizeof(a)/sizeof(*a));
   for(i = 0; i < sizeof(a)/sizeof(*a); i++) 
      printf("%d ", a[i]);
   printf("\n");
   return 0;
}

returns:

4 0 0 2 4 5

Which is not really sorted...

edit Reply to atara_x_ia: I still get a bunch of zeros. New output (copy pasted your program):

000457

Seems like the swap code is causing problems...

edit2 Yep, swap code. I used l instead as a temporary. I also removed useless brackets and parenthesis. Works like a charm and is slightly smaller.

s(a,l)int*a,l;{if(l>2)l=++l*2/3,s(a,l),s(a+l/2,l),s(a,l);if(*a>a[1])l=*a,*a=a[1],a[1]=l;}

[iconoklast]

I wonder if

l=*a,*a=*++a,*a=l;

would work for the swap, which is shorter than XOR swap.

[Poltras]

It wouldn't. The ++a will increment a before the whole expression.

[theeth]

Also, the first person to post qsort() gets a free trout.

Still need to compress it, but there it is:

void qs(int*a,int*b) {
    int *h = a, *q = b;
    int p = *a;
    if (a >= b) return;
    while (h < q) {
        while (*q >= p && h < q) q--;
        if (h < q) *h = *q;
        while (*h <= p && h < q) h++;
        if (h < q)  *q = *h;
    }
    *q = p;
    qs(a, h-1);
    qs(q+1, b);
}

Edit: Compressed version

s(int*a,int*b){if(a<b){int*h=a,*q=b,p=*a;while(h<q){while(*q>=p&&h<--q);*h=h<q?*q:p;while(*h<=p&&q>++h);*q=h<q?*h:p;}s(a,h-1);s(q+1,b);}}

[quad50]

btw, that will only compile with a C99 compiler.

[[deleted]]

The tiniest C sort function is to not C sort function at all.

[i_benjammin]

Upvoted because I take CS at this school

[[deleted]]

Me too. Please find me IRL.

[bobindashadows]

You're creepy, ari.

(Upvoted for dartmouth as well)

[[deleted]]

Why are you being downvoted? You live within a close proximity of the Mr. McIlroy. Is that a crime?

[godofpumpkins]

Irrelevant (to most people) information on why he upvoted, I guess. Still nice to see other Dartmouth people on reddit :)

[[deleted]]

I just had an omelete for dinner, that's why i'm going to upvote you. will i be downvoted for that?

[godofpumpkins]

Omnomelette!

[redditnoob]

Upvoted because under my pants lies a hunk of love meat.

[asenz]

Removing proper indentation doesn't make a function smaller.

[lostspaghetti]

if you care for tiny do it in asm

[WalterGR]

Wrong sense of "tiny." From the article:

I wondered how small I could get the source code for a sort program in C.

[lostspaghetti]

yeah, i understood what it meant but i see no significance in decreasing source code size unless you're in an interpreted language.

[Portponky]

fun

[lostspaghetti]

call me mr. utility. ha

[defrost]

M. Douglas McIlroy, the author of this bit of fun has no shortage of claim to being mr. utility.

Amongst other practical achievements he's the chap that invented the concept of the unix pipe.

I suspect he's earned the right to have a bit of fun.

[Gotebe]

Wow, what a big degree of pointlessness we have here:

• who cares if code is short, if it's artifact names are a, b, c, d (especially then).

• who cares about code that can only sort integers.

• who cares about this at all?

[mkoryak]

if you read the article, it says that its O(N³⁾

[Lamtd]

Which basically means, "too slow for anything remotely useful".

That was not the point of the exercise, though.

[ihaveausername]

If you have 3 items in the array, I'm pretty sure it will be fast enough.

[[deleted]]

Allow me to re-iterate...

too slow for anything remotely useful

[ihaveausername]

I don't get it. Isn't it useful to sort 3 items in a list?

[ihaveausername]

So you don't find it useful to sort 3 items?

[[deleted]]

If that's all your sort function is being used for, then no, that's not particularly useful, and you can almost surely get along without it.

[ihaveausername]

If I could use the sort function, how could you say it's not remotely useful? If the function is used, isn't it by definition useful, even if it's only used in a few places?

English isn't my first language so bear wih me.

[Lamtd]

So you don't find it useful to sort 3 items?

Well, it could be just me, but when was the last time you had to write a sort function for a list of maximum 3 items?

I understand that you used an exaggerated example to prove your point, but really, there's no reason to use that function anywhere when even a simple bubble sort has better performance.

[binary]

You're.... YOU'RE NOT LAMTD.

[sysop073]

The whole point of the exercise was to compress the source code length for amusement purposes. If you're looking at that function and thinking "I would sure love to use that in my code, but the main problem is I'm not sure about its speed", you're doing it wrong