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

譯者: kejia chen 審譯者: 庭芝 梁

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.

這時候，突然送來了1280 本書！

這些書被排成一行，

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,

在第一輪過程就需要進行 1279 次的比較；

then 1,278, and so on,

第二輪要比較 1278 次， 以此類推……

adding up to 818,560 comparisons.

所以總共要比較 818,560 次。

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

如果比較一次需要 1 秒，

那麼你需要花費 9.5 天才能完成工作。

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

這種方法總共需要比較 409,280 次，

would be 409,280,

taking almost five days.

大約需要 5 天時間。

然而，你需要比較的次數還是太多。

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.

每一輪分割大約需要 進行 1280 次比較，

If your partitions are pretty balanced,

如果你的分割點分佈的非常均勻，

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

整排書分為 128 個分支， 每個分支 10 本書，

這樣大約需要七輪分割， 也就是 8960 秒。

or 8,960 seconds.

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

每個分支當中， 大約需要再花 22 秒進行排序。

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.

真是多麼驚險刺激的一天啊！