What’s the Fastest Way to Alphabetize Your Bookshelf?
Let’s say you’ve got a bunch of books that need to be sorted alphabetically by author. What’s the fastest way to accomplish this task? Luckily, efficient sorting is a problem that’s been studied extensively in computer science and this TED-Ed video walks us through three possible sorts: bubble sort, insertion sort, and quicksort.
For more on sorting, check out Sorting Algorithms Visualized, sorting techniques visualized through Eastern European folk dancing, and a site where you can compare many different sorting algorithms with each other. (via the kid should see this)
Discussion 4 comments
Content warning for any other librarians in the audience: This article does not contain information relevant to an actual library.
It envisions a pretend book depository with pleasing colors, clearly marked spines, ample shelf space, and students eager to flock to the stacks.
This is a good explanation of how sorting works in computer programs. It will give you absolutely zero advice on more efficient shelf reading.
Ok now I want to read or watch about how actual books are shelved, what the tradeoffs are, etc.
While I appreciate a good computer science lesson, this has nothing to do with humans sorting books. Humans can compare many books at a glance in less time than it takes to reach for a book. A more realistic algorithm is a variant on bucket sort, where you make a stack for each letter of the alphabet and then sort each stack. This is also more parallelizable, for humans or machines. It also takes advantage of human memory and our ability to make ternary or more complex comparisons.
This distinction is actually relevant to CS, where real-world algorithm comparisons don’t assume comparisons are the limiting factor. Some classic analyses treat comparisons and swaps separately. On modern hardware, branch prediction failures (the CPU guessing wrong and having to redo work) are more relevant than the time it takes to do any work.
I've actually had to sort a whole bunch of books or CDs, and the easiest way (for me) was to place all the items whose creator's last name started with "A" into one pile, then "B," etc. Next, alphabetize the piles. Now start putting the piles on the shelves.
The practical flaw in this video is the idea that keeping all the books except one on the shelf at all times during the sort is a real goal.
And on a real bookcase or CD rack, be sure to leave some empty space on each shelf to allow for future insertions…
Hello! In order to leave a comment, you need to be a current kottke.org member. If you'd like to sign up for a membership to support the site and join the conversation, you can explore your options here.
Existing members can sign in here. If you're a former member, you can renew your membership.
Note: If you are a member and tried to log in, it didn't work, and now you're stuck in a neverending login loop of death, try disabling any ad blockers or extensions that you have installed on your browser...sometimes they can interfere with the Memberful links. Still having trouble? Email me!
In order to leave a comment, you need to be a current kottke.org member. Check out your options for renewal.
This is the name that'll be displayed next to comments you make on kottke.org; your email will not be displayed publicly. I'd encourage you to use your real name (or at least your first name and last initial) but you can also pick something that you go by when you participate in communities online. Choose something durable and reasonably unique (not "Me" or "anon"). Please don't change this often. No impersonation..
Note: I'm letting folks change their display names because the membership service that kottke.org uses collects full names and I thought some people might not want their names displayed publicly here. If it gets abused, I might disable this feature.
If you feel like this comment goes against the grain of the community guidelines or is otherwise inappropriate, please let me know and I will take a look at it.
Hello! In order to leave a comment, you need to be a current kottke.org member. If you'd like to sign up for a membership to support the site and join the conversation, you can explore your options here.
Existing members can sign in here. If you're a former member, you can renew your membership.
Note: If you are a member and tried to log in, it didn't work, and now you're stuck in a neverending login loop of death, try disabling any ad blockers or extensions that you have installed on your browser...sometimes they can interfere with the Memberful links. Still having trouble? Email me!