1,280冊の本の並び替え：どの戦略を使うべきか？

要約

この記事では、1,280冊の本が一直線に並べられているが、すべてが順序通りでなく、翌日の授業開始前に並べ替える必要がある場合に、3つの異なる並べ替え戦略を探求します。バブルソート、挿入ソート、クイックソートの方法を比較し、効率と潜在的な欠点について議論します。

バブルソート

本を並べ替える方法の1つは、バブルソート法を使用することです。これは、一方の端から始めて最初の2冊の本を取り出し、順序通りでなければ交換します。次に、次の2冊に進み、同じプロセスを繰り返し、行の終わりに達するまで続けます。ある時点で、最後になるべき本が現れ、それ以降のすべての本と交換して行の終わりに到達するまで交換します。このプロセスをすべての本が並べ替えられるまで繰り返します。この方法は単純ですが、遅く、818,560回の比較が必要で、9日以上かかります。

挿入ソート

別の戦略は、挿入ソート法です。これは、最初の2冊の本を並べ替え、次に3冊目の本を2冊目の本と比較し、必要に応じて交換します。次に、3冊目の本を1冊目の本と比較し、必要に応じて交換します。ソートされたサブリストに1冊ずつ本を追加し、正しく配置されるまで比較と交換を続けます。通常、この方法ではすべての本のペアを比較する必要はなく、約409,280回の比較が必要で、5日近くかかります。

クイックソート

最も効率的な方法は、クイックソート法です。これは、ランダムに1冊の本をパーティションとして選択し、すべての他の本と比較します。次に、パーティションの左側に来るすべての本を左側に配置し、右側に来るすべての本を右側に配置して、行を分割します。このプロセスを各サブパーティションで繰り返し、小さなサブラインが作成されます。これらのサブラインは、挿入ソートなどの他の戦略を使用して迅速に並べ替えることができます。各パーティションのラウンドには、約1,280回の比較が必要です。パーティションがバランスされている場合、本を10個ずつの128サブラインに分割するのに約7ラウンドまたは8,960秒かかります。これらのサブラインを並べ替えると、それぞれ約22秒かかります。全体として、この方法は本を3時間半以下で並べ替えることができます。ただし、片側に偏ったパーティションのリスクがあるため、時間を節約できない場合があります。

結論

1,280冊の本を並べ替えることは大変な作業ですが、迅速に作業を完了するための効率的な戦略があります。バブルソートや挿入ソートも選択肢ですが、最も効率的な方法はクイックソートです。行をサブパーティションに分割し、迅速に並べ替えることで、この方法は本を3時間半以下で並べ替えることができます。プログラマーは、オンラインストアのアイテムの並べ替えや、距離で並べ替えられたリストの作成にクイックソートを使用することがよくあります。本が並べ替えられたら、図書館は授業の最初の日の準備ができます。