What's the fastest way to alphabetize your bookshelf? - Chand John

Đâu là cách nhanh nhất để sắp xếp tủ sách theo thứ tự bảng chữ cái? - Chand John

Translator: Linh Tran Reviewer: Thao Nguyen

You work at the college library.

Bạn làm việc tại thư viện trường đại học.

You're in the middle of a quiet afternoon

Trong một buổi chiều bình lặng,

when suddenly a shipment of 1,280 different books arrives.

bỗng có một đơn hàng với 1 280 cuốn sách khác nhau được chuyển đến.

Các cuốn sách được xếp thành một hàng dài

The books have been dropped of in one long straight line,

but they're all out of order,

nhưng chẳng theo thứ tự nào hết

and the automatic sorting system is broken.

và hệ thống sắp xếp tự động thì lại hỏng mất rồi.

Còn tệ hơn nữa là các lớp sẽ bắt đầu học vào ngày mai

To make matters worse, classes start tomorrow,

which means that first thing in the morning,

nghĩa là ngay từ sáng sớm,

students will show up in droves looking for these books.

sinh viên sẽ ào đến tìm sách.

How can you get them all sorted in time?

Làm cách nào để bạn sắp xếp chúng cho kịp thời gian đây?

One way would be to start at one end of the line with the first pair of books.

Cách đầu tiên là bạn bắt đầu một vài cuốn ở một đầu của dãy sách.

If the first two books are in order, then leave them as they are.

Nếu hai cuốn đầu tiên theo thứ tự, hãy để nguyên chúng ở đó.

Otherwise, swap them.

Nếu không thì hãy xếp lại.

Then, look at the second and third books,

Tiếp theo, tìm cuốn sách thứ hai và thứ ba

repeat the process,

lặp lại quá trình trên

and continue until you reach the end of the line.

và tiếp tục cho đến cuối hàng.

At some point, you'll come across the book that should be last,

Ở một thời điểm nào đó, bạn sẽ bắt gặp cuốn sách ở thứ tự cuối

and keep swapping it with every subsequent book,

hãy tráo nó với mọi cuốn sách tiếp sau

moving it down the line until it reaches the end where it belongs.

tiếp tục như vậy cho tới khi nó về đúng chỗ ở cuối hàng.

Then, start from the beginning and repeat the process

Tiếp theo, bắt đầu từ đầu và lặp lại

to get the second to last book in its proper place,

để đưa cuốn sách thứ hai từ dưới lên về đúng chỗ

and keep going until all books are sorted.

và cứ thế cho tới khi tất cả chỗ sách được sắp xếp hết.

This approach is called Bubble Sort.

Phương pháp này gọi là Sắp xếp Nổi bọt

It's simple but slow.

Tuy đơn giản nhưng lại chậm chạp.

Bạn phải so sánh 1 279 lần trong lượt sắp xếp đầu tiên

You'd make 1,279 comparisons in the first round,

then 1,278, and so on,

rồi đến 1 278 lần và tiếp tục như thế

adding up to 818,560 comparisons.

tổng cộng lại sẽ là 818 560 lượt so sánh.

If each took just one second, the process would take over nine days.

Nếu mỗi lượt kéo dài 1 giây, cả quá trình sẽ cần tới hơn 9 ngày để hoàn thành.

A second strategy would be to start by sorting just the first two books.

Phương án thứ hai là bắt đầu sắp xếp với hai cuốn sách đầu tiên thôi.

Then, take the third book and compare it with the book in the second spot.

Rồi lấy cuốn thứ ba và so với cuốn ở vị trí thứ hai.

If it belongs before the second book, swap them,

Nếu nó đứng trước cuốn ở vị trí thứ hai, hãy tráo chúng

then compare it with the book in the first spot,

rồi so với cuốn ở vị trí đầu

and swap again if needed.

và tráo lần nữa nếu cần thiết.

Now you've sorted the first three books.

Giờ bạn đã tráo xong ba cuốn sách đầu tiên.

Keep adding one book at a time to the sorted sub-line,

Cứ tiếp tục thêm từng cuốn sách một vào dãy sách đã sắp xếp

comparing and swapping the new book with the one before it

so sánh và tráo cuốn mới với cuốn trước nó

until it's correctly placed among the books sorted so far.

cho tới khi chúng được đặt đúng vị trí trong đống sách đã sắp xếp.

Cách này được gọi là Sắp xếp Chèn.

This is called Insertion Sort.

Unlike Bubble Sort, it usually doesn't require comparing every pair of books.

Khác với Sắp xếp Nổi bọt, cách này không bắt buộc bạn phải so sánh từng cặp.

On average, we'd expect to only need to compare each book

Trung bình, chúng ta chỉ cần phải so sánh mỗi cuốn sách

to half of the books that came before it.

với một nửa số sách trước nó.

In that case, the total number of comparisons

Trong trường hợp đó, số lượt so sánh

would be 409,280,

sẽ là 409 280

taking almost five days.

mất tới gần 5 ngày.

Bạn vẫn phải so sánh quá nhiều lần.

You're still doing way too many comparisons.

Here's a better idea.

Ở đây có một cách hay hơn nè.

First, pick a random book.

Đầu tiên, hãy chọn ngẫu nhiên một cuốn sách

Call it the partition and compare it to every other book.

Hãy coi nó là Vách Ngăn và so sánh nó với tất cả các cuốn sách khác.

Then, divide the line

Sau đó, chia dãy sách ra

by placing all the books that come before the partition on its left

bằng cách đặt tất cả những cuốn có thứ tự trước Vách Ngăn ở bên tay trái

and all the ones that come after it on its right.

và những cuốn sau Vách Ngăn ở bên tay phải

You've just saved loads of time

Bạn vừa tiết kiệm được thời gian

by not having to compare any of the books on the left

vì không phải so sánh bất kì cuốn sách nào ở bên trái

to any of the ones on the right ever again.

với các cuốn sách ở bên phải.

Giờ, hãy chỉ tập trung vào số sách bên tay trái

Now, looking only at the books on the left,

you can again pick a random partition book

bạn lại có thể lựa chọn một Vách Ngăn bất kì

and separate those books that come before it from those that come after it.

và chia số sách đó thành những cuốn đứng trước và đứng sau

You can keep creating sub-partitions like this

Bạn có thể tiếp tục tạo ra các Vách Ngăn phụ như vậy

until you have a bunch of small sub-lines,

cho tới khi có rất nhiều dãy sách phụ

each of which you'd sort quickly using another strategy, like Insertion Sort.

với mỗi dãy, bạn có thể sắp xếp nhanh chóng bằng phương pháp Sắp xếp Chèn

Each round of partitioning requires about 1,280 comparisons.

Mỗi lần chia ngăn cần khoảng 1 280 lượt so sánh

If your partitions are pretty balanced,

Nếu các Vách Ngăn của bạn khá đồng đều

dividing the books into 128 sub-lines of ten would take about seven rounds,

chia số sách thành 128 dãy phụ gồm 10 cuốn sẽ mất khoảng 7 lượt

or 8,960 seconds.

hay 8 960 giây.

Sorting these sub-lines would add about 22 seconds each.

Phân loại hết các dãy phụ này sẽ tốn thêm khoảng 22 giây mỗi lần.

All in all, this method known as QuickSort

Nói chung, phương pháp có tên Sắp xếp Nhanh này

could sort the books in under three and a half hours.

có thể giúp bạn phân loại sách trong vòng chưa đầy 3 tiếng rưỡi

But there's a catch.

Tuy nhiên, vẫn có bẫy.

Your partitions could end up lopsided, saving no time at all.

Các Vách Ngăn của bạn có thể bị lệch và sẽ chẳng tiết kiệm được thời gian

Luckily, this rarely happens.

May mắn là điều này rất hiếm khi xảy ra

That's why QuickSort is one of the most efficient strategies

Vì vậy nên Sắp xếp Nhanh là một trong những phương án hữu hiệu nhất

used by programmers today.

được các nhà lập trình sử dụng ngày nay.

They use it for things like sorting items in an online store by price,

Họ dùng nó để sắp xếp hàng theo giá cả trên cửa hàng trực tuyến

or creating a list of all the gas stations close to a given location

hoặc tạo ra danh sách các cây xăng gần với một địa điểm nhất định

sorted by distance.

theo khoảng cách.

In your case, you're done quick sorting with time to spare.

Trong trường hợp của bạn, bạn có thể sắp xếp nhanh mà vẫn còn thừa thời gian

Just another high-stakes day in the library.

Và đó lại là một ngày bận rộn khác trong thư viện