… made me laugh out loud for the first time in quite a while. (xkcd: Ineffective Sorts)
The Job Interview Quicksort brought back some fond memories!
This one was, for a change, over my head. Other than the most basic of Basic, I’ve never learned programming, so it was gibberish to me. One of the few XKCD’s that I neither understand nor have a chance of understanding without significant amounts of training.
Weird feeling.
Did he change the site’s schedule? New strips used to be Monday, Wednesday and Friday.
This comic was posted yesterday. At least, I saw it yesterday evening when doing my usual pre-bed webcomics run.
The mouseover text was the best part.
Concur.
What language is it? It looks a lot like Python but not exactly.
NM
[QUOTE=Quimby]
Did he change the site’s schedule? New strips used to be Monday, Wednesday and Friday.
[/QUOTE]
I usually see the new ones first thing in the morning but yesterday it wasn’t posted until some point later in the day and I didn’t see it until this morning.
Sorting humor is in a category all its own. You not only have to understand what is being done, but find it funny that it’s being done badly. Bad sorting algorithms are sort of like Rube Goldberg machines.
For what it’s worth, I’ve attempted to summarize what each of the “ineffective” (as opposed to “inefficient”) sorting algorithms below. I promise neither accuracy nor humor as an outcome, however. 
halfheartedmergesort:
It starts out by checking to see if the list has less than two elements. If so, it’s already sorted, so it gives it back. So far, so good. Then it starts splitting up the list. The idea is to split the list into easy-to-sort pieces, then sort the pieces and stick them back together…but this one just keeps chopping up the pieces until each only has 1 element, then it hands back the pieces. Without ever actually sorting them.
fastbogosort:
Bogosort is the canonical example of a bad sorting algorithm…or any kind of algorithm, really. A bogosort works by taking the list, checking if it’s sorted, and if it’s not, randomizing the list order. It repeats this until the list is sorted. The usual analogy is throwing a shuffled deck of cards into the air, then picking them up and checking to see if they’re sorted. This one takes it a step further by giving up after a very few tries and blaming it on the kernel. Bonus: it doesn’t even check if the list is sorted before the first shuffle, so it could be scrambling an already sorted list.
jobinterviewquicksort:
Sorting algorithms are apparently a favorite topic of people interviewing applicants for programming positions, even though almost no one ever really writes sorts from scratch. It’s mostly because it’s easy to get the applicant chasing their own tails, which is amusing for the kind of people who interview would-be programmers.
panicsort:
It’s a deformed hybrid of a bogosort and a quicksort, I think, with a deadline hanging over it. It randomly cuts the list in two and swaps the pieces, then checks to see if the result is sorted. If not, it tries again, up to 10000 times. Then it checks repeatedly to see if the list is sorted. Since it obviously isn’t, the script hides the evidence by deleting the list and everything on the hard drive, returning a hardcoded list ([1, 2, 3, 4, 5]), and shutting down the computer.
Also, QuickSort is one of the cannonical recursive algorithms, it comes up in every CS algorithm class during both the ‘sorting’ discussions and the ‘recursive’ discussions. A CS student sees this one many many times as an undergrad. Recursive algorithms are noted for their elegance and simplicity. Ask someone to write it from scratch though and this is what you get.
I was laughing hard enough that I was crying at the last one.
I think what really did it for me was that after he’d nuked the entire disk on *nix, there was also a line to do it on Windows, with the comment “Portability”. The repeated checks to see if the list might have somehow become sorted (with increasingly anxious comments) were also pretty awesome.
Yeah, for computer geeks, wow. Oh man wow. BWAHAHHAHAHAHAHAHA
My preferred variant of bogosort is the linear bogosort: Randomize the list, using a good (i.e., quantum) randomizer. Then, check to see if the list is sorted. If it’s not, destroy the Universe. Presto, the list is now sorted in every existing Universe.
(spoiler alert: The algorithm isn’t actually linear, despite appearances)
If someone asked me to create or describe a sorting algorithm in a job interview, I’d probably go with Mergesort. It’s not the most efficient on average, but it’s still an n log n method, it’s guaranteed n log n even in worst case, and it’s conceptually simple enough for a human to easily handle.
And I don’t think I’ve ever seen a recursive version of Quicksort-- I’ve always seen it implemented as a loop. Which is probably significantly quicker on most architectures.
C:\dos
c:\dos run
run dos run
Really? I know you can handle most recursive algorithms in a loop, but at the moment I can’t think of a nice, clean way to do it for Quicksort. The two pseudocode examples at wikipedia both use recursion - you partition the list, (which involves a loop,) and then quicksort both partitions.
In fact, with a brief Google search I haven’t found an algorithm for Quicksort that doesn’t use recursion. I’d like to take a look if you can point me to one.
Also, the new XKCD for today, Friday the 15th, is very funny, not as specifically geeky, and relevant to our mission statement of fighting ignorance, (and when ignorance refuses to surrender!)
Tried editing to add this, but ran over the 5 minute limit…
Now I’m reminded of the palmOS utility program I wrote that would give the breakdown of space usage on an SD card. So I had to traverse the card’s folder structure, a naturally recursive task; but the BASIC compiler for palmOS I was using didn’t support functional recursion. If you called a function from itself, you were still using the same local variables you had at the higher level, and they’d still be at the same values when you returned from the recursive call :smack:
I ended up writing that tree traversal as a loop, using fixed arrays as stacks to handle the data from all the parent nodes in the tree; essentially creating my own recursive activation frames since the language didn’t give them to me in the usual way.
Is Donald Knuth’s Fundamental Algorithms, “Sorting and Searching” still a reference?
God, I’m old. Yes, I learned to program on punch cards.