1185: "Ineffective Sorts"

This forum is for the individual discussion thread that goes with each new comic.

Moderators: Moderators General, Prelates, Magistrates

User avatar
rhomboidal
Posts: 754
Joined: Wed Jun 15, 2011 5:25 pm UTC
Contact:

1185: "Ineffective Sorts"

Postby rhomboidal » Wed Mar 13, 2013 4:28 pm UTC

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!!

User avatar
snowyowl
Posts: 464
Joined: Tue Jun 23, 2009 7:36 pm UTC

Re: 1185: "Ineffective Sorts"

Postby snowyowl » Wed Mar 13, 2013 4:35 pm UTC

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.
The preceding comment is an automated response.

User avatar
player_03
Posts: 18
Joined: Sat Oct 16, 2010 11:13 pm UTC

Re: 1185: "Ineffective Sorts"

Postby player_03 » Wed Mar 13, 2013 4:36 pm UTC

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...
Last edited by player_03 on Wed Mar 13, 2013 4:44 pm UTC, edited 2 times in total.

Gargravarr
Posts: 74
Joined: Mon Dec 21, 2009 8:34 am UTC

Re: 1185: "Ineffective Sorts"

Postby Gargravarr » Wed Mar 13, 2013 4:37 pm UTC

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.

User avatar
tibfulv
Posts: 48
Joined: Tue Nov 27, 2012 11:31 am UTC

Re: 1185: "Ineffective Sorts"

Postby tibfulv » Wed Mar 13, 2013 4:41 pm UTC

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.

Gargravarr
Posts: 74
Joined: Mon Dec 21, 2009 8:34 am UTC

Re: 1185: "Ineffective Sorts"

Postby Gargravarr » Wed Mar 13, 2013 4:51 pm UTC

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

Half-forgotten Python?

User avatar
creaothceann
Posts: 34
Joined: Fri Jan 26, 2007 9:44 am UTC
Location: Germany

Re: 1185: "Ineffective Sorts"

Postby creaothceann » Wed Mar 13, 2013 4:53 pm UTC

// THIS CAN'T BE HAPPENING

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

User avatar
peewee_RotA
Posts: 499
Joined: Mon Dec 12, 2011 1:19 pm UTC

Re: 1185: "Ineffective Sorts"

Postby peewee_RotA » Wed Mar 13, 2013 5:08 pm UTC

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.
"Vowels have trouble getting married in Canada. They can’t pronounce their O’s."

http://timelesstherpg.wordpress.com/about/

User avatar
ahammel
My Little Cabbage
Posts: 2135
Joined: Mon Jan 30, 2012 12:46 am UTC
Location: Vancouver BC
Contact:

Re: 1185: "Ineffective Sorts"

Postby ahammel » Wed Mar 13, 2013 5:10 pm UTC

It's pseudocode.
He/Him/His/Alex
God damn these electric sex pants!

User avatar
jc
Posts: 332
Joined: Fri May 04, 2007 5:48 pm UTC
Location: Waltham, Massachusetts, USA, Earth, Solar System, Milky Way Galaxy
Contact:

Re: 1185: "Ineffective Sorts"

Postby jc » Wed Mar 13, 2013 5:13 pm UTC

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 ...

User avatar
Isaac5
Posts: 5
Joined: Mon Feb 01, 2010 1:24 pm UTC

Re: 1185: "Ineffective Sorts"

Postby Isaac5 » Wed Mar 13, 2013 5:15 pm UTC

I am not a big enough nerd for this webcomic. I have no idea what any of this is.

*hangs head in shame*

User avatar
NeatNit
Posts: 41
Joined: Tue Apr 03, 2012 9:10 pm UTC

Re: 1185: "Ineffective Sorts"

Postby NeatNit » Wed Mar 13, 2013 5:19 pm UTC

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

Ehsanit
Posts: 50
Joined: Tue Nov 09, 2010 7:53 pm UTC

Re: 1185: "Ineffective Sorts"

Postby Ehsanit » Wed Mar 13, 2013 5:20 pm UTC

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.

User avatar
Max2009
Posts: 160
Joined: Mon Mar 09, 2009 2:20 pm UTC
Location: Where?
Contact:

Re: 1185: "Ineffective Sorts"

Postby Max2009 » Wed Mar 13, 2013 5:22 pm UTC

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

Also, my brain segfaulted on the PanicSort. RM -RF is not valid.
Cogito ergo surf - I think therefore I network

Registered Linux user #481826 Get Counted! http://counter.li.org

Image

User avatar
Isaac5
Posts: 5
Joined: Mon Feb 01, 2010 1:24 pm UTC

Re: 1185: "Ineffective Sorts"

Postby Isaac5 » Wed Mar 13, 2013 5:22 pm UTC

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.

EverVigilant
Posts: 13
Joined: Mon Oct 10, 2011 12:15 pm UTC

Re: 1185: "Ineffective Sorts"

Postby EverVigilant » Wed Mar 13, 2013 5:24 pm UTC

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?

User avatar
tibfulv
Posts: 48
Joined: Tue Nov 27, 2012 11:31 am UTC

Re: 1185: "Ineffective Sorts"

Postby tibfulv » Wed Mar 13, 2013 5:24 pm UTC

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.
Last edited by tibfulv on Wed Mar 13, 2013 5:27 pm UTC, edited 1 time in total.

Ehsanit
Posts: 50
Joined: Tue Nov 09, 2010 7:53 pm UTC

Re: 1185: "Ineffective Sorts"

Postby Ehsanit » Wed Mar 13, 2013 5:25 pm UTC

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.

User avatar
ahammel
My Little Cabbage
Posts: 2135
Joined: Mon Jan 30, 2012 12:46 am UTC
Location: Vancouver BC
Contact:

Re: 1185: "Ineffective Sorts"

Postby ahammel » Wed Mar 13, 2013 5:26 pm UTC

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.
He/Him/His/Alex
God damn these electric sex pants!

Velo Steve
Posts: 16
Joined: Thu May 05, 2011 12:27 am UTC

Re: 1185: "Ineffective Sorts"

Postby Velo Steve » Wed Mar 13, 2013 5:28 pm UTC

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.

Gargravarr
Posts: 74
Joined: Mon Dec 21, 2009 8:34 am UTC

Re: 1185: "Ineffective Sorts"

Postby Gargravarr » Wed Mar 13, 2013 5:29 pm UTC

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.

User avatar
Jofur
Posts: 102
Joined: Wed Sep 19, 2012 7:50 pm UTC

Re: 1185: "Ineffective Sorts"

Postby Jofur » Wed Mar 13, 2013 5:30 pm UTC

ahammel wrote:It's pseudocode.


I like you. You get it. :P
Everybody is doing it and nobody knows why.

User avatar
orthogon
Posts: 2612
Joined: Thu May 17, 2012 7:52 am UTC
Location: The Airy 1830 ellipsoid

Re: 1185: "Ineffective Sorts"

Postby orthogon » Wed Mar 13, 2013 5:30 pm UTC

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.
xtifr wrote:... and orthogon merely sounds undecided.

RogueCynic
Posts: 355
Joined: Sun Nov 22, 2009 10:23 pm UTC

Re: 1185: "Ineffective Sorts"

Postby RogueCynic » Wed Mar 13, 2013 5:31 pm UTC

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.
I am Lord Titanius Englesmith, Fancyman of Cornwood.
See 1 Kings 7:23 for pi.
If you put a prune in a juicer, what would you get?

User avatar
tibfulv
Posts: 48
Joined: Tue Nov 27, 2012 11:31 am UTC

Re: 1185: "Ineffective Sorts"

Postby tibfulv » Wed Mar 13, 2013 5:33 pm UTC

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 ....
Last edited by tibfulv on Wed Mar 13, 2013 5:39 pm UTC, edited 1 time in total.

teelo
Posts: 728
Joined: Thu Apr 08, 2010 11:50 pm UTC

Re: 1185: "Ineffective Sorts"

Postby teelo » Wed Mar 13, 2013 5:35 pm UTC

Code: Select all

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

User avatar
tibfulv
Posts: 48
Joined: Tue Nov 27, 2012 11:31 am UTC

Re: 1185: "Ineffective Sorts"

Postby tibfulv » Wed Mar 13, 2013 5:36 pm UTC

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.

teelo
Posts: 728
Joined: Thu Apr 08, 2010 11:50 pm UTC

Re: 1185: "Ineffective Sorts"

Postby teelo » Wed Mar 13, 2013 5:37 pm UTC

[:PIVOT] means passing in an array spliced from index 0 through to PIVOT. Synonym for [0:PIVOT].
[PIVOT:] means PIVOT to the end.

User avatar
dash
Posts: 93
Joined: Sat Mar 08, 2008 4:05 am UTC

Re: 1185: "Ineffective Sorts"

Postby dash » Wed Mar 13, 2013 5:51 pm UTC

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/
If my wife were a D&D character she'd be all 10's

TexasToast
Posts: 12
Joined: Wed Oct 06, 2010 4:09 am UTC

Re: 1185: "Ineffective Sorts"

Postby TexasToast » Wed Mar 13, 2013 6:02 pm UTC

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/

User avatar
mrob27
Posts: 1218
Joined: Tue Jun 28, 2011 2:19 am UTC
Location: 〗  
Contact:

Re: 1185: "Ineffective Sorts"

Postby mrob27 » Wed Mar 13, 2013 6:03 pm UTC

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"...
Robert Munafohttp://mrob.com@mrob_27
Image
I ᴍᴀᴅᴇ sᴏɍᴛᴡᴀʀᴇ ᴛʜᴀᴛ Rᴀɴᴅᴀʟʟ ɍᴏᴜɴᴅ ᴜsᴇɍᴜʟ ɪɴ ᴛʜɪs хᴋᴄᴅ

sep332
Posts: 10
Joined: Thu Sep 16, 2010 10:42 pm UTC

Re: 1185: "Ineffective Sorts"

Postby sep332 » Wed Mar 13, 2013 6:03 pm UTC

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.

TexasToast
Posts: 12
Joined: Wed Oct 06, 2010 4:09 am UTC

Re: 1185: "Ineffective Sorts"

Postby TexasToast » Wed Mar 13, 2013 6:04 pm UTC

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/

SamSam
Posts: 22
Joined: Fri Apr 03, 2009 4:00 pm UTC

Re: 1185: "Ineffective Sorts"

Postby SamSam » Wed Mar 13, 2013 6:07 pm UTC

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.

Gargravarr
Posts: 74
Joined: Mon Dec 21, 2009 8:34 am UTC

Re: 1185: "Ineffective Sorts"

Postby Gargravarr » Wed Mar 13, 2013 6:09 pm UTC

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.

hawkw
Posts: 1
Joined: Wed Mar 13, 2013 6:20 pm UTC

Re: 1185: "Ineffective Sorts"

Postby hawkw » Wed Mar 13, 2013 6:21 pm UTC

Due to this comic I'm going to be spending the rest of the afternoon writing a JobInterviewSort implementation in Java. Thanks, Randall. :/

User avatar
super_aardvark
Posts: 54
Joined: Tue Jan 22, 2008 9:26 am UTC

Re: 1185: "Ineffective Sorts"

Postby super_aardvark » Wed Mar 13, 2013 6:22 pm UTC

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.

algorerhythms
Posts: 42
Joined: Fri Nov 02, 2007 4:23 pm UTC

Re: 1185: "Ineffective Sorts"

Postby algorerhythms » Wed Mar 13, 2013 6:24 pm UTC

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!"
The nerdy webcomic that I update on Saturdays: Cesium Comics

User avatar
TimXCampbell
Posts: 110
Joined: Wed Jul 27, 2011 4:26 am UTC
Location: Very Eastern Kentucky, USA
Contact:

Re: 1185: "Ineffective Sorts"

Postby TimXCampbell » Wed Mar 13, 2013 6:27 pm UTC

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.

User avatar
Flumble
Yes Man
Posts: 1923
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: 1185: "Ineffective Sorts"

Postby Flumble » Wed Mar 13, 2013 6:28 pm UTC

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.


Return to “Individual XKCD Comic Threads”

Who is online

Users browsing this forum: No registered users and 28 guests