バブルソート、挿入ソート、クイックソート：授業のために1,280冊の本を時間内に並べ替える

概要

この記事では、大学図書館に順序がバラバラな1,280冊の本が到着した場合、並べ替えるための3つのソート戦略、バブルソート、挿入ソート、クイックソートについて探求します。

バブルソート

本を並べ替える方法の1つは、ラインの一端から最初の2冊の本で始めることです。最初の2冊が順番通りならそのままにしておきます。そうでなければ、交換します。その後、2番目と3番目の本を見て、同じプロセスを繰り返し、ラインの終わりに到達するまで続けます。ある時点で、最後になるべき本に出会い、その後のすべての本と交換しながら、ラインを下に移動させ、最後の場所に到達させます。その後、最初からやり直し、2番目に最後の本を正しい場所に並べ替え、すべての本が並べ替えられるまで続けます。この方法はバブルソートと呼ばれます。シンプルですが遅いです。最初のラウンドで1,279回、次に1,278回、そして818,560回の比較を行います。1秒かかる場合、このプロセスには9日以上かかります。

挿入ソート

2番目の戦略は、最初に最初の2冊の本を並べ替え、次に3番目の本を取り、2番目の本と比較することです。2番目の本の前に置く必要がある場合は、交換します。次に、最初の場所にある本と比較し、必要に応じて再び交換します。これで、最初の3冊の本が並べ替えられました。ソートされたサブリストに1冊ずつ本を追加し、新しい本を前の本と比較して正しく並べ替えられた本の中に置くまで、前の本の半分の冊数だけ本を比較することを繰り返します。これを挿入ソートと呼びます。バブルソートとは異なり、すべての本のペアを比較する必要はありません。平均して、それまでに来た本の半分の本とのみ比較する必要があると予想されます。その場合、比較の合計数は409,280で、ほぼ5日かかります。

クイックソート

より良いアイデアは、最初にランダムに本を選び、それをパーティションと呼び、他のすべての本と比較することです。その後、パーティションより前に来るすべての本を左側に配置し、それ以降の本を右側に配置して、ラインを分割します。左側の本だけを見て、再びランダムなパーティション本を選択し、その前に来る本と後に来る本を分けます。このようにして、小さなサブラインの束を作成し、それぞれを挿入ソートのような別の戦略を使って素早く並べ替えます。各パーティションで約1,280回の比較が必要です。パーティションがかなりバランスされている場合、本を10冊ずつの128サブラインに分割するのに約7ラウンドまたは8,960秒かかります。これらのサブラインを並べ替えるのには、約22秒かかります。全体として、このクイックソートとして知られる方法は、本を3時間半以内に並べ替えることができます。ただし、注意が必要です。パーティションが偏っていると、全く時間を節約できません。幸い、これはめったに起こりません。そのため、クイックソートは、今日のプログラマーが使用する最も効率的な戦略の1つです。彼らは、価格によってオンラインストアのアイテムを並べ替えたり、特定の場所に近いすべてのガソリンスタンドのリストを距離順に並べ替えたりするために使用します。

結論

まとめると、授業のために大学図書館に順序がバラバラな1,280冊の本を並べ替えることは、困難な課題かもしれません。しかし、バブルソート、挿入ソート、またはクイックソートなどの効率的なソート戦略を使用することで、学生のために本を並べ替えることができます。バブルソートや挿入ソートは遅い場合がありますが、クイックソートはアイテムの数が多い場合に特に速く、効率的な戦略です。