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

61–70 of 142 posts

Re: Quicksort explained IKEA-style

#61

Post by NetMageSCW »

theogravity wrote: post #40

This surprisingly made this easy to remember for me. Unfortunately, the merge sort instructions doesn't make sense to me, specifically step 3.

The key to step 3 (of the merge sort) is the little nx in the middle that tells you to repeat step 3 n times. Each time, you take a right or left branch based on if the new weight from the half plank is lighter or heavier than the current weight. You also have to understand that step 1 means you recursively merge sort each half before you merge the two sorted halves.

Re: Quicksort explained IKEA-style

#62

Post by NetMageSCW »

jfengel wrote: post #41
theogravity wrote: post #40

This surprisingly made this easy to remember for me. Unfortunately, the merge sort instructions doesn't make sense to me, specifically step 3.

It's not a merge sort, it's just a partition. Mark every element greater than your pivot as "move right". Then step 4 marks every smaller element as "move left". Step 5 actually does that. You don't really need to split that into 3 steps, though it looks a bit more like a real IKEA diagram with the extra steps.

Wrong diagram - “merge sort”.

Re: Quicksort explained IKEA-style

#63

Post by NetMageSCW »

CyberDildonics wrote: post #38

I think a much better explanation would be to just say that it partitions the values into a lower and higher half. Then it recursively does the same thing to each half. After that you just have to understand exactly how partitioning works and get the ranges correct.

How do you decide which weight to use to create two halves?

Re: Quicksort explained IKEA-style

#65

Post by tialaramex »

f33d5173 wrote: post #49
tialaramex wrote: post #32

Earlier quoted context omitted.

Well, to the extent a picture can explain they say choose at random. That's what the dice shown is about. A random pivot is... fine. It can't solve the worst case perf problem, and it won't ensure high performance for other cases either, but hey you did pick a pivot and this algorithm is often fast enough.

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.

It would be clearer if they weren't magically sorted early. Maybe they can improve in a later edition of the instructions.

I think maybe Lego would cut away to show one layer of repetition for example.

Re: Quicksort explained IKEA-style

#66

Post by tialaramex »

NetMageSCW wrote: post #63
CyberDildonics wrote: post #38

I think a much better explanation would be to just say that it partitions the values into a lower and higher half. Then it recursively does the same thing to each half. After that you just have to understand exactly how partitioning works and get the ranges correct.

How do you decide which weight to use to create two halves?

In their example they choose a random pivot, is that what you're asking about?

There are a number of strategies but random will indeed work and is simple to explain.

Re: Quicksort explained IKEA-style

#67

Post by CyberDildonics »

NetMageSCW wrote: post #63
CyberDildonics wrote: post #38

I think a much better explanation would be to just say that it partitions the values into a lower and higher half. Then it recursively does the same thing to each half. After that you just have to understand exactly how partitioning works and get the ranges correct.

How do you decide which weight to use to create two halves?

You use a value called a pivot, not a weight, and there are many ways and endless variations you can read about, including just choosing a random value from the current range.

Re: Quicksort explained IKEA-style

#68

Post by gerdesj »

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…

"I agree, IKEA instructions are great"

They are until you hit one for something that is so simple it does not really need instructions, then you will end up in a tail spin! We bought a window shade puller thing and it had instructions!

Lego are also superb at instructions, for obvious reasons. I've put together a couple of modern Lego models with a lot of pieces and they are still as good as I remember 40+ years ago. I have to say that the model of the Chinese Year of the Dragon beastie from 2024? was pretty tricky.

Re: Quicksort explained IKEA-style

#69

Post by [deleted] »

xandrius wrote: post #28
rfl890 wrote: post #25

Earlier quoted context omitted.

I ignored the arrows and interpreted it as "move all elements lower than the marker in order to the left of the marker, and move all elements higher than the marker in order to the right of the marker". It's not clear, but if you use a bit of intuition you can come to this conclusion. Personally it took me about 5 seconds.

Have you ever learnt about Quicksort? If so, it might give you an edge on what to expect.

[deleted]

Re: Quicksort explained IKEA-style

#70

Post by 010101010101 »

f33d5173 wrote: post #49
tialaramex wrote: post #32

Earlier quoted context omitted.

Well, to the extent a picture can explain they say choose at random. That's what the dice shown is about. A random pivot is... fine. It can't solve the worst case perf problem, and it won't ensure high performance for other cases either, but hey you did pick a pivot and this algorithm is often fast enough.

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.
Post reply on HN