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
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.
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...
You are correct: https://doodles.google/
It doesn't seem to have the Rubik's cube, though
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.
I have no formal CS background or education at all, but have been working in IT for... over 20 years now?
So I'm not a "novice" in one sense, but in another my education on "algorithms" is pretty light and mostly through osmosis. Quicksort specifically is something where I've looked at the Wikipedia article on a number of times to understand but never managed to grasp.
The diagram made it click for me pretty much immediately. Yesterday if you asked me to implement a quicksort I wouldn't have had any idea where to begin, today I can say pretty confidently that I could implement something that would give you back a sorted list.
I'm probably an outlier here--minimal algorithms background, but an intuitive comfort with things like recursion--but at least some anecdotal evidence that it _may_ be useful to a novice!
Assume spades < clubs < diamonds < hearts, and ascending order for cards for all suits. Once you know the principle you can switch to US playing card order if you want.
In your first pass, divide the deck into black and red cards. Then divide black into spades and clubs. Then divide spades into <= 7 and >7. Then insertion sort the cards <= 7, then insertion sort the cards > 7, spades are now sorted. Clubs come next, divide into <= 7 and > 7, insertion sort, and combine. Split diamonds and hearts, repeat with diamonds, repeat with hearts.
“What about the pivot thing?” Well, that's because we don't know the midpoint of our set in a typical sort. So instead you can just grab a random card and then go through the deck to find all cards < that card. If you want slightly fewer passes, use median of three.
Even better: sort something physically large like several bookshelves of books or a record collection. You can't hold the collection in your hand and you're forced to use piles. You may even decide to work bookshelf by bookshelf first.
These are all good ways to develop intuition for sorting algorithms. Personally I always just use quicksort until I've come to a part of the alphabet where I can immediately recall which letter precedes every other then I do insertion sort. You might decide to use another hybrid sort like timsort.
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.
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.
This is why developer docs are trash. Because 90% of us can’t even identify when we are talking over everyone’s heads.
It's also technically not quicksort
How does FP handle the random selection?
You could use a monad/external state for an OS-level RNG, or define a purely functional PRNG
Surely you mean mergesort, that's the classic FP sorting example.
[0] https://qnikst.github.io/posts/2020-10-18-quicksort.html
Yeah this is lousy. This wouldn’t teach anyone anything.
The name feels like such a near miss though... Kvick (beyond being my surname) does mean quick and I see they changed to it from kwick to make the title "more Swedish". Great! But sört? That's not a Swedish word and feels very "trying to seem Swedish without knowing any Swedish". That letter would be pronounced somewhat like the u in blur.
Meanwhile sort in Swedish is sortera. Sort itself does mean sort as in kind/type. So perhaps Kvick Sort would be the best version of the name?
From my perspective as a Swede, however, making it sound Swedish is the same as making it sound Ikea-ish. Because Ikea products all have names which are either Swedish words or typical Swedish names.
[1]: quicksort is shown here, but the channel has plenty of others https://youtu.be/3San3uKKHgg
The first part is crucial, because if the group has two or more people exposed to CS courses, they'll invariably start negotiating the optimal algorithm to use while trying to recall the actual implementation, thus preventing any actual sorting from taking place.
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.
Practical CS theory isn’t really relevant here because it is N-parallel for N people.
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.
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
https://communities.sas.com/t5/Graphics-Programming/Fun-With...
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.
but if you don't understand it at all... I have bad news for you
Then again, maybe that’s not important to the author - it is a pretty funny illustration to those in the know.
After that you just have to understand exactly how partitioning works and get the ranges correct.
There are a number of strategies but random will indeed work and is simple to explain.
At least they changed the first word to Kvick because it means the right thing and sounds about right. And it happens to be my family name.
Unfortunately, the merge sort instructions doesn't make sense to me, specifically step 3.
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.
Quick sort with Hungarian, folk dance
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.)
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
I guess what it's trying to say is just "mark it as needing to be to the right", and then do the opposite in (4) and then (5) is where things actually move.
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.
https://idea-instructions.com/merge-sort/
and I think in this discussion we marvel the presentation, not the algorithm per se.
Merge sort requires additional space
Please can someone explain what’s meant by “bad worse-case runtime”?
I always thought they were a cost-cutting measure to avoid text in different languages. For me, they tend to be incomprehensible. Maybe because I have a very verbal style of learning, but I think it's not only that because I do find Lego instructions easy.
This captured the IKEA experience perfectly in the sense that I can understand it because I already know Quicksort, but otherwise, I don't think I would figure it out.
As it happens, these instructions were developed in the course of a 1st-year undergraduate course, so it's tried and tested in teaching noobs.
There is even a song-and-dance version (sorry, German lyrics): https://youtu.be/iq_TcSvWaY4
Cheers, Sándor Fekete, Professor for Algorithmics, TU Braunschweig https://www.ibr.cs.tu-bs.de/users/fekete/
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.
How about the direct translation “snabbsortering”? Or even “kvicksortering”, to more resemble the original? Both are perfectly valid swedish.
merge sort has a better big O, is cleaner conceptually, and is trivial to run concurrently.
bah humbug
