What's the fastest way to alphabetize your bookshelf? - Chand John
-
0:07 - 0:09You work at the college library.
-
0:09 - 0:11You're in the middle of a quiet afternoon
-
0:11 - 0:18when suddenly a shipment of 1,280
different books arrives. -
0:18 - 0:22The books have been dropped of
in one long straight line, -
0:22 - 0:23but they're all out of order,
-
0:23 - 0:27and the automatic sorting
system is broken. -
0:27 - 0:30To make matters worse,
classes start tomorrow, -
0:30 - 0:32which means that
first thing in the morning, -
0:32 - 0:37students will show up in droves
looking for these books. -
0:37 - 0:39How can you get them all sorted in time?
-
0:39 - 0:45One way would be to start at one end
of the line with the first pair of books. -
0:45 - 0:49If the first two books are in order,
then leave them as they are. -
0:49 - 0:51Otherwise, swap them.
-
0:51 - 0:53Then, look at the second and third books,
-
0:53 - 0:55repeat the process,
-
0:55 - 0:58and continue until you reach
the end of the line. -
0:58 - 1:01At some point, you'll come across
the book that should be last, -
1:01 - 1:05and keep swapping it with every
subsequent book, -
1:05 - 1:09moving it down the line until it
reaches the end where it belongs. -
1:09 - 1:12Then, start from the beginning
and repeat the process -
1:12 - 1:16to get the second to last book
in its proper place, -
1:16 - 1:19and keep going until all books are sorted.
-
1:19 - 1:22This approach is called Bubble Sort.
-
1:22 - 1:24It's simple but slow.
-
1:24 - 1:29You'd make 1,279 comparisons
in the first round, -
1:29 - 1:34then 1,278, and so on,
-
1:34 - 1:39adding up to 818,560 comparisons.
-
1:39 - 1:44If each took just one second,
the process would take over nine days. -
1:44 - 1:49A second strategy would be to start
by sorting just the first two books. -
1:49 - 1:54Then, take the third book and compare it
with the book in the second spot. -
1:54 - 1:57If it belongs before the second book,
swap them, -
1:57 - 2:00then compare it
with the book in the first spot, -
2:00 - 2:02and swap again if needed.
-
2:02 - 2:04Now you've sorted the first three books.
-
2:04 - 2:08Keep adding one book at a time
to the sorted sub-line, -
2:08 - 2:12comparing and swapping the new book
with the one before it -
2:12 - 2:16until it's correctly placed
among the books sorted so far. -
2:16 - 2:18This is called Insertion Sort.
-
2:18 - 2:23Unlike Bubble Sort, it usually doesn't
require comparing every pair of books. -
2:23 - 2:27On average, we'd expect to only need
to compare each book -
2:27 - 2:29to half of the books that came before it.
-
2:29 - 2:32In that case, the total
number of comparisons -
2:32 - 2:36would be 409,280,
-
2:36 - 2:38taking almost five days.
-
2:38 - 2:41You're still doing
way too many comparisons. -
2:41 - 2:43Here's a better idea.
-
2:43 - 2:45First, pick a random book.
-
2:45 - 2:50Call it the partition and compare it
to every other book. -
2:50 - 2:52Then, divide the line
-
2:52 - 2:56by placing all the books
that come before the partition on its left -
2:56 - 2:59and all the ones that come after it
on its right. -
2:59 - 3:00You've just saved loads of time
-
3:00 - 3:04by not having to compare
any of the books on the left -
3:04 - 3:07to any of the ones
on the right ever again. -
3:07 - 3:10Now, looking only
at the books on the left, -
3:10 - 3:13you can again pick a random partition book
-
3:13 - 3:17and separate those books that come
before it from those that come after it. -
3:17 - 3:20You can keep creating
sub-partitions like this -
3:20 - 3:22until you have a bunch of small sub-lines,
-
3:22 - 3:28each of which you'd sort quickly using
another strategy, like Insertion Sort. -
3:28 - 3:33Each round of partitioning requires
about 1,280 comparisons. -
3:33 - 3:35If your partitions are pretty balanced,
-
3:35 - 3:41dividing the books into 128 sub-lines of ten
would take about seven rounds, -
3:41 - 3:44or 8,960 seconds.
-
3:44 - 3:49Sorting these sub-lines would add
about 22 seconds each. -
3:49 - 3:52All in all, this method
known as QuickSort -
3:52 - 3:55could sort the books
in under three and a half hours. -
3:55 - 3:56But there's a catch.
-
3:56 - 4:00Your partitions could end up lopsided,
saving no time at all. -
4:00 - 4:01Luckily, this rarely happens.
-
4:01 - 4:05That's why QuickSort is one of the most
efficient strategies -
4:05 - 4:07used by programmers today.
-
4:07 - 4:11They use it for things like sorting items
in an online store by price, -
4:11 - 4:15or creating a list of all the gas stations
close to a given location -
4:15 - 4:16sorted by distance.
-
4:16 - 4:20In your case, you're done quick sorting
with time to spare. -
4:20 - 4:23Just another high-stakes day
in the library.
- Title:
- What's the fastest way to alphabetize your bookshelf? - Chand John
- Speaker:
- Chand John
- Description:
-
View full lesson: http://ed.ted.com/lessons/what-s-the-fastest-way-to-alphabetize-your-bookshelf-chand-john
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.
- Video Language:
- English
- Team:
- closed TED
- Project:
- TED-Ed
- Duration:
- 04:39
Jessica Ruby approved English subtitles for What's the fastest way to alphabetize your bookshelf? | ||
Jessica Ruby accepted English subtitles for What's the fastest way to alphabetize your bookshelf? | ||
Jessica Ruby edited English subtitles for What's the fastest way to alphabetize your bookshelf? | ||
Jennifer Cody edited English subtitles for What's the fastest way to alphabetize your bookshelf? |