Originally published at: http://boingboing.net/2016/11/29/this-is-the-fastest-way-to-alp.html
…
2 Likes
Biography
Mystery
Non-fiction
Books that arrived yesterday (alphabetical by title)
Reference
11 Likes
I’d actually go with a radix sort here. Since there are only 26 letters, you initially create 26 buckets (one for each first letter of book titles). That should give you on average 50 books per bucket. From there, you could either do a second radix sort for the second letter of each bucket (creating 26 sub-buckets for each first letter bucket), or you could just do a quicksort or insertion sort if the bucket is small enough.
I haven’t done the math, but I think that would be faster than a quicksort over everything.
17 Likes
While they are correct to pick Quicksort as the algorithm of choice, they seem to take it for granted that juggling even half of those 1200+ books is no big deal.
Technically off topic, but anyway…
Having actually worked in a bookstore I can tell you that the most realistic method involved breaking the books into fairly even groups based on the number of shelvers, having each shelver sort their books (by topic, author, then title, or series volume if appropriate). Parallel computing at its best.
21 Likes
Of course for physical books, this breaks down a bit. Something like a bubble sort works best. You start at one end and place each book into the correct order among the books to the left. This works because physical books are not computer files…
1.) you can easily move all books over one notch by simply pushing the entire shelf worth in one operation, unlike computer memory where moving every item from position n to n+1 requires a separate operation for each item. This is why I SERIOUSLY HATE storage solutions which have a individual niche for each DVD or CD or whatever.
2.)As you move forward, the books that you have passed ARE in order, so you can make an educated guess of where the next book goes.
6 Likes
And… they spent the first 2:30 of a 4:30 tutorial showing us the wrong ways to do it.
6 Likes
This is one of those niche real world cases where radix sort would be faster than quicksort, definitely.
Plus, the issues with variable key length that normally slow radix down compared to quicksort, are a lot easier to overcome with human operators rather than machines.
But, as an educational analogy to teach basic algorithms to non-coders, I think quicksort is the better solution to demonstrate than radix, in this case.
2 Likes
Fair enough, quicksort is more important for learning algorithms. Radix is just underrated and underloved. Hoping to change that. Even though radix is generally considered a niche sorting algorithm, in practical terms radix often outperforms quicksort especially when working with a fixed number of bits (eg- integers).
4 Likes
We literally just sorted a few thousand books and related media in the last week at my home (we moved). Fiction was the largest section, and we did it this way, though I did not know it was called radix. Alpha by author first letter of last name only, then for bigger letter groups, sort by author. Alphabetize from there. Within each author, tried as best to be chronological, by publish date. Could not imagine touching every book many times like required by quicksort. I think our max touches per book was 3, but the average was probably just over 2. Though technically in the final alphabetizing stage, each book was compared to, on average, half of the respective set in the smallest grouping. So essentially precisely your radix sort.
2 Likes
My wife insists we sort books by color. So, um, there’s that.
16 Likes
I’d then insist on an index.
2 Likes
Because that’s how it’s taught in most algorithm classes. Here’s the easiest way conceptually, here’s how long it takes, here’s a more complex method, and here’s how much time you save. This way, the student understands how to think about these problems.
4 Likes
I’m just impressed that you sort your own books. All my books are in piles in my basement from my last move.
3 Likes
We have student helpers for that, until they get frustrated and quit.
6 Likes
This drives me insane. Unless you keep an index, how would you ever find anything, unless you have few enough books that you know them by color, as well as by author or title. I do not, so alphabetical by author, then by title is my way of choice I have bookcases in almost every room in the house, and if it were only by color… well, I’d probably end by gibbering in a corner.
3 Likes
The results can look striking, but it seems impractical.
https://www.google.co.uk/search?q=books+sorted+by+color&tbm=isch
I’ve got to go through a wallsworth of shelving and three cases, one of them double-stacked, to sort out books to go to the local charity. Now, that’s a real timesink.
3 Likes
There are provisions for keeping series in order and grouping like sized books so it’s not quite that striking. I’d take pictures but they’re currently double stacked with board games and other assorted crap.
From: The International Education Standards Board
To: School Districts, Teachers, Educational Facilities, etc.
At its most recent biannual meeting the IESB made a decision to revise the accepted alphabetical standard, concluding that the old one was in need of updating. The new standard will be as follows:
While we acknowledge this change may be controversial some concessions have been made to the previously accepted standard. Committee members however agreed that this is a more logical order and should be adopted immediately.
In pursuit of greater uniformity it was also agreed that in all countries where the final letter is pronounced “zed” this practice may continue, but the eight proceeding letters will now be known as bed, ced, ded, ed, ged, ped, ted, and ved.
The term “alphabet” also is no longer applicable and will be gradually phased out in favor of the new term “ajkafilm.”
Because of metrical changes the old standard “Next time won’t you sing with me” song no longer works, but the IESB hopes to have a new song available for teachers in time for them to learn it before the start of the next school term. To this end we have hired Philip Glass.
Thank you for your cooperation. Please begin ajkafilmizing your materials accordingly.
16 Likes
That’s not bubble sort, that’s an insertion sort using O(1) insertions (which is reasonable for books, albeit perhaps not several hundred books). You can even use a binary search to find the insertion point, at which point I believe it’s O(n log n), and not O(n^2). Almost as good as a quick sort.
What I want is a good algorithm for sorting a book case, where individual shelves can fill up and you have to move books from one shelf to another to make space.
Seems impractical? It strikes me as a practice that’s only suitable for people who spend markedly more of their time staring at the colors of their walls than actually, y’know, reading.
I have heard of this benighted practice of color-coding one’s bookshelves. My wife and I share a visceral loathing for the very idea. Which is why we married each other, obvs.
11 Likes
