Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Quicksort explained IKEA-style

idea-instructions.com

Post reply on HN
Print view View original

121–130 of 142 posts

Re: Quicksort explained IKEA-style

#121

Post by necovek »

ninkendo wrote: post #60
lucaslazarus wrote: post #51

Earlier quoted context omitted.

Presumably some kind of Radix Sort: you ask the crowd to split up and group together by month, let the people in each group self-sort and organize however they'd like, and then just concatenate the sorted queues together

Or to make “concatenate” more physical, divide an area into 12, one for each month in order, then in each area, people sort themselves. This is similar to the best design we have for the fastest way to board a plane: take people in a dozen or so “chunks”, then have each chunk stand in a sorting area atop a diagram of the airplane, one chunk at a time. A group enters the area and sorts themselves by standing near the…

It should be obvious that's most efficient if you can get everyone to be there 30 mins early. Which they can't, mostly due to connecting flights and really not having what to do at the gate for 30 mins.

Re: Quicksort explained IKEA-style

#122

Post by branko_d »

saghm wrote: post #19

If we're willing optimize for aesthetic over ability to help understand, I'll nominate demonstration via Hungarian Folk Dance[1] as a candidate for the best medium to depict sorting algorithms, which I first saw during a lecture years ago when the professor pulled up on of the videos to show us in class [1]: quicksort is shown here, but the channel has plenty of others https://youtu.be/3San3uKKHgg

I was disappointed that men in the video were sorted by their numbers, but not their height! ;)

Re: Quicksort explained IKEA-style

#123

Post by enedil »

zahlman wrote: post #75
TeMPOraL wrote: post #45

Earlier quoted context omitted.

> for some reason in FP languages quicksort is typically next after "hello world" Because the recursive implementation is surprisingly straightforward and concise, and more-less demonstrates what the whole paradigm is about. As much as I hate to admit it, it's a good learning artifact.

Am I alone in that I always felt like mergesort was easier to explain (and the O(n lg n) behaviour was easier to prove)?

O(n lg n) is indeed hard to prove for quicksort, because it is not even true in the general case. Worst case is O(n^2).

Re: Quicksort explained IKEA-style

#124

Post by tmtvl »

jason_s wrote: post #20
klibertp wrote: post #8

If I didn't know how quicksort works - and I had to learn, since for some reason in FP languages quicksort is typically next after "hello world" - I would struggle to make sense of the pictures, I think. However, it's absolutely brilliant as a memory refresher: it packs so much info in so little space that it's insanely efficient. I imagine it would pair well with a good textbook on algorithms.

> since for some reason in FP languages quicksort is typically next after "hello world" How does FP handle the random selection?

Just do the Sedgewick thing and take the median of the first, middle, and last elements.

Re: Quicksort explained IKEA-style

#126

Post by nucleardog »

shib71 wrote: post #80

My first thought was that it would be explaining Quicksort using an Ikea warehouse as a metaphor, to show how different algorithms suit different constraints. As for the actual Ikea-style instruction pamphlet... I suspect that making it was very helpful for the author. But I don't think the result would have helped me as a novice. It took some work for me to understand the diagram, and I've used Quicksort.

> As for the actual Ikea-style instruction pamphlet... I suspect that making it was very helpful for the author. But I don't think the result would have helped me as a novice.

I have no formal CS background or education at all, but have been working in IT for... over 20 years now?

So I'm not a "novice" in one sense, but in another my education on "algorithms" is pretty light and mostly through osmosis. Quicksort specifically is something where I've looked at the Wikipedia article on a number of times to understand but never managed to grasp.

The diagram made it click for me pretty much immediately. Yesterday if you asked me to implement a quicksort I wouldn't have had any idea where to begin, today I can say pretty confidently that I could implement something that would give you back a sorted list.

I'm probably an outlier here--minimal algorithms background, but an intuitive comfort with things like recursion--but at least some anecdotal evidence that it _may_ be useful to a novice!

Re: Quicksort explained IKEA-style

#127

Post by giancarlostoro »

a022311 wrote: post #93
giancarlostoro wrote: post #76

Earlier quoted context omitted.

I kind of get it, but just like Ikea instructions, you start second guessing yourself, then you realize, its BACKWARDS after you flip back 5 pages in when something doesn't fit.

Reminds me of when I was assembling some drawers and put in the bottom of one upside-down. At least I wasn't the one using them...

Are you on about the ones where the bottom is carboard that could go either way? LOL I hate building those.

Ikea instructions are like an Easy to Medium level test in reverse engineering skills, with occasional EXPERT TIER SUPREME level skills needed because of subtleties.

Re: Quicksort explained IKEA-style

#128

Post by f33d5173 »

010101010101 wrote: post #70
f33d5173 wrote: post #49

Earlier quoted context omitted.

I'm talking about step 5. The elements just magically migrate to the correct position, whereas in the real algorithm they would be moved individually.

The curly braces with the arrow pointing down are the thing implying the recursive calls on that set of elements until you’re done.

you're describing step 6

Re: Quicksort explained IKEA-style

#129

Post by ksenzee »

nucleardog wrote: post #126
shib71 wrote: post #80

My first thought was that it would be explaining Quicksort using an Ikea warehouse as a metaphor, to show how different algorithms suit different constraints. As for the actual Ikea-style instruction pamphlet... I suspect that making it was very helpful for the author. But I don't think the result would have helped me as a novice. It took some work for me to understand the diagram, and I've used Quicksort.

> As for the actual Ikea-style instruction pamphlet... I suspect that making it was very helpful for the author. But I don't think the result would have helped me as a novice. I have no formal CS background or education at all, but have been working in IT for... over 20 years now? So I'm not a "novice" in one sense, but in another my education on "algorithms" is pretty light and mostly through osmosis. Quicksort spec…

If you’re an outlier, I’m out there with you: I’ve also been writing software professionally for 20 years, I have no CS degree, and I’m not fool enough to reimplement algorithms like quicksort that are sitting right there in stdlib. I similarly found this explanation a lot more useful than anything else I have read about quicksort, and I’m confident I could implement it now, but couldn’t have before I read this.

Re: Quicksort explained IKEA-style

#130

Post by ants_everywhere »

crdrost wrote: post #82
shib71 wrote: post #80

My first thought was that it would be explaining Quicksort using an Ikea warehouse as a metaphor, to show how different algorithms suit different constraints. As for the actual Ikea-style instruction pamphlet... I suspect that making it was very helpful for the author. But I don't think the result would have helped me as a novice. It took some work for me to understand the diagram, and I've used Quicksort.

For me the key was just application to figuring out if any cards are missing in a deck by sorting it. Assume spades In your first pass, divide the deck into black and red cards. Then divide black into spades and clubs. Then divide spades into 7. Then insertion sort the cards 7, spades are now sorted. Clubs come next, divide into 7, insertion sort, and combine. Split diamonds and hearts, repeat with diamonds, repeat w…

Similary idea: I used to be a TA and every week I would sort ~50 papers or exams alphabetically to make it easier to verify accuracy in the grading spreadsheet. Sorting this many papers regularly forces you to find a good way to do it, and it's hard to avoid recursion.

Even better: sort something physically large like several bookshelves of books or a record collection. You can't hold the collection in your hand and you're forced to use piles. You may even decide to work bookshelf by bookshelf first.

These are all good ways to develop intuition for sorting algorithms. Personally I always just use quicksort until I've come to a part of the alphabet where I can immediately recall which letter precedes every other then I do insertion sort. You might decide to use another hybrid sort like timsort.

Post reply on HN