現在のスピード: 300 ms
選択ソート
挿入ソート
クイックソート
先日、本の並び替えゲームを作ったときに、結局これどういう手順で並び替えるのが一番効率いいんだろうと気になったので、代表的なソートアルゴリズムを比較するシミュレータをChatGPTに作ってもらいました。
いくつか代表的なソートアルゴリズムのなかから、自分が理解できて本の並び替えに使いそうかなと思った3つのアルゴリズムを選んでいます、それぞれのアルゴリズムの詳細は、参考をみていただければと思いますが、簡単に言うと、
- 選択ソート：一番小さいのを選んで左に置いていく、を繰り返す。
- 挿入ソート：左から1冊ずつ、そこより左の最適な場所に淹れていく。
- クイックソート：基準を決めてそれより小さい、大きいに分けるを繰り返す。
と言うことのようです。通常、システムがソートは対象の二つの位置を入れ替えながら進めていくようですが、本の場合、入れ替えというよりも挿入していく感じかなと思い、そのようにしてもらってます。
ブックポストに入っていた20冊の返却本を、それぞれのアルゴリズムでブックトラックに並べるという想定のシミュレーションなのですが、試していただけると結果は明らかで、名前のとおり、クイックソートが一番早いようです。直感的には手数多そうな気がしますが不思議ですね。
実は調べる前、自分が普段どうやっていたかイメージわかず、強いて言えば挿入ソートのようなことをやっていたかなと思ったのですが、言われてみれば、まず大まかに類ごとに分けて並び替えていたような気もするので、そういう意味ではクイックソートに近いのかなと思いました。
余談ですが、バブルソート（隣り合う本を比較して小さい方を左にするを繰り返す）は、さすがに使わないだろうと思って、シミュレーションには入れなかったのですが、よく考えると書架整理はこれですね。実際、元からある程度ソートされているデータに使うと有効なアルゴリズムらしいです。
実際の人間が本を並び替えるのとシステムがデータを並び替えるのでは、いろいろ違うところもある（物理的な移動が大変だったり、比較をもっとヒューリスティックにできたり）ので、あくまで参考程度ですが、おもしろいですね。なんとなく昔のPCのデフラグを見ているようです。
お相手は、やわらか図書館学でした。
参考
