Page 1 of 5

1185: "Ineffective Sorts"

Posted: Wed Mar 13, 2013 4:28 pm UTC
by rhomboidal
Image

Title Text: StackSort connects to StackOverflow, searches for 'sort a list', and downloads and runs code snippets until the list is sorted.

// AT LEAST GIVE ME CREDIT FOR MY FLAWLESS INDENTATION!!

Re: 1185: "Ineffective Sorts"

Posted: Wed Mar 13, 2013 4:35 pm UTC
by snowyowl
I will buy a cookie for anyone who writes a working StackSort implementation. Two cookies if it doesn't occasionally crash my computer. Three if it occasionally crashes StackOverflow.

Re: 1185: "Ineffective Sorts"

Posted: Wed Mar 13, 2013 4:36 pm UTC
by player_03
So I looked up "Bogosort" on Wikipedia and found this:

An in-joke among some computer scientists is that quantum computing could be used to effectively implement a bogosort with a time complexity of O(n). It uses true quantum randomness to randomly permute the list. The list is then inspected, and if it is not in order, the universe is destroyed. By the many-worlds interpretation of quantum physics, the quantum randomization spawns 2^N (where N is the number of random bits) universes and one of these will be such that this single shuffle had produced the list in sorted order.


(Emphasis mine.)

And here I thought shutting down and wiping the computer was an overreaction...

Re: 1185: "Ineffective Sorts"

Posted: Wed Mar 13, 2013 4:37 pm UTC
by Gargravarr
FastBogoSort made me LOL. So brutal, yet strangely elegant.

The correct answer to JobInterviewQuickSort() is, of course:
std::sort(l.begin(), l.end());

If the interviewer asks if you even remember the QuickSort algorith, answer that you'd rather not waste the employer's resources by reinventing the wheel. Because that's the sort of responsible programmer you are.

Re: 1185: "Ineffective Sorts"

Posted: Wed Mar 13, 2013 4:41 pm UTC
by tibfulv
Ok, so this is why Munroe was sacked from NASA. This explains so much! :twisted: Also, the panicsort is evil. Very evil.

Afterthought: Which language is that? I don't recognise it.

Re: 1185: "Ineffective Sorts"

Posted: Wed Mar 13, 2013 4:51 pm UTC
by Gargravarr
tibfulv wrote:Afterthought: Which language is that? I don't recognise it.

Half-forgotten Python?

Re: 1185: "Ineffective Sorts"

Posted: Wed Mar 13, 2013 4:53 pm UTC
by creaothceann
// THIS CAN'T BE HAPPENING

Not if your list isn't modified by another thread/process.

Re: 1185: "Ineffective Sorts"

Posted: Wed Mar 13, 2013 5:08 pm UTC
by peewee_RotA
creaothceann wrote:
// THIS CAN'T BE HAPPENING

Not if your list isn't modified by another thread/process.

But it's clearly not locking before accessing the data. Probably a crash here.

Plus this is probably a scripting language. More likely that this thing will learn to operate a loom than work with threads.

Re: 1185: "Ineffective Sorts"

Posted: Wed Mar 13, 2013 5:10 pm UTC
by ahammel
It's pseudocode.

Re: 1185: "Ineffective Sorts"

Posted: Wed Mar 13, 2013 5:13 pm UTC
by jc
Some years back, perhaps in the 1980s, there was a competition for the "worst" sort algorithm. They were careful to state that 1) the sort had to actually work, 2) speed was measured only by operation count, and 3) "irrelevant" time wasting or sabotage instructions weren't allowed (since we all know how to write a cpu-eating busy loop). I.e., everything in the code had to contribute to improving the sort order. Some of the algorithms were truly incredible, and really, really slow. I wonder if there's an archive of this lying about somewhere ...

Re: 1185: "Ineffective Sorts"

Posted: Wed Mar 13, 2013 5:15 pm UTC
by Isaac5
I am not a big enough nerd for this webcomic. I have no idea what any of this is.

*hangs head in shame*

Re: 1185: "Ineffective Sorts"

Posted: Wed Mar 13, 2013 5:19 pm UTC
by NeatNit
Isaac5 wrote:I am not a big enough nerd for this webcomic. I have no idea what any of this is.

*hangs head in shame*

I literally could not stop laughing. You don't belong here.

:P

Re: 1185: "Ineffective Sorts"

Posted: Wed Mar 13, 2013 5:20 pm UTC
by Ehsanit
I wonder for what kind of list length Panic Sort would actually return the correct list.
It's basically a bogosort, but it "cuts" instead of "shuffles" the deck at each iteration. I imagine that the average case running time would still be n!, so it should handle 7 elements correctly more often than it goes psycho.

Re: 1185: "Ineffective Sorts"

Posted: Wed Mar 13, 2013 5:22 pm UTC
by Max2009
I laughed out loud and got well-deserved strange looks.

Also, my brain segfaulted on the PanicSort. RM -RF is not valid.

Re: 1185: "Ineffective Sorts"

Posted: Wed Mar 13, 2013 5:22 pm UTC
by Isaac5
NeatNit wrote:
Isaac5 wrote:I am not a big enough nerd for this webcomic. I have no idea what any of this is.

*hangs head in shame*

I literally could not stop laughing. You don't belong here.

:P

I'm nerdier than a lot of people and I understand I large portion of xkcd's but... I have no idea what is going on right now.

I'll go cry in the corner.

Re: 1185: "Ineffective Sorts"

Posted: Wed Mar 13, 2013 5:24 pm UTC
by EverVigilant
I don't get the halfhearted mergesort one. I mean, he's forgetting to include the pivot (unless it's implicitly included in either PIVOT: or :PIVOT but not both; I am not familiar with that syntax). Is that it?

Re: 1185: "Ineffective Sorts"

Posted: Wed Mar 13, 2013 5:24 pm UTC
by tibfulv
Isaac5 wrote:I am not a big enough nerd for this webcomic. I have no idea what any of this is.

*hangs head in shame*


It's a programming joke. See Algorithm on Wikipedia. See also Sorting algorithm, and know that the object of inventing them is to make the quickest one possible. People have been joking about making inefficient sorts for a long time, Bogosort being the most famous one.

Also: Read on. Farther down in the algorithms, he's doing things that no one sorting should be doing.

Re: 1185: "Ineffective Sorts"

Posted: Wed Mar 13, 2013 5:25 pm UTC
by Ehsanit
Isaac5 wrote:I'm nerdier than a lot of people and I understand I large portion of xkcd's but... I have no idea what is going on right now.

I'll go cry in the corner.

Mr. Munroe is just trying to increase the stock of code that doesn't work on the internet.

Re: 1185: "Ineffective Sorts"

Posted: Wed Mar 13, 2013 5:26 pm UTC
by ahammel
EverVigilant wrote:I don't get the halfhearted mergesort one. I mean, he's forgetting to include the pivot (unless it's implicitly included in either PIVOT: or :PIVOT but not both; I am not familiar with that syntax). Is that it?

Also: it doesn't sort anything.

Re: 1185: "Ineffective Sorts"

Posted: Wed Mar 13, 2013 5:28 pm UTC
by Velo Steve
FastBogoSort was definitely my favorite, but I had a problem with PanicSort. I don't know the DOS command line very well any more, so I just typed RD /S /Q C:\* on my pc to see what would happen.

What now? I'm typing this from my tablet, of course.

Re: 1185: "Ineffective Sorts"

Posted: Wed Mar 13, 2013 5:29 pm UTC
by Gargravarr
jc wrote:Some years back, perhaps in the 1980s, there was a competition for the "worst" sort algorithm. They were careful to state that 1) the sort had to actually work, 2) speed was measured only by operation count, and 3) "irrelevant" time wasting or sabotage instructions weren't allowed (since we all know how to write a cpu-eating busy loop). I.e., everything in the code had to contribute to improving the sort order. Some of the algorithms were truly incredible, and really, really slow. I wonder if there's an archive of this lying about somewhere ...

Please let us know if you remember the winner.
The worst one I've ever used in production code is BubbleSort. Because the boss liked it for some obcure reason.

Re: 1185: "Ineffective Sorts"

Posted: Wed Mar 13, 2013 5:30 pm UTC
by Jofur
ahammel wrote:It's pseudocode.


I like you. You get it. :P

Re: 1185: "Ineffective Sorts"

Posted: Wed Mar 13, 2013 5:30 pm UTC
by orthogon
Ehsanit wrote:
Isaac5 wrote:I'm nerdier than a lot of people and I understand I large portion of xkcd's but... I have no idea what is going on right now.

I'll go cry in the corner.

Mr. Munroe is just trying to increase the stock of code that doesn't work on the internet.

... thus reducing the effectiveness of his own "stacksort" algorithm.

Especially if stacksort alights on stacksort as a candidate, leading to the recursive stacksort.

Re: 1185: "Ineffective Sorts"

Posted: Wed Mar 13, 2013 5:31 pm UTC
by RogueCynic
ahammel wrote:It's pseudocode.
The last panel has linux commands. Of course, starting with shutdown -h +5 would shut the computer down, losing the rest of the commands.

Re: 1185: "Ineffective Sorts"

Posted: Wed Mar 13, 2013 5:33 pm UTC
by tibfulv
EverVigilant wrote:I don't get the halfhearted mergesort one. I mean, he's forgetting to include the pivot (unless it's implicitly included in either PIVOT: or :PIVOT but not both; I am not familiar with that syntax). Is that it?


I think the colon is supposed to mean something like "less than"/"up to" and so on, and the calls are recursive. They are usually non-intuitive, and require a lot of thinking*) to figure out what they do. A major way to obfuscate your code, and therefore hugely popular.


*) Forgot this, which made the sentence a bit odd. I'll forget my own head next ....

Re: 1185: "Ineffective Sorts"

Posted: Wed Mar 13, 2013 5:35 pm UTC
by teelo

Code: Select all

DEFINE SandwichSort (List, boolean hasSU):
    if (!hasSU) return "What? Sort it yourself.";
    return "Okay.";

Re: 1185: "Ineffective Sorts"

Posted: Wed Mar 13, 2013 5:36 pm UTC
by tibfulv
RogueCynic wrote:
ahammel wrote:It's pseudocode.
The last panel has linux commands. Of course, starting with shutdown -h +5 would shut the computer down, losing the rest of the commands.


Technically, it waits for five minutes first, and in fact has to be scheduled first, since once the disk is clean, there would be no shutdown command.

Re: 1185: "Ineffective Sorts"

Posted: Wed Mar 13, 2013 5:37 pm UTC
by teelo
[:PIVOT] means passing in an array spliced from index 0 through to PIVOT. Synonym for [0:PIVOT].
[PIVOT:] means PIVOT to the end.

Re: 1185: "Ineffective Sorts"

Posted: Wed Mar 13, 2013 5:51 pm UTC
by dash
Fellow named Ron Hunsinger and I were talking once, he told me about an argument he'd had with some young punk about how with the ever increasing power of computer hardware there was no need to write efficient code.

Ron told him that he could devise algorithms that were so bad they'd bring any conceivable hardware to its knees. Then he started to list some of them. Here's one he told me about:

Sorting a list:
1) Is the list already sorted? If so, quit, you're done
2) Randomly exchange 2 elements in the list
3) Go to step 1

It can be proven that this WILL sort the list. But it might take a very long time...

Funny rebuttal to Ron's argument. Another of his "algorithms" was a method for drawing a line:
1) For every pixel on the display, check if the pixel is along the line from P1 to P2. If it is, draw a dot, otherwise do nothing.

And strangely enough, that's exactly the approach used in GPU's, when you can program the shaders and you have massive computational power to burn...

Shader sandbox link:
http://glsl.heroku.com/

Re: 1185: "Ineffective Sorts"

Posted: Wed Mar 13, 2013 6:02 pm UTC
by TexasToast
tibfulv wrote:
RogueCynic wrote:
ahammel wrote:It's pseudocode.
The last panel has linux commands. Of course, starting with shutdown -h +5 would shut the computer down, losing the rest of the commands.


Technically, it waits for five minutes first, and in fact has to be scheduled first, since once the disk is clean, there would be no shutdown command.

Really? Make your own sandwich. http://xkcd.com/149/

Re: 1185: "Ineffective Sorts"

Posted: Wed Mar 13, 2013 6:03 pm UTC
by mrob27
jc wrote:Some years back, perhaps in the 1980s, there was a competition for the "worst" sort algorithm. They were careful to state that 1) the sort had to actually work, 2) speed was measured only by operation count, and 3) "irrelevant" time wasting or sabotage instructions weren't allowed (since we all know how to write a cpu-eating busy loop). I.e., everything in the code had to contribute to improving the sort order. Some of the algorithms were truly incredible, and really, really slow. I wonder if there's an archive of this lying about somewhere ...


Good search words to use for this are "pessimal sorting algorithm competition". I found "Inefficient sort algorithms" by Richard Harter:

http://richardhartersworld.com/cri_d/cri/2001/badsort.html

The "evil sort" by Carl Howells (at the bottom of the page) is O((n^2)!).

For a 1984 example, see "Pessimal Algorithms and Simplexity Analysis" by Broder and Stolfi:

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.116.9158

which presents a "slowsort" with the note "One of the most important results of modern simplexity theory is the proof that the sorting problem can be solved in Ω(n^log(n)/(2+ε)) time"...

Re: 1185: "Ineffective Sorts"

Posted: Wed Mar 13, 2013 6:03 pm UTC
by sep332
ahammel wrote:It's pseudocode.

Funny. It's basically Python: no semicolons, no variable type declarations, slice syntax for lists, and no parens after the "for" keyword. There's a joke that Python is just runnable pseudocode. Oddly, the code here uses C-style // comments instead of pythonic # comments.

Re: 1185: "Ineffective Sorts"

Posted: Wed Mar 13, 2013 6:04 pm UTC
by TexasToast
Velo Steve wrote:FastBogoSort was definitely my favorite, but I had a problem with PanicSort. I don't know the DOS command line very well any more, so I just typed RD /S /Q C:\* on my pc to see what would happen.

What now? I'm typing this from my tablet, of course.

Install Linux. http://xkcd.com/456/

Re: 1185: "Ineffective Sorts"

Posted: Wed Mar 13, 2013 6:07 pm UTC
by SamSam
dash wrote:Ron told him that he could devise algorithms that were so bad they'd bring any conceivable hardware to its knees. Then he started to list some of them. Here's one he told me about:

Sorting a list:
1) Is the list already sorted? If so, quit, you're done
2) Randomly exchange 2 elements in the list
3) Go to step 1


That's pretty much exactly what Randall's FastBogoSort is doing (swapping two random elements is essentially the same as shuffling), except that Randall's is "fast" because he only tries it a few times, and if it hasn't worked yet he gives up and throws a kernel fault.

Re: 1185: "Ineffective Sorts"

Posted: Wed Mar 13, 2013 6:09 pm UTC
by Gargravarr
sep332 wrote:
ahammel wrote:It's pseudocode.

Funny. It's basically Python: no semicolons, no variable type declarations, slice syntax for lists, and no parens after the "for" keyword. There's a joke that Python is just runnable pseudocode. Oddly, the code here uses C-style // comments instead of pythonic # comments.

I'm still looking forward to an XKCD comic written entirely in BrainF*ck. Not even Googleable.

Re: 1185: "Ineffective Sorts"

Posted: Wed Mar 13, 2013 6:21 pm UTC
by hawkw
Due to this comic I'm going to be spending the rest of the afternoon writing a JobInterviewSort implementation in Java. Thanks, Randall. :/

Re: 1185: "Ineffective Sorts"

Posted: Wed Mar 13, 2013 6:22 pm UTC
by super_aardvark
And here I thought bogosort had something to do with coupons.

Max2009 wrote:I laughed out loud and got well-deserved strange looks.

Also, my brain segfaulted on the PanicSort. RM -RF is not valid.


Those aren't actually upper-case letters, they just look like it in that font. Think Copperplate Gothic.

Re: 1185: "Ineffective Sorts"

Posted: Wed Mar 13, 2013 6:24 pm UTC
by algorerhythms
Velo Steve wrote:FastBogoSort was definitely my favorite, but I had a problem with PanicSort. I don't know the DOS command line very well any more, so I just typed RD /S /Q C:\* on my pc to see what would happen.

What now? I'm typing this from my tablet, of course.

So you saw this DOS command listed next to "rm -rf /" and decided to try it?

Gotta learn sometime, I guess. :twisted:

Gargravarr wrote:
sep332 wrote:
ahammel wrote:It's pseudocode.

Funny. It's basically Python: no semicolons, no variable type declarations, slice syntax for lists, and no parens after the "for" keyword. There's a joke that Python is just runnable pseudocode. Oddly, the code here uses C-style // comments instead of pythonic # comments.

I'm still looking forward to an XKCD comic written entirely in BrainF*ck. Not even Googleable.

I'm looking forward to an XKCD comic written in Shakespeare. "Thou art as brave as a beautiful lord! Speak your mind!"

Re: 1185: "Ineffective Sorts"

Posted: Wed Mar 13, 2013 6:27 pm UTC
by TimXCampbell
Isaac5 wrote:I am not a big enough nerd for this webcomic. I have no idea what any of this is.

I was a computer consultant for 25 years who used to code 6809 machine language directly in hex.(Translation: I'm a nerd.) But even I sort of sighed when I realized that I had to work my way through the jokes. I really did laugh, but I may have missed some of the humor for the simple reason that I never liked sort algorithms and thus didn't study them. (The best sort algorithm I ever wrote myself was probably a QuickSort, but I didn't know that that's what it was called.)

I personally will not revoke your nerd card just because there's some small part of nerd-dom that you don't understand.

Re: 1185: "Ineffective Sorts"

Posted: Wed Mar 13, 2013 6:28 pm UTC
by Flumble
teelo wrote:[:PIVOT] means passing in an array spliced from index 0 through to PIVOT. Synonym for [0:PIVOT].
[PIVOT:] means PIVOT to the end.

That's indeed the most logical meaning of the short-hand notation. It also leads to PanicSort being somewhat plausible instead of always-fail-except-if-the-list-is-sorted.

dash wrote:It can be proven that this WILL sort the list. But it might take a very long time...

No, you cannot be certain (for either real RNGs or pseudo-RNGs) that it will sort the list in any finite time. It has the same problem as bogosort and panicsort, namely using random without a heuristic* to change the list. Pure* randomness, by definition, does not bring you closer to or further from the desired state.


* There are of course ways in which random only slows your algorithm but doesn't allow an infinite running time, like 'wait a random amount of time between 0 and 10 steps before continuing the algorithm' after every iteration.