XKCD: It's more than a comic

I think Oobleck, in addition to being an hilarious mixture, is an Inherently Funny Word.

Of course it is, Dr Seuss invented it!

he did?

The Boston Molassas disaster was hilarious, too...

actually, i was laughing at that.

then i saw 20 people died. stopped laughing.

I feel like he saw people complaining about the world ending too often so he made a what-if that was so dull and uneventful that you can almost see that little hole in it where his heart was supposed to be. So yeah, not one of his finer pages.

edited 12th Mar '13 2:16:36 PM by Brickman

"you can almost see that little hole in it where his heart was supposed to be"

I guess he's just your average Evil Scientist. If he's not ending the world, he's not happy.

Ineffective Sorts

Sigh.

hahahahahahaha. Oh, man. I love computer science jokes. I have, many times, needed to throw together a sort algorithm. I almost always go for a standard selection sort because it's easy.

That is an entirely too accurate description of most job interviews.

I've never been asked to pseudocode a sorting algorithm in a job interview, but then again I haven't interviewed for very many baseline coding jobs. The point, which is that you often flub basic task questions out of nerves, is still valid.

edited 13th Mar '13 10:54:38 AM by Fighteer

Generally, I am either using a language with plenty of sorts built in, or else I simply require a priority queue. So either selection sorts or heapsorts, depending on if there's enough items that I care about big O.

The good news about my work is that I can generally rely on the underlying database engines that I work with to handle large sorts for me, simply by constructing queries properly. When I need to sort in code, it's almost always on data sets that are small enough to make the efficiency gains from using a more complex sorting algorithm not worth the tradeoff in coding and debugging.

Now, I have worked with lower level languages (C and such), and in general if I'm going to implement heap or other more complex sorts, I'd write library code to manage the general case, preferably using generically typed containers. Heck, I'd do it with selection sorts too, just to keep things modular.

void * mysort(void * list, char * sKey, int sType) { ... }

Okay, that's kind of gibberish but it's the basic idea. It's been a long time since I've written live C code.

edited 13th Mar '13 11:25:50 AM by Fighteer

I'm almost entirely certain that I don't want to go out of my way to try and get this joke today...

I got the general idea but I really dont get most of it. I just wrote it up to "well, maybe in a few weeks we'll learn that in class"

The core of the joke is that there's several standard "best" sorting routines but they're all pretty complicated. "Best" means that the rate at which the runtime increases when you sort more items is the best you can with a starting set in random order, which is constant*N*log(N). There is NO method which beats NlogN on a large unsorted data set, period.

The first snippet of code starts off like he's going to write one of the standard methods but runs into trouble because that the actual mechanics behind that sort are tricky and the writer realized he didn't know what he was supposed to do after the setup phase. So he gives up and returns it unsorted.

The second one doesn't even bother trying to sort; it just randomizes the order of the list a handful of times and if that doesn't work it pretends to crash. But it's guaranteed to "finish" in NlogN time like all the "good" sorting methods.

The third one is just gibberish; there is no method whatsoever because it's parodying the arbitrary nature of many hiring practices.

The fourth one is like the first two but worse; it checks if it's already sorted, incorrectly implements mergesort such that it's not actually changing the order and just checks the starting order over and over, rechecks the last order it came up with several more times even though it can't accomplish anything, then tells your computer to shut down in five hours and deletes all your files, presumably so you can't tell what happened later.

Personally, I haven't written or looked at code implementing ANY sorting method except selection-sort (for the uninitiated, that means "find item #1, then find item #2, etc" and does NOT run in NlogN time, but a trained monkey could implement it) since the class in which I learned about them, not counting maybe a brushup when I was doing interviews. If I need something better I'm probably programming in a language or on a system that already has it.

edited 13th Mar '13 1:39:01 PM by Brickman

I got the gist of all of those, although it's even funnier when you write it out explicitly like that.

What's even more facepalm-worthy from my perspective as a programmer is that the calls to issorted(list) are likely to be very expensive — nobody writing a real sort would ever do it that way. It's the pseudocode equivalent of Step Three: Profit.

Edit: In response to your edit, I too find myself having to look up any sort more complicated than a basic selection sort if the situation calls for it. I'm actually pretty good with recursion, which most advanced sorts use, but the specifics elude me since I almost never use them.

If I actually had a job interview in which sorting algorithms became an issue, I'd either bone up ahead of time or flat out tell the guy, "Look, the Internet exists for a reason. I know how sorting works in general and I know how to write head and tail recursion without blowing my computer up. If I really need to manually code a heap sort in this job, I'll look it up. Meanwhile, I'm shocked that you haven't developed common libraries if you're really programming at the level this question would imply."

edited 13th Mar '13 1:46:19 PM by Fighteer

Note: The second is an "abridged" version of the archetypal "worst" (The Jargon file says "Perversely awful") sorting algorithm, Bogosort

If a job interviewer is asking you for a sorting algorithm he doesn't really care about the algorithm. He cares that you understand recursion and that you have the skills to find a solution to a coding-style problem. I'm no interviewer but my guess is he's actually hoping you don't have it memorized and he gets to watch you puzzle it out to demonstrate your skills, but obviously can't fault you if you were that prepared.

edited 13th Mar '13 2:06:09 PM by Brickman

I know merge sort off the top of my head, at least the naive high-memory-usage version. Anything else...I'm either in a language that does it for me, or I can look it up on the Internet.

Personally, my favorite was the FastBogoSort.

My favorite is the alt text. God, Stack Overflow is my new Bible. And yeah, I haven't implemented a sort since my university days, and if asked, I would probably say "Use the built-in sorting algorithm, these guys generally know what they're doing".

It's pretty funny how stuck in a rut companies tend to be. I just took an interview for a six-figure job at a large investment back where the job description involved a complete rewrite of their internal systems architecture. The screener question? Straight out of a comp sci text book, complete with "prompt and read from standard input". Geesh.

Right, because if you can do a printf/scanf combo (or even better, INPUT$!) you are clearly qualified to rewrite system architecture. I should apply!

edited 14th Mar '13 6:18:47 AM by Fighteer

The built-in sorting algorithm isn't always fine when you want a stable sort.

Stable? What does that mean?