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. 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, 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.
あなたは大学図書館に勤務しています 静かなある日の午後 突然1,280冊の書籍が入荷してきました 書籍は長い1列に並んでいますが 順番はバラバラです あいにく 書籍整理自動システムは ダウンしています さらに厄介なことに 明日から授業が開講します つまり 明日朝一番に 学生たちがこれらの本を求めて どっとやってくるのです それまでに本を アルファベット順に並べるには どうしたらよいでしょう? まず 列の片端の2冊から 始める方法があります その2冊が正しく並んでいたら これは そのままにします そうでなければ この2つを入れ替えます 次に 2冊目と3冊目を比べ 同じようにします 列の最後までそれを続けます そのうち一番最後に置くべき本を 手に取ることになるでしょう この本を 後に続く本と 交換していき この本が収まるべき 列の最後に来るまで作業を続けます 次に 最後から2番目の本も 正しい位置に並ぶように 最初から同じ手順を繰り返します 全部の本が順番に並ぶまでこれを続けます このやり方はバブル・ソートと言います シンプルですが 時間がかかります 第1段階で 1,279回比べなければならず 第2段階で1,278回と続き 合計で818,560回 比べることになります 1回1秒としても 9日以上かかる計算になります 2つ目のやり方は まず最初の2冊を正しく並べます そして 3冊目を2冊目の本と比べます 3冊目が2冊目の本より 順番が先だったら 交換し さらに 1番目の本と比べ 必要なら 交換します これで最初の3冊の順番が整いました 4冊目以降も 1冊ずつ この手順で加え続けます 新しく加える本を 1つ前の本と 比べて 必要なら交換し それまで順番に並べた本の中では 正しい位置にくるように置きます このやり方は挿入ソートと言います バブル・ソートと違って 1冊1冊を 必ずしも他の全てと比べる必要がありません 本1冊につき 比べる相手は 平均で 既に整理された本の半数だけです その場合 比較の回数は 合計で409,280回です 大体5日間かかります これでも 比較の回数が多過ぎます 実は もっといいやり方があります まず 本を1冊 適当に選びます その本を「パーティション」と呼び 他の全ての本と比較します 列を2つに分けて パーティションの前に来る本を全て左に置き 後に来る本を右に置きます これで時間を大幅に節約できます 左に置いた本は右に置いた本と もう比べなくて済むからです では 左に置いた本だけを見て もう1冊適当に「パーティション」を選び パーティションの前に来る本と 後に来る本に分けます このようなミニ・パーティションを 作り続けると 短い列がたくさんできます 短い列を挿入ソートなどのやり方で 手早く整理します 1つのパーティションで 約1,280回の比較をすることになります パーティションの位置が適切なら およそ7つの段階で本を 10冊ずつの128列に分けられます 時間にして8,960秒です 短い列の整理にはさらに22秒ずつかかります クイック・ソートと呼ばれるこのやり方だと 3時間半以内にアルファベット順に 本を並べ直せます 注意点が1つ パーティションの位置が偏っていると 時間は全く節約できません 幸いそんなことは滅多にありません こうして クイック・ソートは 一番効率的なやり方の1つとして 現在プログラマーに使用されています オンラインストアの商品を価格順に並べたり ある地点の付近にある ガソリン・スタンドを近い順に並べたリストを 作ったりします 本の例に戻ると クイック・ソートなら 余裕で整理できます 危ういところでしたが 図書館ではこんな日も珍しくありません