ฝัง
- เผยแพร่เมื่อ 27 พ.ย. 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.
![[TH]FFWS SEA Spring 2024 Knockout Stage - Day 11](http://i.ytimg.com/vi/Qr0L1ab9dLE/mqdefault.jpg)
![[TH]FFWS SEA Spring 2024 Knockout Stage - Day 10](http://i.ytimg.com/vi/4QaEryUGWQw/mqdefault.jpg)
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
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
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"
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
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
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.
“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
I’ve watched countless “15 different sorting algorithms” videos before this, now I’m a pro
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
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
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
"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 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
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
Me, an intellectual:
Watch the colours
that's so smart I would just procrastinate and not do it ..lol
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
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
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
TH-cam: 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.
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.
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 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
Of course, it is probably a lot easier to sort the books when they are all organized by color
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 🙄
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)
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
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.
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.
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
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
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!
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...
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
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
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.
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.
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.
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.
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.
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.
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 think my college library uses bogosort...
(To be fair, students probably keep randomizing the shelves.)
Lol
Ikr?
(in all grades)
haHA
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)
where was this video when I needed it for cs classes
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 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
It is in our programming class, thank you for making it easier to understand.
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).
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.
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
Rough/relative alphabetization first, then specific alphabetization. Put books in piles such as A-D, E-H, etc, then organize those sections.
this was so calming to watch
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. :)
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.
I'm happy to say this is usually sort of what I do when I sort my collections.
by far the best algorithm video I came across!
Nice intro to sorting algorithms!!
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.
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.
Other option. Write down all the names in a spreadsheet with their current position in the next column and sort by name.
Now you have a lookup table for each of the books.
This list can be used to sort the books really quickly. By going over the sorted list one item at a time, finding it's position in the first stack, and moving it to the end of the sorted stack. (The name of the book you're currently looking at can give directions to where you need to be looking for the next book)
"Write it down" haha no 💀
4:08 the prices have the gray dot effect
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.
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.
I love listening to this sort of theories. It’s fascinating.
USE THE VOLUNTEERS
YOU ARE THE VOLUNTEERS
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.
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 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.
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.
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
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.
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 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
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
I think about this video every week for some reason.
I've actually applied my Computer Science knowledge of sorting to real-world tasks, in a summer job right after high school at an insurance company. Of note were two tasks:
First were small (about a quarter of a standard sheet of paper) summary sheets torn from a printed packet, which had to be filed in drawers. The paper was also very thin (it was used with carbon paper to print multiple copies) and did not slide against other sheets well. It was impossible to "square up" a stack of them by tapping the edges against a table, for example.
The other task was sorting check stubs, by number.
There are two aspects: the comparisons, and the handling of the physical records.
For the thin paper index cards, it was easier to insert into the drawers if the stack was sorted first. Then, finding the next location to insert was just a little ways down in the same drawer, rather than being a random location. To sort these, I started with a merge sort technique and evolved it. I sorted as many as was easy to do "in hand" using insertion sort, keeping them spread out and separated with my fingers in one hand. Often it was more than just three or four because I'd have cards that went before the first or after the last already in hand. When that got to be too much effort, I made that one packet and started over. These were my initial groups for the merge sort, rather than just starting with pairs.
For the check stubs, I used a work table and did a radix sort. It looked like playing solitaire! But I was able to sort them so much faster than had been done by anyone else. They were not interested in having my teach others how to do it; rather, I was stuck with that job for the summer.
In software, you still have to look at two dimensions to the sorting efficiency: the cost of a comparison and the cost of a swap.
For the book example, I think a real person, without knowledge of Algorithms and Complexity Theory, would start by pulling all the "A"s into a bin, then taking those to a different area and sorting them using an insertion sort where you don't compare against every element one by one but jump the the correct position: more like the software binary search rather than sequential search; and inserting would push all the books along at one go rather than moving them one by one.
Then repeat with the "B" titles, etc.
I love it when I watch it again after learning sorting algorithms, as I finally know what the video was talking about.
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
Excellent, explained multiple sorting algorithms with their pros and cons (iterations) through a real life example. 👍
I just got a bunch of color sample chips that have number codes. I used the last method to organize them and it made the process a lot faster.
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.
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.
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!!
This is a fantastic way to visual different shorting algorithm
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.
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!
Partition with M and N at the same time, as one book (M on left, N on right) since M and N are the 2 middle letters of the alphabet.
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
I would use the roy g biv method to sort those books.
reminds me of animal riddle
less sorting needed in the middle (differation?) and more resorting in the beginning.
i think its similar to permutations laws.
This was in fact a lesson worth sharing
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".
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
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.
I'd personally use base 26 iterative bucket sort. It's easier for human mind do recognize if each letters match as opposed to comparing whether K is larger than H. It should result in nlogn performance as well.
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
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.
"The automatic sorting system is broken"
Of course it is
Can you make a video/series where you explain different sorting algorithms like Select Sort, Radix Sort, etc., without making it too hard to understand?
Radix Sort is just sorting the books by first letter, then second, then third etc.
Bonus Information: Mergesort is about as useful as Quicksort, but can't be done "in place" easily, hurting memory. Still, whenever you use a method on your computer that sorts, it's likely using Quicksort.
Also as a bonus...all these are examples of sorting in a "state machine". Obviously a human could do it much faster because humans are not state machines. I believe there's a mathematical proof somewhere that demonstrates it is impossible to sort in this sort of situation (i.e. a comparison sort) more efficiently than in an x * ln x algorithim, where x is the number of items (and the complexity of Quicksort).
But as someone noted below, Radix Sort is faster but only works on certain data types (i.e. non-comparison sort).