What's the fastest way to alphabetize your bookshelf? - Chand John
Vložit
- čas přidán 27. 11. 2016
- View full lesson: ed.ted.com/lessons/what-s-the-...
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.
Lesson by Chand John, animation by Anton Trofimov.
I love how the sign they chose for the broken *sorting system* is “Out of order”
this comment made me happy to stumble upon
that's hilariousss
I don't get it
Puncity
L Jackson order. Sorting. Ordering things by letter. No order = no sorting. and out of order = broken machine which in this case is used for sorting
My instinct would be to find all the books beginning with 'a' and place them at the start of the line, then 'b', 'c' and so on.
This is essentially Radix sort.
As a matter of fact, radix sort would be faster in many cases, including this one. After sorting the first letter, you can sort the second letter, by the third or maybe fourth letter, comparison sort would allow you to quickly sort the remaining subset of books.
To increase the sorting time even further, you can lump common title names together like "the" and "one" and exclude them from the primary and secondary sorts to save a few iterations of checks.
@@gbm7690 Same here
I would do the same thing. It feels much easier
@@johnwilliams1621 Mm, I thought it was called selection sort
“the books have been dropped off in one long straight line”
idk about you but that seems like a pretty inconvenient way to drop off books
especially, when the line is 1280 books long, which each book roughly 3-4cm thick (on average, i just looked at my bookshelf). It would make a line of 38-51m, IF the books are stacked tightly. If you take all the running into account, it will take far longer to sort. Plus, you'd probably need an ambulance after that:D
You missed the whole point. It's not about how books are arranged, it's about finding a fastest way to sort the books.
Stacking books in a straight line is for simplicity's sake.
@@erek r/wooosh
Mr. Communist r/ihavereddit
@King [Retracted] to be fair i was actually 14 when i posted the original comment, lol
Pretend like you weren't there when the books arrived and act surprised.
Yup. That's the way to go. Then when the students arrive tell them that the books havent come yet and when they point at the books just act surprised and ask them if they'd be so kind and help sort all the books :)
@@starsandstuff2100 this is what we call genius
and get fired
It's called "Surprise Sort", also sometimes called "Fired Sort"
All the computer science kids - "I've trained my whole life for this"
Years of academy training used
Basically yeah. Being able to sort stuff in a hurry is a rarely used skill but still nice to have.
insertion type beat
I was gonna comment this!
Shell sort all the way
How to make it faster:
*ask people to help*
multithreaded quicksort. Nice.
what if u have to friends
That's just asking for indeterminacy.
@Question Guy
What if the people who work there reject
Have one person help, and you suddenly have dual pivot quick sort.
Bogo Sort: Throw all of the books everywhere several times until it is sorted.
Best time O(1)
Worst time oo(infinity)
anywhere from several to infinite
So that would be a 1/1280! shot to get right. From that we can estimate how many times we would need to randomize on average, and see what's the quickest way to check whether or not that they are in the correct order.
To check if they are in order: Start at the first two books, and compare them, if they are in order move over to book 2 and 3, and so forth. If any two books are not in order, stop checking and randomize again.
This may take a while; let's get started!
@Unauthorized It should take way longer than that. 172 years if you're lucky
I’ve watched countless “15 different sorting algorithms” videos before this, now I’m a pro
Or you can take your time cause you know no one will have their shit together for the first day of school
Larissa Skyes and besides, your a student in a work study slot and get paid by the hour anyway.
+Thomas R. Jackson LOL Accurate.
The person who comes to the library on the first morning of class is also the person who's likely to freak out if they can't find a book though.
Put your shit together Summer! (I hope someone gets it)
how to troll
read more
OR you could repair the sorting machine.
But that could take more than a week
hey its the owners job not yours
Are you certified to repair the machine?
LOL
the repair manual is in amongst the 1200 books
Having worked in a library, and having a BSCS degree where we carefully examined Knuth “Sorting and Searching”, I can assure you that none of these algorithms translate well for human beings.
In the real world, we would most likely create small stacks of books, in groups that can be easily handled by a human - say, about 10 or so. Then sort each stack. Then merge the stacks, one by one.
Which is also known as mergesort.
@@faihan988 -- D'oh! I had never made that connection before. Sigh.....
As I humaun being I promise that I am a humam being
I would just add them and put them where I think is good
and then look at it to correct my errors
small problem computers can't just say "oh mate I feel like this 0 is not the biggest number since I saw a 329something so I'll start with mate"
That said, having worked in a Library shelving books for almost five years during college, I would use the Library of Congress system. Of course, that means I'd have to look up the LC data based on the ISBN of every book or magazine I buy. But there are tools for that, and you can easily scan barcodes with your phone or a dedicated barcode reader.
@@faihan988 there are probably over 50 different sorting algorithms, each with tons of different subsets. If someone managed to efficiently sort something in a way that meets none of those definitions, the number of sorting algorithms will simply go up by 1
CZcams: wanna know the fastest way to alphabetize books?
Me: well, it's 3am and has been years since I last held a paper book but OK
Lol.
The worst part is that the video is wrong. This isn't even the fastest way for a computer to alphabetize books, let alone a human.
What about *b o g o s o r t*
"It's all sorted!"
*looks at date*
"And right on time too."
*looks at year*
"Ah crud."
NO!! ANYTHING BUT BOGO SORT! PLEASE NO!
Gimmie 4734231678547 years. I will sort the first 2 books
My friend tried, he died before he could sort the first book.
Bogosort, assuming one second per comparison, would take an average of 3.05 x 10^3415 years, aka 30,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 years
Now that's efficiency
as someone who worked in libraries, you find yourself doing #3 almost automatically. (if there are less than 10 books, you use #2) Just wanted to express what a good example this is.
Yay!
I've been paid doing this since I was 13 by my local library
A Cat , your local library employs a cat?
A Cat , your local library employs a cat?
Massimo O'Kissed
Ya
Of course, it is probably a lot easier to sort the books when they are all organized by color
Me, an intellectual:
Watch the colours
that's so smart I would just procrastinate and not do it ..lol
pigeonhole sort
Or you could label shelves with letters, and put books on those shelves if they start with that letter.
Then sort each shelf. This is called a bucket sort.
bg6b7bft What you are talking about is called bucket sort not heap sort.
Fixed, thanks.
Yeah, then you'd get a more consistent version of the partitions, without having to note the separation between partitions and their groups. It's also better given the actual context of the situation.
Isn't that kind of just a more organized way of doing QuickSort's Partitioning?
bg6b7bft the problem is that you can sort just letters, not number or symbols
I love when I already know information that's taught is these videos, it gives me such a great false sense of intelligence.
Hobbes
YAY! FEIGNED DISCOVERY!!
TerrierZz SAME
Hobbes ikr
Isn't that just how advertise works?
Literally me because of Java and Python
"You work at the college library"
No I don't
_closes video_
“You do now. Now sort these books or else.”
Or else what? 😎
I came here to learn how to move my books,
Instead gained Computer science degree.
Inaccurate. You don't get a CS degree unless you learn about sorting algorithms six times.
@@christopherverdery1294 then watch this video ten times and become your local indian programming youtuber
But I can assure you will master in sorting algorithm if u go watch the visualisation of sorting 30 times.
Learn about the Dewey classification system and never get lost in a library again, this video gave me a headache since the alphabetically part is the last part in sorting books in a library
Get some college kids to do it for you. Call them interns. This will take about 1 second. Go have a smoke now.
Trap Music NOW.
Is your channel good?
Trap Music NOW. Oh and good method XD
Trap Music NOW. Why collage?? Why not University students?!? Weird Americans.
Alex Barker "Collage?" Weird foreigners.
Dane Maricic I don't get what you mean
I actually tried gravity sort once.
They stopped me before I could finish throwing them out the nearest window.
Intrafacial86 you should try intern sort. Very easy.
HA
My personal favorite is fire sort, but if you wanna do the longer way do goodwill sort.
I like not my problem sort
Or
Random order sort
lmbo
I thought this was actually about bookshelves, and was baffled why there weren’t 26 piles of books. I’m pretty sure I could sort 1200 books into 26 piles in 90 minutes or less, and then alphabetize each pile in another 90
I don't know, man, I have about 23 alphabetical piles of books (well actually 30, there's multiple piles for some letters), around 400 books, and it took several hours. 1280 books is a lot.
Exactly, that was how I sorted invoices 20 years ago as an intern
thats impressive!
I think this is called Radix Sort
That's a radix sort and it's actually really good for this kind of thing. I'd take it over quicksort for this job.
In practice I'd use Radix Sort (as others already suggested) instead of Quick Sort, and the reason is that comparing authors is not constant time for my brain (it takes much longer to compare Bradbury to Bradley than Asimov to Verne). For radix sort you only compare one letter (where the letters before are the same) so it should be a lot quicker.
Yeah, I got to the end of the video and went "well, another video that thinks quicksort is the best for any arbitrary problem..."
Quicksort could benefit greatly from a comparison method that could be told "until further notice, all items being compared will be between ___ and___", determine how much of the key matched, and then only look at the later parts of the key while processing items within a partition.
I used this, but I realized too late that I alphabetized by title instead of author.
isn't that how sorting books works though
cammiecookies but i mean what if you have books that are in a series with different starting letter in the title, imagining looking for them after you’re done. i sort by author too
@@mabellew6445 Sort by title of series. This results in all books in each series being next to each other (though, like with author, not necessarily in the correct internal order), but they will be easier to find assuming the searcher doesn't know the name of the author. For instance, if you are looking for (The) Lord of The Rings, but are not aware of Tolkien, you can still find it under 'L'.
cammiecookies
Haven’t you ever been to a library, or a bookstore? 😀
cammiecookies Come to my school it might be confusing for you
This would take be longer because I would be reciting the ABC's in my head trying to remember what comes before/after a letter
aahah same
That's why I would do the bubble emthod but reverse
People who know which number corresponds to which letter in the alphabet are scary.
Or in this case, people who knows which comes after a specific letter in the alphabet without reciting it is scary.
@Erhixon7
It's probably easy enough to learn to memorize... But except for librarians, it just seems pointless to do.
*me
Okay, my on-campus JOB in college - LITERALLY - was sorting and reshelving books and scientific journals. We had five floors, and all was based on the Dewey Decimal System. We had a "rough sort" area and a "fine sort" area, about 15 shelves for each area. After some experience, it took me about an hour to sort through a whole mess of books and load up about 10 book carts. Reshelving individual books took a bit longer, but we all got really good at it. Not to mention the leg muscles I built up squatting down with armloads of books. For some reason, those all-important scientific journals always seemed to be housed on the bottom shelves!
Oh yeah, I hate it when a shipment of 1200 books gets delivered at my house
Uh ikr so annoying
the only good thing is that you get a lifetime supply of books, but that will need lotsa sorting
I hate it even more when they dump it at the neighbours in the appartment because they came at a time I wasn't home
and jugding from the way a certain on-line shop has the tendency to pack items in boxes that are 5 times the item, such a delivery would probably block the whole street.
ughhh its just the worst 🙄
Easiest way possible.
1.) Don't touch the books
2.) When students find there book, they check it out.
3.) Have them put it in its correct spot.
4.) Take the day off
Corpsgrinder360 you're hired
their*
Waitwaitwait...
So you're saying the current method DOESN'T have to be changed?
So I'm not allowed to breathe?
ugh
not the dewey decimal system? either way i'd go through the pile of books, tossing them into 27 piles depending on their first character, then organize the piles, thats whats always worked for me.
Radix sort en.wikipedia.org/wiki/Radix_sort
That only works for letters, you are missing the point of the video..
Aren't the titles of the books made out of letters? You have to give me a little more to work with then just stating that I missed the point of the video.
John Donahue There are other things to sort other than books.
Eric Pive, what are you even talking about you convoluted turd? You're the one missing the point of this comment.
How I'd describe Radix Sort:
Go through the books, and put them in different boxes depending on their starting letter. This requires 1,280 movements. Then, go through each box and put the books in that box into different boxes based on their second letter. This also requires 1,280 movements. In the average scenario, you now have 1-2 books per box, and 576 boxes. You can now just put books on the shelf, and swap those that are in the wrong order. This is likely 2,560 more movements. If it takes 1 second to do a movement like before, then this takes around an hour.
But you need a lot of boxes
@@st_s3lios860 you can just pile them up......no need for boxes.....
@@st_s3lios860 Not If you apply Stage 2 to one letter at a time. (e.g. Do all the A's, then all the B's...
Well, I separate my books into languages and sizes. Greek, my native language, gets a portion of my library and English gets the other. From that, I go on comparing sizes, from biggest to smallest. The only exception I make is in a book series where I put them in series order no matter the size. Though that is usually not a problem, because series almost always are the same size.
That awkward moment when you don't have books, but its still useful for your videogames.
Elder Scrolls? I'm guessing Elder Scrolls. I know I try to collect at least one of each book, even if I'll only read a few of them.
i sold all my books to wiinterhold library
Usually whatever house mod I'm using that autosorts my crafting materials usually also autosorts books but also doesn't the inventory window automatically sort everything by alphabetical order unless you're using a different order in SkyUI?
43 hours on current Special Edition playthrough and I've never gone to Winterhold. Don't think I had any reason to avoid it but then I was so far in, it felt silly to visit for the first time.
I'm gonna organize all my switch games! First goes Mario Odyssey.... then in goes Zelda Breath of the Wild... DONE!
(I'm not joking, these are the only switch games I own xD)
I think my college library uses bogosort...
(To be fair, students probably keep randomizing the shelves.)
Lol
Ikr?
(in all grades)
haHA
By experience, just do pile of "a" "b" "c".... then class them in alphbetical order inside each pile usually by quick sort then put them all on the shelves. but you do you ;)
That first step is called "pigeonhole sort".
It's very effective when it can be employed, and I was expecting to see it mentioned in the video.
It mean, even by just looking at the wikipedia page for "sorting algorithm" you can find the pigeonhole under "Non-comparison sorts", a section they seem to have completely ignored when putting this video together.
But yeah, that's TED... (whose slogan should be "ideas grossly overlooked and over-simplified")
Instead of quick sorting each pile, arrange them by second letter and repeat with third letter and so on. This is Radix Sort.
As a volunteer/worker at an archive, jazz archive in Denmark. A place where there are 66.000 collection of jazz samples, cd's, vinyls, etc. I came across this video and learnt the quick sort method, it really helps the fast process on gathering samples together. And I got to mention that the archive only depends on volunteer worker, having no machine that could order the samples in chronological order or alphabetical order and besides the data base (PC), mostly everything is done by hand.
It feels really great on doing such work, by sorting things together chronologically and alphabetical order. The work is long and sometimes devistating, but the result are very satisfying.
Now, I have a dream education in working such places like an archive, libraries, old bookstore and such, cause everyday it feels like a long puzzle and every each bit and pieces has a story they have to tell.
The great thing I'm looking forward to, is to learn new ways on sorting things out.
"For those who played WoW back in 2004-2007."
It really makes it feel like playing World of Warcraft (vanilla) where you had to grind the last part to the endgame, really adventurous!
Thank you for sharing such knowlegde!
Cheers!
- Kaff.
what kind of library sorts non-fiction books into alphabetical order
This one
Did they say it was non-fiction?
@@Veronicz most college books are non fiction
Its pretende time laraujo
uh, okay you're right lol
It's also pretty easy when the books are a fucking spectrum of colors....
you ever try the colorblind sorting test? it's horrible
Nope not once,
It depends how good your colour vision is, I suppose.
oldcowbb I got a zero on it, a perfect score
All I have to say is Day-um
Its worse than the hemospectrum, for sure.
I feel like this is being over-complicated. Just sort all of them into piles of the same letter and stack them
That is called bucket-sort, and would only do the job if these books really just had one letter. But a book is not just called "A", but has a longer title. You would still need to sort all the books inside your "A"-pile. You would have some multi-step sorting similar to QuickSort -> RadixSort
Right
@@erikbrendel3217 Yep, and since the scenario is about physical books in the real world, being sorted by human beings, it would be the fastest method BY FAR. Every one of these sorting methods is ridiculously over-complicated and not at all feasible for humans, who'd have to be shoving entirely silly amounts of weight with all the shifting of books and whatnot.
And, additionally, this scenario COMPLETELY negated the secondary sorting of books. None of those methods included the full titles in their calculations, so trying to add that on to prove how smart you think you are is just embarrassing for you.
@@DocFunkenstein ...no. All these methods include sorting the whole surname, since "aa" would come before "ab". Takes no extra time and works the same way. They just showed them as letters for simplicity.
@@cityuser Wrong. Not a single example showed multiple cases of the same letter being repositioned within their subcategory, and most of the methods would require that.
as someone who works in a library and has to alphabetize hundreds of books per week it is absolutely DELIGHTFUL to realize that the system i've developed for myself is a real method with an actual name, and is the most efficient way to do it. bless! how have i never watched this video before!!
Any programmer here should be like "Oh.. so that's how they teach librarians time complexity..."
I pretty much thought it was going to be a metaphor for sorting algorithms, and when I saw her do bubble sort my suspicions were confirmed.
Or in your guys case, organize them by color.
the color is there just to help you see and imagine how the books move and how they should be
color is just a symbol of a letter
that way is more eazy to the eye.
Computers aren't very good at sensing humor.
I was just joking lol
Paris0825 same
;-p
def
Rough/relative alphabetization first, then specific alphabetization. Put books in piles such as A-D, E-H, etc, then organize those sections.
As a computer science major who was at one time an assistant manager at Blockbuster, I tried getting the employees to do quicksort on a pile of about 700 movies. In practice, swapping movies is the slow part, comparisons are basically free, and keeping track of your partition entries is easy for a computer but hard for a human. Insert sort ends up being better for humans for anything except an extreme example.
this helped me sort my yugioh cards
Bee Keeper this kills me 🤣🤣
if i had a penny for every time i wasn't cool i'd have *no pennies*
THEORICAL INFORMATICS PHD
The irony is that if you give this task to a human, they'll figure out a pretty fast way, without any of this knowledge.
all algorithms comes from humans. its no surprise you are already using 1.
this is because we can identify the letters, if instead letters were variables, we would need a formula
icgantshat Well, only humans before us figured out stuffs that we read, learn and watch today everywhere.
This is because the human brain is exponentially better at solving problems than computers for now. A.I. at its best can find information and spout it out, but learning how to sort on its own? I don't think a computer has ever "learned" how to sort. It is always "told" how to sort.
icgantshat yes this is computer algorithms for dumb computers, not really how humans sort books that can recognise actual letters. You know A is the start and z is the end and can see that instantly in a large pile of books.
This was my job when I was a student. In reality it depends on our how much space you got to work with, but none of these algorithms will work. I would find different sorting criterias like first letter, and split them into smaller piles, and add one more criterias until each pile is around 5-10 books, so the small partitions can be sorted and merged. We had around 200 books at a time, and it would take around 30 mins. Most others would just take one book at a time and place it on another cart. It would take them around 2 hours.
Step 1. Bucket Sort, if possible (alphabetical or by genre / dewey decimal group).
Step 2. Quick Sort each bucket / group / set of shelves, if practical (as books are put on shelves. Put 'N' or '0.5' divider in the middle, 'G' or '0.25' divider on the left, and 'S' or '0.75' divider on the right.)
Step 3. Insertion Sort each section.
Alternate Step 3. Selection Sort, if sorted items need to be complete, not missing any items, and ready for immediate use, which is rare.
You don't need step 3, as quick sort is recursive. First, you can either select a random pivot or the middle pivot, split the books into letters before it and ahead of it, then choose a random or the middle one for each of the sections. Do this until you reach a section with only one book. Put that section behind the last section. At the end, you should have the sorted books.
Just look at the color of the book. It makes it waaaaay easier.
Andy Shinnerl XD
That only works for her.
Why?
Can you *really* easier see 26 shades of color in the correct sequence, rather than just sorting by alphabet?
I find it much easier to know that Q is before R and after P, than to know that Lavender is to the right of Mauve but left of Taupe.
As someone who has quite a bit of experience working at the college library, here are my thoughts: I tend do something LIKE the insertion sort. But it isn't a pure insertion sort because I compare the book I'm working on to the books in the general area of where I remember it should go (someone previously mentioned this is an informed insertion sort). While the quick sort seems great in theory, the reality is that manipulating such a large amount of books is an important factor to consider (as in the example given). There are physical limitations. This would work best on one shelf, or on one book cart, but with that you're already working with such a small number of books that it probably doesn't REALLY matter. Also, most libraries already have a pre-sorted collection in which the new items are integrated into... which is a pretty significant factor to consider in terms of real world application of this system of sorting. Again, the theory is fun and I appreciate the thought put into it and the thoughts it's provoked (reading all the comments was entertaining), but real world application is a different story.
Very cool way to introduce these CS concepts, a cool thing is that many of the existing sorting algorithms can be heavily optimized given we know the range that the elements belong to (a to z) meaning that for example, for quicksort we can always pick the exact element that will partition our lists the best way, yielding a best case running time (assuming we can get to these elements relatively quickly rather than having to look through the entire list of books for them)
Thank you for this explanation. I went to 4 different videos trying to get a quick overview of what quicksort is and why it would be used and they all started by explaining the nitty-gritty details without explaining what it is used for.
Knowing the alphabet helps tremendously. Thanks Alphabits.
Exactly. If you're doing a quick sort, don't pick a book starting with an a or z because those won't make very good partitions.
Alexandre Pinho my man knows. Gotta have a good pivot or else q-sort is useless
Thanks, alphabet. Thalphabet.
Alpha bits is a cereal from Post. In case you missed that.
I did suppose "Alphabits" was not a typo at all, but I wasn't aware of the cereal.
Still wanted to make the _Look Around You_ reference anyway. :)
I take the books that start with A and put them in a pile, and so on and so forth. Then, I go through the A books and sort them by AB, AC, AD, AE; until all books are sorted.
well that would be Radix Sort :) depending on the length of the book names and the number of books, it might or not be better than Quicksort.
Edit: Actually, comparing two books by alphabetical order takes so long that your method is always better in that case.
I havn't watched the vid, tho, I'm guessing they are using QuickSort or MergeSort which is both have a complexity of n log(n). Doesn't Radix Sort have complexity of n*k?
Ares iSTAR they use quick sort. And yes, radix sort is O(n*k)
dude or u could just ask from help from the rest of the staff and that makes it a whole lot easier
TheMacpardo same
imagine using insertion sort with a list of books that is sorted in reverse, you'll end up just comparing all books and consuming the same amount of time as bubble sort, well it was the worst case scenario for insertion sort that's why insertion sort speed still varies with how the list is arranged, overall still better than bubble sort since bubble sort's speed is fixed.
where was this video when I needed it for cs classes
time sort is great, too.
it works like this:
1. treat the book titles as base 26 numbers (or however many letters your alphabet might have) and convert them to your preferred number system
2. acquire some alarm clocks and place one on each book.
3. Now set each alarm to its corresponding book's number (from step 1) of seconds into the future.
4. Now everytime an alarm goes off you just take that book and place it into your book shelf.
It's that easy.
But you need thousand of alarms
@@squidwardfromua semantics
It's a very cool thought, was wracking my brain for a bit.
It's O(N^2) tho each alarm hides a linear time operation, where it checks if each moment of time is equal to the 'time' of the book.
That's what I always do.
@@microwavecoffee I think it's O(n*m) with m being the largest number or in this case the longest book title. But that's usually just worse than O(n²) plus the massive overhead of setting all those alarms.
It's a similar trick to counting sort or radix sort in the sense that it's not comparison based and scales with the size instead of just the amount of your items.
Nice intro to sorting algorithms!!
Speaking as someone who works shelving at a library the 'quick sort' method brought up from 2:42+ onward closely resembles what I do in practise with most non-serial based fiction DVD's (movies instead of say seasons of a TV show or documentaries) since I'm not following the 'Dewey decimal system' or (in say a post-secondary setting) the 'library of congress' system. I appreciate knowing how there is a bona fide significance of sort to (2: insertion sort) and (1: bubble sort).
4:08 the prices have the gray dot effect
As the daughter of a librarian, and someone who helps organize books all the time, I find the quickest way to sort is to look for all the a's, b's, c's, so on. I don't know how effective this would be with that many books, but I do around 10-30 books at a time with this method. If it's the decimal system though, i section off each by their whole number than organize them in each section using the decimal. I then combine them again.
You are right! I believe the quickest way to do this is the way you described. In Computer Science terms (like Insertion Sort or Quick Sort) is Bucket Sort. You create "Buckets" of the books, and in this case we'd use A, B, C, etc. Then you can either repeat this process indefinitely within each bucket (for multiples) or decide to do an easier sort like the ones described to finish the smaller buckets off.
You have rediscovered a piece of computer science, bucket sort. QuickSort takes O(n log n) time, while Bucket Sort takes O(n+k) time; n being # of books and k being the number of significant bits, being 26 in this case
You have discovered bucket sort. It actually requires fewer and fewer comparisons relative to quick sort the larger the data set is.
Real library books need to be sorted more than once. First by category then by author, then title and sometimes even by edition, in that order.
depends on if they're fiction or non-fiction. Fiction, yes, you've got it. Non-fiction, by Dewey decimal number--alphabet's got nothing to do with it.
Hey TED-ED! Quick sort is cool and all, but have you ever tried bogosort? In rare circumstances, it can sort a completely random batch of books in one go!
Pretty much what the students are gonna do if you don’t sort it yourself
USE THE VOLUNTEERS
YOU ARE THE VOLUNTEERS
why not be like Tom Sawyer and just make some freshman do it! Convince them it's a game
nicekid76 so now it just takes O(1). World best algorithm.
+ParfaitEtrangerLive there's one in Bungou Stray Dogs... along with tons of other book titles.
Kaida Tong BUNGOU STRAY DOGS
:D! You've read it as well!
This should be titled "some basic ways to program a library-ordering software", but no intelligent human being would ever do any of those things: if I pick A, why on earth should I compare it with N, M, L and all the other inbetweens rather than place it at the beginning as if I've never seen the alphabet in my life?
You still literally compare it. By reading that "N" on the shelf, you mentally note "nope, not here" and just skip the physical step of swapping the book all the way down the line, until the final spot it should go in.
@@amandaslough125 But I don't. Because I have a memory and if I have already pick a D a G and a K, and then I found an A, I know that I must go back at least three positions, I don't need to swap them phisically or mentally. It may be not 100% precise, but it's not like each and every time I have to start from zero.
@@valeriacavalloro2729 You're still comparing. It's just nearly instant because your memory is so familiar with the alphabet. Yes, you have a memory. But you're still comparing them since your memory is telling you G goes after A-F but before H-Z.
@@amandaslough125 Honestly, I don't get it. This is like saying then when you multiply two numbers you are actually doing a bunch of sums very quickly in your mind without writing them. You may have to compare the ones in the approximate final position to find the exact spot, but you are not doing two thousand and oh-my-god hundred swaps (physically or mentally).
*You're proposing a valid optimization for sorting books.* I think the other people in this thread have misunderstood what you're proposing so let me see if I understand you correctly. I think you're saying that since we know nothing can come before A, we should just put all the A books at the start of the bookshelf. This is a really good point!
Why should you bother with N, M, and L? You shouldn't! We know that some books HAVE to be in certain areas because we already know our ABCs. The video only explains Bubble Sort and Insertion Sort for the sake of introducing the idea, and after introducing them, it explains why they're bad.
What happens if we put all the A books in a group at the front like you suggest? After that we have every other book, which we now know range from B-Z. So let's put every B book at the front of that. Then we have books ranging from C-Z, so let's just put every C book at the front of that, and so on and so forth. The books of course have more than one letter so we need to sort them by the rest of the name. We can just zoom in on the A group and repeat this process for the second letter of the name. Then we can do it for the B group etc. This is an algorithm called Radix Sort.
Radix sort is actually a potentially a pretty fast method for sorting things. Doing some math, we can determine that it could beat Quick Sort if the books' names weren't too long (Roughly 10 letters, but my math is iffy)
They're all alphabetical, but you still have to shelve them. Sorting them into groups based on genre and section in the library first would probably save a lot of time with shelving, and would make your groups to sort at once a lot smaller.
You also can use radix sort
Artur Der Große
everyone gangsta until the librarian starts getting 10 hands
Henry Guerra
There are plenty of videos explaining radix sort, also known as « bucket sort ». Go look some of them up :p
you should sort them by their letters so there is no any number then how will do you use radix sort ?
@@ahmetbcakici You assign a number to each letter in alphabetical order
@@42scientist Radix Sort is not exactly Bucket Sort. They both are a non-comparison distribution sort, but the way they go about sorting is not exactly the same.
I work at a library, so if we ever have to sort this many books, I'll share this strategy with my coworkers!
You'd be better of doing a Bucket Sort; i.e. a pile for each letter, then recursively repeat on the second letter of each pile, then third, etc. - you'll just need quite a bit of space
Yes, quicksort isn't that quick in my opinion.
Rebecca Potato I don't have enough memory for quicksort.
Yeah, generally, my coworkers and I divide up our books into their Dewey decimal categories by hundreds, and then fiction by letter, in piles. It gets a little tricky when you get to the kids' books and their many strange categories, but at least it narrows down the areas in which they need to go. XD
this was wrong. Quick sort is not even the fastest comparative sorting algorithm. Since books have a natural order you can use a non comparative sort. Yes your method of dividing into dewey decimal by hundreds is better than the quicksort they listed. Quicksort is generally fast but only for comparative elements.
this was so calming to watch
Me: Sees title
Me: Perfect for my bookshelf!
The video: You work at the college library
Me: This is normal, right?
I always orginize my books by height. the tallest/biggest book comes first, and the shortest/smallest goes last. It makes it look nice and neat. If I have lots of books with the same height, (which i do) i organize them by series or color.
me too
OCD for the win!
Kaden Lacey I usually organize my books by order in sieres and hight, if a book doesnt have a sieres or i dont have the other books, i just do it by hight.
Looks neat and organised, BUt impractical. Depends on what you would prioritize
It looks neat but this is a college library so a lot of students will be annoyed because they can't find their book because they don't know the height.
Why aren't the books organized by subject?
lestrange Maybe they're fiction?
Jeremy Downey then why would you sort them for the next day? No kid would go to the library on their FIRST day of school.
Good point
At the library I volunteer at it's done by genre then alphabetized for fiction.
Even if you sort them by subject, you will still want to alphabetize them.
as someone who worked in a library this isn't how you sort books, this mathematical model should describe something else. When books come you can scan them into their categories based on a database, this generally means you have 8 smaller categories already. And on top of that when you get new books you usually have lots of duplicates. The time spent sorting the books are also nothing compared to tagging the books, they need to be chipped or striped so that they make noise if they are checked out and they need to be logged in the new system so that you can lend them out to the students. And if you are forced to sort though so many books in the middle of the night you need to just stop, put the books in the back room and get through it tomorrow morning, it's okay if a book isn't on the shelf when a student comes and asks for it, you can add their email to the system so they will be notified the moment you have the books tagged.
Your model would be much better for something like clearing up a shelf at the end of the day when people have put the books back in all kinds of places and even then a lot of libraries choose to what pictures indicating different topics so you can more easily spot ones that are in the wrong spot and then you just find each books right spot.
With an insertion sort, you can do the comparisons much quicker than one per second. It would be about a second or two for each round of sorting. It is the actual physical moving of the book in and out the pile that takes time. Different for computers though.
I love it when I watch it again after learning sorting algorithms, as I finally know what the video was talking about.
Why not just go along the line and take out all the A's and put them all in a pile? Then do the same with the other letters and put them all in their respective piles. When that is finished, you then alphabetize the piles.
laki74 congrats, you are now using bucket sort
Luiz Sarchis is bucket sort effective?
Jarvis-Gaming yes bucket sort is more efficient than quick sort, especially with large data sets. But in terms of computer science, it's a different concept than the sorting methods listed here
Yes, this way is more efficient. O(N) vs O(NlogN)
merge sort worst case , average and best case is O(NlogN) .while quick sort worst case is n^2.
I use this daily! I work in a medical clerical position where I get hundreds of papers every day that I have to sort into their specific charts for different patients. It’s so much easier when it’s alphabetized because I can get all of the papers for one client into their chart all at once. So I use a version of quicksort that works- making piles for subdivisions of the alphabet. If a patient’s last name starts with A-C, it does in pile 1. D-F, pile 2. So on until we get to Z, dividing piles where appropriate (R and S need their own piles because they’re common, while U-Z usually are fine to all go in one pile). Once each pile is completed, I can then insertion sort and bubble sort these smaller piles, paper clipping together any two or more papers that are for the same client. Then it’s so much easier and faster to file!
That’s more of a bucket/radix sort. It’s much better than quick sort for sorting physical objects, because people aren’t computers.
"The automatic sorting system is broken"
Of course it is
right click, sort alphabetically. done.
And yes I know they are talking about physical books in the video. but digital books and the new kindles work great (the old kindles may have turned some off)
legendp2011
0:22 "the automatic sorting system is broken"
I was just making a joke about how physical books can be dated, when organizing your books is a million times faster on a computer. This scenario isn't important though, it is just an example for a way of thinking they want to demonstrate, so they used this as an example. I made a joke about the scenario, but I understand the scenario isn't what the video is REALLY about
legendp2011 and I knew that was what you meant.
The point of the video is to demonstrate how the computer algorithm does the sorting. Physical or not, the same principle applies.
Min-Chul Kim I know, read my reply above. I was just joking around
"Quicksort" is for puny, one-dimensional mortal beings. Here is the fastest way to sort these books: Pile every book on a flat surface that you can lift. Throw it at the shelves as hard as you can. Now, here is where it gets tricky. Theoretically, in one of the infinite amount of universes, these books have arranged themselves perfectly on the shelves.
Job done.
That's called bogosort lol
not quite, bogosort won't always be done with the first try, whilst IMB's version will
but are you living in the right universe?
by far the best algorithm video I came across!
This helped me file students' tests and workbooks. (Each is named by subjectn student's name, and number).
The one who worked there for a year was surprised that I finished sorting before him.
this is my strategy: just separate them in letters and sort it out.
thats called bucket sort.
likrmoge😂😆😆😆🤔😥😣😏😏🙄😶😑😐😙😚☺🙂🤗😇🤔😗😘😍😎😎😋😊😉😆😅😅😃😃😋😂😁😀😀😚😚😚😚😚😚😚😚😚😚😚😚😚😚😙😙😙😙😙😙😙😙😙😚😶
my method is: call the freshmen for doing it
its called being a lazy b****
That's called radix sort
For sorting books *Bucket Sort* would be 3 times quicker than Quicksort.
Bucket sort in this case would mean that you first sort books to different piles based on their first 1 or 2 letters and then you sort those new groups individually. In this case Bucketsort would take you 4096* seconds
*1280+ (22 x 128) = 4096 secons. That would be 1.1 hours.. 3 times quicker than quicksort
Good to see that someone shares same ideas :)
You know I don't get much of this but I've read many methods from the video and the comments and bucket sort really seems like the most logical algorithm to go with
Bucket sort would definitely be the best algorithm. You can even speed it up by having multiple people each sort a subset of the pile of books and then merge them asynchronously.
Margus T i was thinking the same thing
Yeah the first thing I thought when I saw this problem was, "well, first I would go through and pull out all the A's, then the B's, etc., and sort those separately"... sounds way simpler just in the explanation alone
I love listening to this sort of theories. It’s fascinating.
It is in our programming class, thank you for making it easier to understand.
I would use the roy g biv method to sort those books.
I have an 80 mark test comprising of 7 chapters in biology tomorrow and here I am learning how to sort my books in alphabetical order. Thank you Ted Ed.
Did you pass
Did you pass
Did you pass
I didn't even know about these strategies, but I do a variation of the last strategy. I know that "m" is the 13th letter in the alphabet, so I divide the books into piles of "Before 'm'" and "After 'm.'" If the 2 piles are still too big, I do this again but with 'g' and 's.' So, I'll have a pile of "A-G," "H-M," "N-S" and "S-Z." Usually by this point, the books are sorted enough to quickly rearrange each pile. I studied office administration and alphabetizing is one of the sorting methods that we learned about.
Radix MSL sort:
Group all books into piles where each pile contains a book with a title that begins with "A", "B", "C", ... Then, group each group into sub groups, this time alphabetizing the second letter. Keep moving letters until the full titles are covered.
Well if you are a computer then ok, do quicksort, but a human can predict where the book will be more or less, making an informed insertion sort... with very few comparisons. Computers have to use quicksort because the processor is a very fast-working stupid.
To be fair, with the right algorithm a computer can do much better than quicksort. Quicksort is great for completely random sets, but book titles /aren't/ random so there's various heuristics that can, for average book collections, greatly cut down times.
@@doctorwhouse3881 counting sort?
@@doctorwhouse3881 And giving the computer info about alphabets it can just divide the books into separate lists and sort them even with primitive sorting methods really fast
Well, the video presents this problem in a context where it's specifically stated that the automatic system is down. But really, for humans, it's totally ridiculous to compare and swap books 2 by 2 when you could just *insert* the book you're holding where it belongs in the part of the line you have already sorted and in which you already know what is where ("insertion" is the method's frikkin' name !)
I really don't get what they intended to do here, either they shouldn't have set up this whole "automatic system is down" context and presented it as plain computer logic, or they should have presented the insertion method the proper human way.
This is flawed. Those sorting algorithms are based on the fact that a computer can only compare two things at a time. But we can compare many more things at once.
I don't need to compare an A with all other letters to know that it comes first. I know that A is first. Of course I still need to compare books that start with A
Nilaksh Singh the thing is even computer can divide everything by letters and then sort out each part. This is called bucket sort. The authors of video just used bad example.
BUT... usually a sorting algorithm is going to be working with numbers.
Your method is just as flawed. You assume that you know the nature of the distribution of the books and that they will fit into your predetermined buckets (A-Z). What if all titles started with A. Your first pass of 1280 comparisons would be a waste of time (it would put all titles in the A bucket). So whilst a choosing a random book as the first partition still carries the risk of it being the first or last in order, random start lets the nature of the distribution decide where the partitions are.
Stinger Tuck so what? You can continue using bucket distributing till the end. The time will be linear to the total number of letters anyway.
Stinger Tuck I'm not talking about qsort modification. I'm talking about another sorting algorithm that's based not on comparison's but on counting. Google up "bucket sort".
I would throw all red books to the left, the purple books to the right, the yellow a bit before red, blue a bit before purple, and green in the middle.
i thought bogo sort would be the best answer
1 day...
*300,000,000....
how does bogo sort even work tho
@@rubberd6cky it sets all things randomly. If all things are in order - it's done. If not, it does the same thing - put things randomly in places. It goes on until all thing are sorted out. It's the fastest yet the slowest sorting method. All depends on "luck"
Sorry for eng
@@GewelReal ok thanks, your english is perfectly fine kskskskd
Or tell them to find their own book since I don't get paid enough for this shit.
+John B I know right
I honestly think I needed this during my Data Structures and Algorithms class. Would have made it A LOT easier to grasp.
(Kudos to my professor. Recognized bubble sort before they called it.)
I work as a librarian in a university library, and...we don't have any "automatic sorting system". So does anyone else have one? Other than like Finland with their robot which reshelves their books
Yea, the example scenario is a very bad one for teaching computer sorting techniques. Human eyes and hands are required for sorting physical books. It's funny reading all of these computer science geeks comments, as if they have a clue. I've been a volunteer in a library sorting and reshelving books.
You technically could copy/paste all the titles of all the books and sort them from A to Z in a Word or Google Docs document. That counts as an automatic sorting system, even though you have to order the physical books with your own hands. Plus, even if many books started with the letter A, what you look for first is the category. An A in Mistery will belong in a totally different place than an A in Biology.
@@sofiaroura9652 very good points. Such a bad scenario for an example. The Word/Google sort might be helpful, especially if there were tons of books, but with the added divisions into genre, it seems more likely to be a waste of time. You're going to have to use your eyes anyway to do a lot of the sorting.
@@HeidiQuist most of us are suggesting a radix sort, which goes "gather the books starting with each letter of the alphabet into their own box, then sort your A's and so on." The video is committing the sin of assuming quicksort is always the best for every situation.
Yeah... Believe me, NOBODY comes to issue books the first few days from the library.
The Newbies are too busy getting lost,
The Oldies are too busy catching up, &
The Procastinators are getting a visit from their friendly neighbourhood Panic Monster!
Im seeing the panic monster right now
lol i saw that video XD
_references intensifies_
Anyone reading this who doesn't know the panic monster?
Great, you're one of today's lucky 10,000!
@@TheEnderLeader1 was a reference to another TED talk titled "what's inside a brain of a procrastinator" i believe
If we consider book names are finite strings, couldn't we use Bucket/Radix sort for even faster results?
I think the point of the video was to explain the basics of computer sorting algorithms, which it does well. I don't think it wanted to teach the most efficient algorithm we've got so far. Just the kind of limitations you have to face (ex: compare 1 book to another, 1 at a time, instead of being able to visually identify group of books in 1 look).
Trilioh
Bucket sort would compute faster but requires vastly more processing (in the example, space) to come to the same result. I think, as the other person intimated, that the subroutines inherent to a bucket sort are just beyond the scope of the example.
Bucket has WC complexity O(N^2), radix is slower for log2 N < log10 max value, which will be true as number of books exceed 10^26 so quick is kinda general case. but yea for this radix is faster