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

アルファベット順に本を並べる最速の方法 ― チャンド・ジョン

翻訳: kanna kobayashi 校正: Tomoyuki Suzuki

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.

突然1,280冊の書籍が入荷してきました

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,

第１段階で 1,279回比べなければならず

then 1,278, and so on,

第２段階で1,278回と続き

adding up to 818,560 comparisons.

合計で818,560回 比べることになります

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,

合計で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.

１つのパーティションで 約1,280回の比較をすることになります

If your partitions are pretty balanced,

パーティションの位置が適切なら

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

およそ７つの段階で本を 10冊ずつの128列に分けられます

or 8,960 seconds.

時間にして8,960秒です

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.

危ういところでしたが 図書館ではこんな日も珍しくありません