You're in the middle of a quiet afternoon

這天，正值寧靜午後的時段

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

突然運輸車送來一千二百八十本不同的書籍到館

The books have been dropped off 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.

有可能再遇到圖書館另一個新危機啦！