You work at the college library. You’re in the middle of a quiet afternoon when suddenly a shipment of 1,280

different books arrives. The books have been dropped of

in one long straight line, but they’re all out of order, and the automatic sorting

system is broken. To make matters worse,

classes start tomorrow, which means that

first thing in the morning, students will show up in droves

looking for these books. How can you get them all sorted in time? One way would be to start at one end

of the line with the first pair of books. If the first two books are in order,

then leave them as they are. Otherwise, swap them. Then, look at the second and third books, repeat the process, and continue until you reach

the end of the line. At some point, you’ll come across

the book that should be last, and keep swapping it with every

subsequent book, moving it down the line until it

reaches the end where it belongs. Then, start from the beginning

and repeat the process to get the second to last book

in its proper place, and keep going until all books are sorted. This approach is called Bubble Sort. It’s simple but slow. You’d make 1,279 comparisons

in the first round, then 1,278, and so on, adding up to 818,560 comparisons. If each took just one second,

the process would take over nine days. A second strategy would be to start

by sorting just the first two books. Then, take the third book and compare it

with the book in the second spot. If it belongs before the second book,

swap them, then compare it

with the book in the first spot, and swap again if needed. Now you’ve sorted the first three books. Keep adding one book at a time

to the sorted sub-line, comparing and swapping the new book

with the one before it until it’s correctly placed

among the books sorted so far. This is called Insertion Sort. Unlike Bubble Sort, it usually doesn’t

require comparing every pair of books. On average, we’d expect to only need

to compare each book to half of the books that came before it. In that case, the total

number of comparisons would be 409,280, taking almost five days. You’re still doing

way too many comparisons. Here’s a better idea. First, pick a random book. Call it the partition and compare it

to every other book. Then, divide the line by placing all the books

that come before the partition on its left and all the ones that come after it

on its right. You’ve just saved loads of time by not having to compare

any of the books on the left to any of the ones

on the right ever again. Now, looking only

at the books on the left, you can again pick a random partition book and separate those books that come

before it from those that come after it. You can keep creating

sub-partitions like this until you have a bunch of small sub-lines, each of which you’d sort quickly using

another strategy, like Insertion Sort. Each round of partitioning requires

about 1,280 comparisons. If your partitions are pretty balanced, dividing the books into 128 sub-lines of ten

would take about seven rounds, or 8,960 seconds. Sorting these sub-lines would add

about 22 seconds each. All in all, this method

known as QuickSort could sort the books

in under three and a half hours. But there’s a catch. Your partitions could end up lopsided,

saving no time at all. Luckily, this rarely happens. That’s why QuickSort is one of the most

efficient strategies used by programmers today. They use it for things like sorting items

in an online store by price, or creating a list of all the gas stations

close to a given location sorted by distance. In your case, you’re done quick sorting

with time to spare. Just another high-stakes day

in the library.

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.

Very useful, but dont know when I will find it necessary 😂

Dump all of the books off of the shelf and into piles according to the letter they start with

I should of watched this before my ICT exam

You forgot Bogosort/Monkeysort: Put them into the shelf in random order and hope they're sorted. If they aren't, take all books out of the shelf again and repeat the process.

All the computer science kids – "I've trained my whole life for this"

GCSE Computer Science anyone?

The video is how to get a person to sort things; but you use computer coding to determine the number of comparisons. If I as a human see a book that starts with Z; I make no comparisons. I simply place that book at the end.

I think this is satysfing her voices aswel

Errrrr. Don't think quicksort is really used that much, as it's worst case is still n^2. There are much better sorting algorthms out there that are stable no matter the case.

Damn the algorithm sorting videos are broken yall need to repair them

Counting Sort ^^

Radixsort would be much better. especially for a library

Actually, Counting Sort would be faster if there was a numeric order at the first place.

Google SORT – search and order!

Am I the only one thinking merge sort is better ?

Didn't saw the vid yet, is it quicksort?

Are Ted x vids for kids or for everyone?

Nah, who reads a book? No one does that anymore.

Don't worry I have the time.

WOW – Thank you very much!

This is very Santiago stuff.

Surely another faster way could be sorting the books by their first letter by putting them into 26 piles, and sort each of them by their second letter?

OR you could not care nobody ever sorts books

I don’t have a bookshelf…

Memorize the alphabetIt's literally in the name : QUICKsort …

LSD sort hahAAA

For anyone who curious about another algorithm, like sort algorithm, you can check out visualgo (i forgot the domain), its a link dedicated to visualize almost any kind of algorithms for programming

Just straight up picking the books by alphabetical order is probably the fastest.

1280 books so look for the As and put the out the pile and create a pile to the side As first then Kick the Bs Then Cs and so on

Lol, first I thought it was the merge sort

Bubble sort

your not ted.

This reminds me of the Statistics class and its grade…

Get 25 other colleagues and bring 26 containers. Everyone is assigned an alphabet from A to Z. Everyone takes a book belonging to their alphabet and throw into their containers. Now everyone just need sort their books according to their letters. Voila.

Never having to compare any of the books on the left to any of the ones on the right.

What about gravity sort?

Master dark powers and make the books sort themselves.

Considering it's a university library, I'd imagine a significant portion of the books are textbooks. In that case, sorting them by subject might be a good start. Then you can sort each subject's group with Insertion Sort.

Shell sort.

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!

Of you can just search the all books with an a and then b and then c and so on (sorry for the bad english)

add like 5 hours for me to recite the alphabet

Um the books are color and letter sorted

Just Follow the color

1:00 or you could just take it out and put it at the end

Just put the book in the shelf in any order and let a person get annoyed and fix it for you

This video failed to acknowledge the non-constant random access time

How does sorting 26 book take 9 days

I know this is a programming thing… But are librarians really trained on how to sort books the most efficient way?

Batch processing!

Call your co workers

looks at my disorderly bookshelfwatches videodoes nothing about bookshelfOr you could just ask for them to bring them in alphabetical order

Yo this is so smart

Why don’t you just use the psychic powers this person some how has to sort all of the books at once?

lol they made the "Library" in real life

Okay but who uses the first two in their pure form? You surely don't compare every book any other.

That's basically how sorted my magic card collection :

Make 3 stacks (A to F, G to N and O to Z is the most balanced partition i came up with by trial and error in french).

Make 6 stacks A,B,C,D,E,F.

For each First letter do the same 3 stacks as in the beginning for the second letter and keep going until each letter is sorted

Put every A to F stacks together in order, take the second stack and repeat the process …

I sorted thousands of cards that way in a few hours ^^ if it can help anyone 🙂

step 1: be born

step 2: learn the alphabet. you don't even need to know the sounds the letters make just that the symbols go in a specific order. If you already know counting, you have a head start. ask an older friend or a family member to tell you about the alphabet or wait until you're in school.

step 3. watch this video

your shelves are gonna be so neat

Why is the sun moving backwards is time going in reverse

Step 1: find book A

put book A in the start

Step 2: find book B

put it after book A

SIMPLE!

Repeat

Bucket sort, also known as Radix Sort, is much faster than the Quick Sort method. Take all the books beginning with A and put them into one box, B goes into another, etc. until you get to Z.

Then depending on how many books are in each subset, you could either do insertion sort for that subset, or organise them into smaller groups by the second letter.

I normally do A to Z

Your whole system has one flaw. I can't tell if g comes before i without reciting the entire alphabet to the point where I meet one of them. This goes for other pairs too. Its just not that quick. However if I put all my books on a diffrent place I can recite the alphabet just once to get the books in stacks and for those who have more than one kind of book maybe a few more times but it will be overall quicker

0:16 That's a lot!

Where my programmers at?

Hi i am a human who need to manually sort data at school, i cant use computer and all sorting algoritme i know take more than 16 minute to execute, using my human system, paper and pen. do you have any suggestion to solve this issue?

Can’t you just get the A book and put it on the start and go on?

Just use color coding…Causally uses gravity sort and sorts them by magic.

In intsertion sort with my luck A would be the last one.

Simply use the rainbow pattern

Or use Radix LSD Base-10 sort like a boss.

Or you could just bogo-sort it

I did it with books on my bookshelf

Who else heard Shitmint

I still prefer bogo sort

why not just choose the middle book as the partition, instead of random?

Divide and Rule

0:10 "when suddenly, a sh**ment of 1280 different books…"

Its caled radix base 10

nah ill do radix lsd base 10

Me: *uses bogo sort *

Actually it’s the bogo sort if you’re lucky enough

I used to do QuickSort with my Pokémon cards when I was little, but now I just sort them by real order as in; Generation 1: Bulbasaur, Ivysaur,Venusaur, and so on. Every time I get new Pokémon cards, I need to sort them but it’s always a pain because I’d always see a mistake in my binder, so I have to restart, and I had more than 700 cards, and that’s just the Pokémon, not including the trainer cards, the barcodes, and all that, coming with a total of more that 1000 cards. But now I have tons of extras, so I started to sell to get rid of them.

Prices:

Regular Card: $0.75

Pack O’ Cards (Ten Regular): $15

Rare Card: $5

Rare Pack (Ten Rare): $50

Trainer Card: $0.50

Pack O’ Cards (Ten Trainer): $5

Anyway, yeah I just really like to do this stuff and now, I’m one of the greatest Pokémon collectors in my school!

Ever tried the it's not my problem sort?

I suggest using bogo sort

Mergesort is a better bet; best worst and average are nlogn

Like quicksort, split into 128 sets, sort each set, and compare the least of each of every two sets. Put the smallest on the left most. Repeat with the least of the set with one less book each step. Continue with the next two's each step. Now do the same for the sets of 20s, 40s, until 640s.

This was in fact a lesson worth sharing

I would just arange them with colour

No

Bogo sort is the easiest

If you use Gravity Sort or Counting Sort it will be done instantly

Or just sort them alphabetically like a normal person.

im the new troop librarian in my boy scout troop, this helped! thanks!

Or just leave it like that,

Its not like millennials has books on their phone

Jacksucksatlife has more subs than this bro

My first instinct would be to sort all the books into piles by letter, then alphabetize the piles.

But but, quicksort is O(n^2) worst case

MOM, can you help me with these books ?