The tiniest C sort function? (2008) | Hacker News Reader

The tiniest C sort function? (2008)

cs.dartmouth.edu

95 pointsrwmj25 comments

Of course this is a n^2 sort. Combinatorial Algorithms by Nijenhuis and Wilf, 1975, has a 23 lines Fortran implementation of Heapsort, a n log n sort. It is available on the web and easily found, so I am going to list it here. I am not going to attempt to convert it to C.

Note: Enjoy discriminating between the one and the lower-case l.

      subroutine hpsort(n,b)
      integer b(500),bstar
      n1=n
      l=1+n/2
   11 l=l-1
      bstar=b(l)
      goto 30
   25 bstar=b(n1)
      b(n1)=b(1)
   29 n1=n1-1
   30 l1=l
   31 m=2*l1
      if(m-n1)32,33,37
   32 if(b(m+1).ge.b(m)) m=m+1
   33 if(bstar.ge.b(m))goto 37
      b(l1)=b(m)
      l1=m
      goto 31
   37 b(l1)=bstar
      if(l.gt.1)goto 11
      if(n1.ge.2)goto 25
      return
      end

Why are only some of the lines numbered, and not all?

Because those lines are jumped to.

I might be showing my age, but we used to number the lines manually, but then we would leave gaps in case we needed to add lines in between.

I think the numbered lines are branch destinations, but I can't find a goto 29 in there.

Technically they aren’t numbered, they have a label. Labels serve as jump targets, have to appear in columns 1-5, must be numeric and all different, and should appear in order, but I don’t think they must.

(If they must, https://en.wikipedia.org/wiki/Fortran#Simple_FORTRAN_II_prog... is in error. It has label 601 follow label 799)

Of note is the statement

    if(m-n1)32,33,37

That jumps to label 32 if (m-n1) is less than zero, to label 33 if it is zero, and to label 37 if it is larger than zero.

> Of course this is a n^2 sort.

Isn't it exponential? An n element sort calls two n-1 element sorts. Each of those calls two n-2 element sorts, and so on. So you get 2^n total calls, if I'm not mistaken. That is also why the page asks if you can beat it with a function of equal length but subexponential runtime.

The following C-code heap sorts integers t[1]...t[j] in ascending order:

        for (i = j/2; j > 1; t[l] = k) {
                if (i) k = t[i--]; else { k = t[j]; t[j--] = t[1]; }
                for (l = i + 1; (m = l + l) <= j; t[l] = t[m], l = m) {
                        if (m < j && t[m] < t[m+1]) m++;
                        if (t[m] <= k) break;
                }
        }

Think of this comment what you will, but to me that is some beautiful code. I love the conciseness. Snobol is a bit like that, too. Languages today tend to be relatively verbose, but certainly not as economic nor efficient.

Ah! The return of the infamous "goes to" operator (-->)

For those unaware: https://stackoverflow.com/q/1642028/1350209

My favorite interpretation of it:

> Or for something completely different... x slides to 0.

    while (x --\
                \
                 \
                  \
                   > 0)
         printf("%d ", x);

Two small threads from 2010:

https://news.ycombinator.com/item?id=1048091

https://news.ycombinator.com/item?id=1888207

Those are both from before the final, 56-byte version was added, though I expect they probably prompted / were prompted by the addition of steps 12–19.

Just wanted to say how cool this was. It's been awhile since I've done any C/C++ programming but the pointer syntax and work really takes me back!

I wonder if you could an optimizer to find even shorter solutions. At 60 bytes, the search space is huge, but with some clever tricks, who knows...

Cool. I like the step-by-step process that's not usually shown alongside code golf and obfuscated C programs.

I had no idea Doug McIlroy had a website!

Surely we can do some sort of automated search at this point to give the shortest such program.

That would (kind of) be the Kolmogorov complexity[1] (only kind of - the Kolmogorov complexity is actually the shortest program that produces a single output, rather than the shortest program that implements an algorithm). In any case the search space is still vast: making some assumptions about the number of bits in a character of C source code, you'd be searching something like 2^(6*60) bits, a number with about 108 decimal digits. We're in "longer than the lifetime of the universe" territory here. It might be better to search C ASTs instead, although the numbers are still going to be huge.

The general field of endeavour for searching binary programs is called superoptimization[2] and people really do it for very small program fragments.

[1] https://en.wikipedia.org/wiki/Kolmogorov_complexity

[2] https://en.wikipedia.org/wiki/Superoptimization

Sleep sort would have most compact implementation while still O(n) complexity.

I thought about this more than I probably should have, and I'm fairly sure you can't pull off a C sleep sort that sorts in place and is nearly as compact as the programs in the article.

You get that sleep sort is a joke sort algorithm?

So is the exponential one in the featured article. But both do sort. If you could get a sleep sort shorter than that, that would be a nice achievement. Though I guess your original post was just a bad joke, oh well.

I’d much prefer to see people focus on tiny after compiler than tiny in source code.

Making it hard for humans to read by removing white space is fun and all, but entirely pointless to the machine.

Reply on news.ycombinator.com