6 ms·
The tiniest C sort function? (2008)
- EliAndrewC 6y agoJust 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!
- mk_chan 6y agoAh! The return of the infamous "goes to" operator (-->)
- colejohnson66 6y agoFor those unaware: https://stackoverflow.com/q/1642028/1350209 https://stackoverflow.com/q/1642028/1350209
- gnulinux 6y agoMy favorite interpretation of it: > Or for something completely different... x slides to 0. while (x --\ \ \ \ > 0) printf("%d ", x);
- ramshorns 6y agoCool. I like the step-by-step process that's not usually shown alongside code golf and obfuscated C programs.
- dang 6y agoTwo small threads from 2010: https://news.ycombinator.com/item?id=1048091 https://news.ycombinator.com/item?id=1048091 https://news.ycombinator.com/item?id=1888207 https://news.ycombinator.com/item?id=1888207
- wizzwizz4 6y agoThose 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.
- mjcohen 6y agoOf 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
- colejohnson66 6y agoWhy are only some of the lines numbered, and not all?
- winrid 6y agoBecause those lines are jumped to.
- rileymat2 6y agoI 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.
- a1369209993 6y agoI think the numbered lines are branch destinations, but I can't find a goto 29 in there.
- Someone 6y agoTechnically 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_program 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.
- joelthelion 6y agoI 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...
- deleted 6y ago[deleted]
- deleted 6y ago[deleted]
- LifeLiverTransp 6y agoEh, you can make it tinier. Let the data be a buffer filled with x elements of random length. Let the computer be a system with multiple cores. Let the property to sort for be the length of the datums in the buffer. Each core, takes one "cycle" to process one length unit of the datum. Each core copies a "finnished" datum to a common shared pointer in a buffer. Once the buffer is completely copied, they cycle repeats, until no more elements are moved. "Ocean" sort kernel code is hyper trivial, side effect free (except for the pointer) and sorts all the "sand" by size, purely with the "data physics" properties of the system. https://github.com/PicassoCT/CompScienceExperiments/tree/master/DataPhysics https://github.com/PicassoCT/CompScienceExperiments/tree/mas... Lousy implementation and esoteric rambling about the systems properties.
- Y_Y 6y agoSurely we can do some sort of automated search at this point to give the shortest such program.
- rwmj 6y agoThat 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 https://en.wikipedia.org/wiki/Kolmogorov_complexity [2] https://en.wikipedia.org/wiki/Superoptimization https://en.wikipedia.org/wiki/Superoptimization
- akkartik 6y agoI had no idea Doug McIlroy had a website!
- lmilcin 6y agoSleep sort would have most compact implementation while still O(n) complexity.
- deleted 6y ago[deleted]
- deleted 6y ago[deleted]
- tom_mellior 6y agoI 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.
- lmilcin 6y agoYou get that sleep sort is a joke sort algorithm?
- tom_mellior 6y agoSo 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.
- SV_BubbleTime 6y agoI’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.