4 ms·

The tiniest C sort function?

19 points by amjith 17y ago

mrcharles 17y ago
But it's still a selection sort.
- ajross 17y ago
  And thus one that works fine for many uses. Most "sorting" happens (at least when measuring "most" by line of code written) because you're about to display something to the user. Using a quadratic algorithm on the few hundred entries a person can actually interpret is hardly a problem. Pick the tool for the job (though, as pointed out elsewhere, that tool should probably be a library function). Algorithmic optimization isn't always as important as your textbooks tell you it is. If I were going to nitpick about this kind of exercise, I'd pick the insanity of compressing the whitespace (and symbol naming) of the thing, which a trivial deterministic tool can do. It represents no insight on the part of the author.
  - icefox 17y ago
    Well sure, until you hit the case where two years down the road that 100 items is now 1,00,000 and if you had only used the built in function that does qsort... I would always choose a sorting function from a library over some hand grown thing (with no tests no doubt). They are too easy to make mistakes. Sorting functions are one of those things you get for free in [nearly] every language, writing a new one is usually just a waste of time.
city41 17y ago
> Use obsolescent (pre-void) syntax. (68 bytes) If memory serves, that means the method now implicitly returns int and has an implicit "return 0;" at the end. Sure the source code is smaller, but the actual machine code is larger. Going for the shortest source code is pretty silly, but then this isn't exactly a serious endeavor :)
- tedunangst 17y ago
  Implicitly returning int is not the same as implicitly returning 0. If it falls off the bottom, the return value is undefined. No additional machine code.
  - city41 17y ago
    Ah, I guess it's just main that implicitly returns 0.
    - azim 17y ago
      If memory serves correctly, I believe the typical calling convention for x86 is returning ints in %eax. So the caller will interpret whatever happens to be in %eax at the time as the return value.
jrockway 17y ago
The tiniest sort in most other languages: "sort". And it probably runs in not-O(n2) time...
- scott_s 17y ago
  C99 has a sort function that is a part of the standard library. Clearly, the point of the exercise is not calling a library function, but how most compactly one can express a sort algorithm.
  - ajross 17y ago
    Hey, cool. ANSI C89 has a sort function that is part of the standard library too! So does 3BSD! Small world. :) I'm sure qsort() is older than even 3BSD, but that's the oldest source base I have sitting on this box.
jacquesm 17y ago
If you program in this style you are simply asking for trouble. C is a great little language but I've seen it be described as a racecar. Take too many turns on two wheels and you'll end up regretting it. There is absolutely no benefit from trying to cram something like this in to two lines other than to show off your C fu, it sets a bad example and and makes for very obscure bugs. A defensive programming style with clarity in mind rather than weird little optimizations like this are a great way to get good mileage out of what is essentially a luxury assembler. The lower the level of the language you are working the more important clarity is. As soon as you start to rely on obscure language features or possibly even implementation dependent tricks you clearly no longer have the mindset required for long term maintainable code. Of course it is a fun little exercise but it really is an example of exactly how not to program in C. Incidentally, this code will only compile on C99 standard compilers and even then it will probably give you a warning or two about missing return types.
- ajross 17y ago
  Must you be so humorless? It's a clever hack, designed to show how little syntax is required to capture a given algorithm. The admonishment against programming style seems silly: no one actually does that for anything that needs to be maintained (at least no one who can write a correct selection sort). Lighten up, basically.
  - jacquesm 17y ago
    > no one actually does that for anything that needs to be maintained You wish.
petewarden 17y ago
I'm tempted to waste an afternoon to see if I can make a smaller implementation using bogosort. Shuffle the input randomly, check if it's sorted, if not, shuffle again. Hey, if we're allowed to use selection sort...
lacrossegm 17y ago
template<typename Iterator> void QuickSort(Iterator first, Iterator last) { std::sort(first, last); } // C++ > C, need to #include <algorithm> and <iterator>

19 points by amjith 17y ago

mrcharles 17y ago

But it's still a selection sort.

ajross 17y ago
And thus one that works fine for many uses. Most "sorting" happens (at least when measuring "most" by line of code written) because you're about to display something to the user. Using a quadratic algorithm on the few hundred entries a person can actually interpret is hardly a problem. Pick the tool for the job (though, as pointed out elsewhere, that tool should probably be a library function). Algorithmic optimization isn't always as important as your textbooks tell you it is. If I were going to nitpick about this kind of exercise, I'd pick the insanity of compressing the whitespace (and symbol naming) of the thing, which a trivial deterministic tool can do. It represents no insight on the part of the author.
- icefox 17y ago
  Well sure, until you hit the case where two years down the road that 100 items is now 1,00,000 and if you had only used the built in function that does qsort... I would always choose a sorting function from a library over some hand grown thing (with no tests no doubt). They are too easy to make mistakes. Sorting functions are one of those things you get for free in [nearly] every language, writing a new one is usually just a waste of time.

city41 17y ago

> Use obsolescent (pre-void) syntax. (68 bytes) If memory serves, that means the method now implicitly returns int and has an implicit "return 0;" at the end. Sure the source code is smaller, but the actual machine code is larger. Going for the shortest source code is pretty silly, but then this isn't exactly a serious endeavor :)

tedunangst 17y ago
Implicitly returning int is not the same as implicitly returning 0. If it falls off the bottom, the return value is undefined. No additional machine code.
- city41 17y ago
  Ah, I guess it's just main that implicitly returns 0.
  - azim 17y ago
    If memory serves correctly, I believe the typical calling convention for x86 is returning ints in %eax. So the caller will interpret whatever happens to be in %eax at the time as the return value.

jrockway 17y ago

The tiniest sort in most other languages: "sort". And it probably runs in not-O(n2) time...

scott_s 17y ago
C99 has a sort function that is a part of the standard library. Clearly, the point of the exercise is not calling a library function, but how most compactly one can express a sort algorithm.
- ajross 17y ago
  Hey, cool. ANSI C89 has a sort function that is part of the standard library too! So does 3BSD! Small world. :) I'm sure qsort() is older than even 3BSD, but that's the oldest source base I have sitting on this box.

jacquesm 17y ago

If you program in this style you are simply asking for trouble. C is a great little language but I've seen it be described as a racecar. Take too many turns on two wheels and you'll end up regretting it. There is absolutely no benefit from trying to cram something like this in to two lines other than to show off your C fu, it sets a bad example and and makes for very obscure bugs. A defensive programming style with clarity in mind rather than weird little optimizations like this are a great way to get good mileage out of what is essentially a luxury assembler. The lower the level of the language you are working the more important clarity is. As soon as you start to rely on obscure language features or possibly even implementation dependent tricks you clearly no longer have the mindset required for long term maintainable code. Of course it is a fun little exercise but it really is an example of exactly how not to program in C. Incidentally, this code will only compile on C99 standard compilers and even then it will probably give you a warning or two about missing return types.

ajross 17y ago
Must you be so humorless? It's a clever hack, designed to show how little syntax is required to capture a given algorithm. The admonishment against programming style seems silly: no one actually does that for anything that needs to be maintained (at least no one who can write a correct selection sort). Lighten up, basically.
- jacquesm 17y ago
  > no one actually does that for anything that needs to be maintained You wish.

petewarden 17y ago

I'm tempted to waste an afternoon to see if I can make a smaller implementation using bogosort. Shuffle the input randomly, check if it's sorted, if not, shuffle again. Hey, if we're allowed to use selection sort...

lacrossegm 17y ago

template<typename Iterator> void QuickSort(Iterator first, Iterator last) { std::sort(first, last); } // C++ > C, need to #include <algorithm> and <iterator>