Welcome to the MacNN Forums.

mr_sonicblue · Jan 8, 2002, 05:47 PM

Here's an tough contest:

http://harry.cciflorida.com/HTML3/ho...quicksort.html

You have to come up with one line that does all the partitioning in a quicksort function.

With all the coding styles in the world, the results should be interesting...

parallax · Jan 9, 2002, 09:20 AM

Yup, I got a solution that works (hacky, though) yesterday in a short time.

It's a fun contest, so you all should do it, especially if you're C students.

Arakageeta256 · Jan 9, 2002, 02:58 PM

...your solution is recursive, right??

parallax · Jan 9, 2002, 08:12 PM

No choice. It has to be recursive, since he gives you the other three lines.

absmiths · Jan 11, 2002, 11:47 AM

This is a typical academic excercise - yes it is challenging to create a single line which does what is needed, but the product will not be production quality (IMHO). Take a look at the GNU qsort.c definition - Quicksort that is efficient, fast, and reliable under unknown constraints (How much stack is left? How much heap is available? What tweaks can make a significant performance difference?) is no small item.

I had an instructor once who was convinced that simple recursion could solve every problem (because it is generally easier) - and he refused to consider any alternative.

BTW, the GNU qsort.c is not recursive, and with comments is 200+ lines. The Microsoft version is also non-recursive and is 300 lines (The GNU version looks cleaner to me).

A version of the GNU quick sort is here qsort.c slightly modified.

mr_sonicblue · Jan 15, 2002, 01:08 AM

Sure it's not efficient. But in working on the one-line version you discover will quite a few techniques that would greatly improve something you wrote without any constraints.

And recursion is the essential worst idea in programming ever (other than Perl's $_ variable).

But, I still think it's a fascinating problem.

lgerbarg · Jan 15, 2002, 01:20 AM

Originally posted by mr_sonicblue:
Sure it's not efficient. But in working on the one-line version you discover will quite a few techniques that would greatly improve something you wrote without any constraints.

And recursion is the essential worst idea in programming ever (other than Perl's $_ variable).

But, I still think it's a fascinating problem.

Perl has a lot of issues, though I would argue $_ is a rather minor one.

As for recursion, I am not sure how you could reach such an opinion. I really think you should read some stuff on lambda calculus and recursion theory before you make such statements. Recursion is a spectacular mechanism, especially if you understand the difference between true recursion and tail recursion, and how to use tail recursion to avoid stack growth. When I used to teach intro CS using scheme I didn't teach how to use any of the language's explicit looping constructs, and it always worked out very well ;-)

Louis

Apocalypse · Jan 15, 2002, 07:54 AM

Yeah, I tend to think that recursion is one of the best things since integrated circuits.

When I learned Scheme, for example, our instructor wouldn't even tell us if/how you could do looping. Of course, a clever recursive function in scheme is really a structure of beauty (especially when you have to use Currying, too).

I don't think that anyone should sell recursion short. The concept of a technique who's structure alone lends itself to abstraction of complicated algorithms is quite amazing. Of course, we can see that in this contest where 200 lines of code can become 4 as long as you don't have a few limitations.

Interesting challenge, though.
Jeff.

absmiths · Jan 15, 2002, 09:06 AM

Originally posted by Apocalypse:
Yeah, I tend to think that recursion is one of the best things since integrated circuits.

...

Of course, we can see that in this contest where 200 lines of code can become 4 as long as you don't have a few limitations.

Interesting challenge, though.
Jeff.

The point is that they are 4 useless lines - the limitations are that the software be applicable and functional. Do a survey of real production code (C/C++/Java) and see how much of it is true recursion. Techniques that are trendy in one language make no sense in another. Scheme may have methods for handling recursion, but tail recursion doesn't exist in C the way it does in scheme or python (unless you implement your own C compiler or do some macro funkiness - in which case you have created a bigger beast than either solution). Unless I missed something, this excercise is in C.

Lambda calculus and recursion theory don't matter much in production code. You have to get your job done and it has to be testable/verifiable/stable.

What this challenge will reinforce is that writing code like this:

<BLOCKQUOTE>code:<HR><pre>for(int i=0;i<100;i++){temp=a[i];a[i]=a[i+1];a[i+1]=temp;}[/code]

is acceptable. Techniques for cramming code onto one line are useless. Also, the instructor stressed simplicity, which is a worthy goal, but not for a general purpose sort routine. In my opinion a better excercise for young programmers would be to write a straightforward yet efficient qsort in as clear a style as possible.

parallax · Jan 15, 2002, 12:28 PM

Everyone knows that $_ is the greatest thing man created (erm, maybe not, but it sure is helpful

).

But that's the thing. This contest is obviously not designed for efficiency, but for convenience. People DO use bubble sorts in their programs when other sorts would be better, and doing a small quicksort can prove to people that they have no excuse to bubble sort again.

At any rate, this is an programming contest, not a programming exercise. I guess you guys hate the Obfuscated C contest more than anything else?

mr_sonicblue · Jan 15, 2002, 02:14 PM

Originally posted by lgerbarg:
Perl has a lot of issues, though I would argue $_ is a rather minor one.

As for recursion, I am not sure how you could reach such an opinion. I really think you should read some stuff on lambda calculus and recursion theory before you make such statements. Recursion is a spectacular mechanism, especially if you understand the difference between true recursion and tail recursion, and how to use tail recursion to avoid stack growth. When I used to teach intro CS using scheme I didn't teach how to use any of the language's explicit looping constructs, and it always worked out very well ;-)

The $_ comment was for parallax.

And I should have explained further what I meant. True recursion is fine for controlled situations. For instance, if I pack a structured file list into an XML file, it's nice to be able to recursively pass lower parts of the structure into new objects as they are created during unpacking. But, in a case where the recursion is open-ended, like in the quicksort function, you're doing nothing more than asking for your program to crash. Tail recursion, on the other hand, is simply a great solution to the problem, not part of the problem itself.

Originally posted by absmiths:
What this challenge will reinforce is that writing code like this:

...snip...

is acceptable. Techniques for cramming code onto one line are useless. Also, the instructor stressed simplicity, which is a worthy goal, but not for a general purpose sort routine. In my opinion a better excercise for young programmers would be to write a straightforward yet efficient qsort in as clear a style as possible.

Although I agree that the lines created for the quicksort function are excessive, I think that saying that code-cramming techniques are useless is terrible. The fact that all C-type expressions are evaluated into a value has some great uses:

In C:
<BLOCKQUOTE>code:<HR><pre>
a = b = c = 0;
[/code]

<BLOCKQUOTE>code:<HR><pre>
return (something ? YES : NO);
[/code]

<BLOCKQUOTE>code:<HR><pre>
a ^= b ^= a ^= b;
[/code]

In Perl/PHP:

<BLOCKQUOTE>code:<HR><pre>
print 'Hello ' . ($cfg_login ? $cfg_username : 'unregistered user') . '!';
[/code]

<BLOCKQUOTE>code:<HR><pre>
if ($my_p1 = mysql_query('select id from users')) {
[/code]