It looks like Step 3 may be using Hoare's original partitioning method with two pointers, which is laudable.
Quicksort explained IKEA-style
11–20 of 142 posts
Re: Quicksort explained IKEA-style
#12Seems to be:
1) Pick a random (dice roll) pivot
5) Move all values less than pivot before it, all greater than after it
6) Recurse to sort elements before & after pivot
Re: Quicksort explained IKEA-style
#13This 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.
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. (-:
Re: Quicksort explained IKEA-style
#14This is cool, but missing a LOT of details between steps 4 and 5, which is the meat of the quicksort. Actually, the first and last elements of step 4 would be swapped, which means the order depicted in step 5 is incorrect.
Re: Quicksort explained IKEA-style
#15I 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 implement the algorithm, and then from the program create IKEA instruction (or a mix of IKEA and railroad diagram). That way I can be sure I didn't skip any steps in the instructions.
[1] https://github.com/thomasmueller/rubiks/blob/main/README.md
Re: Quicksort explained IKEA-style
#16This is cool, but missing a LOT of details between steps 4 and 5, which is the meat of the quicksort. Actually, the first and last elements of step 4 would be swapped, which means the order depicted in step 5 is incorrect.
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.
Re: Quicksort explained IKEA-style
#17It 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.
Re: Quicksort explained IKEA-style
#18Step #5 is very much a "draw the rest of the fucking owl" step.
Re: Quicksort explained IKEA-style
#19If 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
Re: Quicksort explained IKEA-style
#20If 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?