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

51–60 of 142 posts

Re: Quicksort explained IKEA-style

#51

Post by lucaslazarus »

stevage wrote: post #44
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

So what is the best algorithm when you have a bunch of people and want them sorted in order of, say, birthday.

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

Re: Quicksort explained IKEA-style

#53

Post by QuantumNomad_ »

TeMPOraL wrote: post #50
BaardFigur wrote: post #24

Don't call it quicksört (aka quicksørt/quicksœrt). It's so jarring to read. It's pronounced line the vocal sound in "learn"

Doesn't matter - it's just a FEJKA manual anyway.

But it does matter. I’m not sure if you are already aware and did it intentionally or if it was a happy accident, but FEJKA really is named that because it’s a real word in Swedish that comes from English with meaning very near to how you used it there.

Swedish adjective “fejk” comes from English adjective “fake”.

Swedish “fejka” is the verb form of the same, with the meaning similar to one of the English meanings of the verb form: To give the impression that something is a certain way when it is not.

And that’s what the FEJKA series of products happen to be. Artificial plants that look like they are real, even though they are not :)

And so back to the point of naming these pretend IKEA manuals. If they are to really look real without being real, they should be named in a way that would make even swedes second guess whether they might be real manuals. (When seen in a context where it was not immediately stated that they are imitations.)

Re: Quicksort explained IKEA-style

#54

Post by riffraff »

Arch-TK wrote: post #42
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.

Quicksort in FP? Surely you mean mergesort, that's the classic FP sorting example.

quicksort, e.g. the haskell[0] example is quite well known. Problem is, it's not real since it doesn't work in place defeating the whole point.

[0] https://qnikst.github.io/posts/2020-10-18-quicksort.html

Re: Quicksort explained IKEA-style

#55

Post by QuantumNomad_ »

junga wrote: post #10

I miss the default IKEA instruction to have two people for building even the tiniest piece of furniture.

How many people do you need to assemble a BILLY bookshelf?

Three!

One to read the manual.

One to be instructed by the first on how assemble it.

One to break up the fight when the first two get into fisticuffs over step 4 in the manual.

Re: Quicksort explained IKEA-style

#57

Post by TeMPOraL »

QuantumNomad_ wrote: post #53
TeMPOraL wrote: post #50

Earlier quoted context omitted.

Doesn't matter - it's just a FEJKA manual anyway.

But it does matter. I’m not sure if you are already aware and did it intentionally or if it was a happy accident, but FEJKA really is named that because it’s a real word in Swedish that comes from English with meaning very near to how you used it there. Swedish adjective “fejk” comes from English adjective “fake”. Swedish “fejka” is the verb form of the same, with the meaning similar to one of the English meanings of…

> I’m not sure if you are already aware and did it intentionally or if it was a happy accident, but FEJKA really is named that because it’s a real word in Swedish that comes from English with meaning very near to how you used it there.

I guessed as much; I'm Polish but know enough English that I burst into laughter when I first saw a fake plant labeled FEJKA in a local IKEA store. In fact, I couldn't believe they'd be this direct with naming. But then I don't know enough Swedish to translate the other names.

(Still wonder what kind of geopolitical order they meant when they named their wardrobe system PAX. Or is it just because you can pack absurd amount of things into it?)

> If they are to really look real without being real, they should be named in a way that would make even swedes second guess whether they might be real manuals. (When seen in a context where it was not immediately stated that they are imitations.)

Fair enough. I was just making an unsophisticated joke about the FEJKA line :).

Re: Quicksort explained IKEA-style

#58

Post by recursivecaveat »

stevage wrote: post #44
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

So what is the best algorithm when you have a bunch of people and want them sorted in order of, say, birthday.

Real objects are basically always either psuedo-radix because you have a good idea of the distribution and aren't limited to pairwise comparison, or psuedo-selection because the objects are big and heavy so you don't want to move them more than necessary. For people self-sorting psuedo-radix is definitely the way because they can self-parallelize easily.

I say psuedo because real objects have lots of properties both on the rearranging and comparison sides that are not quite the same as digital ones. For eg it's faster to compare numbers that have a large difference in magnitude, and it's easier to swap objects that are physically close to each other. So following a CS algorithm to the letter is usually slower than adapting a little.

Re: Quicksort explained IKEA-style

#60

Post by ninkendo »

lucaslazarus wrote: post #51
stevage wrote: post #44

Earlier quoted context omitted.

So what is the best algorithm when you have a bunch of people and want them sorted in order of, say, birthday.

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 place on the diagram where their seat is, then boards the plane in line. As each chunk boards, they’re already in the right order so that nobody is blocking anyone while trying to stuff their overhead luggage.

I’m not sure if any company has implemented the system but there was some test a company did of a bunch of boarding techniques and it was the most efficient.

Post reply on HN