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

31–40 of 142 posts

Re: Quicksort explained IKEA-style

#31

Post by jalk »

JdeBP wrote: post #13
musicale wrote: post #3

Earlier quoted context omitted.

Missing the instruction panel where the customer is attempting to follow the baffling instructions and has to use a wired phone to call the store for help. Getting quicksort's boundary conditions right (avoiding off-by-one errors, infinite recursion, etc.) can be tricky. Another popular algorithm that can be hard to get right is binary search.

BINÄRY SEARCH has you covered. (-: * https://idea-instructions.com/binary-search/

Stuck in second round of step 2, since there is no middle cup to lift!

Re: Quicksort explained IKEA-style

#32

Post by tialaramex »

f33d5173 wrote: post #17
kazinator wrote: post #11

It looks like Step 3 may be using Hoare's original partitioning method with two pointers, which is laudable.

You're misunderstanding. They don't explain how to do partitioning at all. Step 3 is just tagging the elements that are above the partition element, which there happen to be two of.

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.

Re: Quicksort explained IKEA-style

#33

Post by Dan42 »

Dan42 wrote: post #23
HarHarVeryFunny wrote: post #16

Earlier quoted context omitted.

Isn't that more of an implementation detail? I'd guess if you care more about speed than memory it might be faster to just move elements into new array - sequence through old array appending to start/end of new array according to pivot comparison. You'd be moving every element vs leaving some in place with a swap approach, but the simplicity of the code & branch prediction might win out.

I'm pretty sure the swapping is a fundamental part of the quicksort algorithm, not a mere implementation detail. That's the reason quicksort is an in-place algorithm.

Actually you're right, it is an implementation detail. The original isn’t mistaken, it’s just showing the lo-to-hi partitioning pass rather than the from-both-ends version I had in mind when I implemented quicksort before.

shame, shame, I should have double-checked before posting.

Re: Quicksort explained IKEA-style

#35

Post by klibertp »

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?

They use the first element. Like, it's random enough, right? :) (I mean, it still works, but goes badly for lists already sorted in reverse, etc.)

Re: Quicksort explained IKEA-style

#36

Post by imajoredinecon »

rfl890 wrote: post #25
LordGrey wrote: post #18

Step #5 is very much a "draw the rest of the fucking owl" step.

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.

I agree it does a pretty good job of communicating that. I think the other commenters are pointing out that doesn’t show how to efficiently get all the smaller items left of the partition and larger ones to the right. While that’s probably second nature to most people who’ve taken an algorithms class or done a decent amount of programming, I guess it’s up for interpretation how obvious it would be to the “intended audience” of the ikea manual

Re: Quicksort explained IKEA-style

#37

Post by tialaramex »

klibertp wrote: post #9
tlahtinen wrote: post #7

Earlier quoted context omitted.

I'm a programmer (after a fashion) but I don't know how quicksort works. This is how I understand it after reading these instructiöns, without looking up any further explanation: 1. Choose a random element as the 'center' point of the sort 2. That element defines the maximum 'height' (value) 3. Anything that is larger than that value, is moved to the right side of the 'center' 4. Anything that is smaller than that va…

Yeah, that's about it. Personally, I'm not sure I'd get this much out of the picture, but you can see the information is there. > surely it can't be just three iterations? To save others a search: you stop when the remaining sub-arrays are sorted by definition (ie. [] or [x]/size of 0 or 1).

Also, to save any further puzzling: In practice the very fast sort you use, even if it is labelled "Quicksort" probably doesn't actually do this "all the way down" even though that's the strict algorithm.

They'll have a highly optimised small sort and use that whenever sorting very small things. So e.g. IPN Sort the Rust stdlib unstable sort will do this for 16 items, even though for a big slice it'd quick sort them by default, once it's down to say 10 items they're going to the specialised small sort.

Any serious "fast" sort in 2025 will be a hybrid, using several of these classic sorting algortihms, plus other insights to produce the overall best solution to their problem on modern hardware.

Re: Quicksort explained IKEA-style

#38

Post by CyberDildonics »

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.

Re: Quicksort explained IKEA-style

#39

Post by shpongled »

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?

There's no problem with randomness in FP?

You could use a monad/external state for an OS-level RNG, or define a purely functional PRNG

Post reply on HN