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

91–100 of 142 posts

Re: Quicksort explained IKEA-style

#91

Post by moi2388 »

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…

That’s how I sorted cards long before knowing about sorting algorithms

Re: Quicksort explained IKEA-style

#92

Post by eru »

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…

A lot of people have trouble with understanding recursion. Perhaps that's where they struggle with quicksort?

Luckily, there's a simple non-recursive quicksort variation. It goes like this:

Simplifying assumption: all items are distinct.

Invariant: Throughout our procedure, we will have a bunch of bags arranged in a sequence before us from left to right. Items in a bag are all jumbled up, but all items in bag A are smaller than any item in bag B, if A comes before B in our sequence.

Now, we start by stuffing all our items into a single bag.

We repeat the following:

- Pick an arbitrary bag X. Anyone will do, you can pick at random, or your favourite bag, or always the left-most or whatever. Only one condition: bag X has to have more than a single element left in it.

- Grab a random element E out of X as your pivot.

- Categories all elements of X into: smaller than E, E itself, and bigger than E. Stick these categories into their own bags and place them into our sequence in the appropriate order.

Repeat until all bags left have one or fewer elements.

Re: Quicksort explained IKEA-style

#93

Post by a022311 »

giancarlostoro wrote: post #76
a022311 wrote: post #2

This is so cool! Not only is the design similar, but just like the real IKEA instructions, I can't understand them! This is as realistic as it gets.

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

Re: Quicksort explained IKEA-style

#95

Post by Dwedit »

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)?

Merge Sort is much easier to explain when you do the non-recursive version that's upside-down. Merge size 1 together, merge size 2 together, merge size 4 together, merge size 8 together, etc...

Re: Quicksort explained IKEA-style

#96

Post by froh »

Dwedit wrote: post #94

I never understood why use Quick Sort when you could use something else instead, like Merge Sort. Using a pivot seems backwards compared to something guaranteed to be NLOGN time.

here you go:

https://idea-instructions.com/merge-sort/

and I think in this discussion we marvel the presentation, not the algorithm per se.

Re: Quicksort explained IKEA-style

#97

Post by froh »

this page is fun. and it has a large number of algorithms "explained" Ikea style.

I think it's great to explain them to others. I think it doesn't work as a teaching tool per se. it needs someone who understands the algorithms already, to decide and explain what's going on.

thank you for sharing

Re: Quicksort explained IKEA-style

#98

Post by Cockbrand »

porridgeraisin wrote: post #27
thomasmg wrote: post #15

I agree, IKEA instructions are great. A bit related are railroad diagrams, like the one of the JSON syntax [2]. I worked on Rubik's cube solving instructions for beginners [1] (for my children initially), but then I found it would be so much better if the instructions are IKEA style. (Then I vibe-coded a Rubik's cube 2D and 3D model, and now I stopped working on this. Something for later.) For the cube, I want to imp…

> Rubik's cube 3D model Google had a doodle way back when... That let you play the cube on the search page. I found it hosted here [1] although I'm sure they have a doodles archive. Didn't check it myself but it should be possible to take the JS from that and use it for our purposes. [1] https://sites.google.com/site/populardoodlegames/rubik-s-cub...

> I'm sure they have a doodles archive

You are correct: https://doodles.google/

It doesn't seem to have the Rubik's cube, though

Re: Quicksort explained IKEA-style

#99

Post by xigoi »

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…

What you’re describing is more like MSD radix sort.

Re: Quicksort explained IKEA-style

#100

Post by nayuki »

thomasmg wrote: post #15

I agree, IKEA instructions are great. A bit related are railroad diagrams, like the one of the JSON syntax [2]. I worked on Rubik's cube solving instructions for beginners [1] (for my children initially), but then I found it would be so much better if the instructions are IKEA style. (Then I vibe-coded a Rubik's cube 2D and 3D model, and now I stopped working on this. Something for later.) For the cube, I want to imp…

SQLite also has lots of excellent railroad diagrams for SQL syntax. e.g. https://sqlite.org/lang_select.html#overview
Post reply on HN