This is the fastest way to alphabetize 1,000+ books (or anything else)

From TED-Ed:

You work at the college library. You’re in the middle of a quiet afternoon when suddenly, a shipment of 1,280 books arrives. The books are in a straight line, but they're all out of order, and the automatic sorting system is broken. How can you sort the books quickly? Chand John shows how, shedding light on how algorithms help librarians and search engines speedily sort information.

Notable Replies

  1. Biography
    Mystery
    Non-fiction
    Books that arrived yesterday (alphabetical by title)
    Reference

  2. 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.

  3. 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.

  4. agies says:

    My wife insists we sort books by color. So, um, there's that.

  5. 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.

Continue the discussion bbs.boingboing.net

75 more replies

Participants