ソートのお話

（このサイトは2013年２月５日午後より正式公開に移行し、ソースリストも正式公開しています。無料でご利用できます。）

はじめに

　みなさんは、パソコンなどでソートを使っていますか？　データを並び替えるソートです。

　プログラムを作る人や、Excel などでデーター処理をしている人だったら、意図的にソートすることはよくあります。

　では、そうでない人は？　というと、実は気が付かないところでソートは行われています。

　何かの検索をするときに、実際には画面の向こうでソートされた結果を利用して検索していたりとか。ばらばら状態から探すより、ソートされている状態から探したほうが速いですよね。

　zip ファイルの解凍をするときも、みなさんの気が付かないところで、内部ではソートが動いています。しかも、このソートは普段はなかなかお目にかかれない、超高速ソートの「カウンティングソート」という珍しい技法だったりします。

　ただ、カウンティングソートは、特定の条件がそろっている時は使えますが、普段の一般的な場面では使えません。ちょっと残念

　一般的な場面で使える、並び替える速度が一番速い方法が、「クイックソート」と呼ばれる技法で、現在、世界中で広く使われています。

　ただ人間の欲はきりがなくて、一番速い方法を使っているにもかかわらず、「遅いっ！」とか思ったりすることもあります。

　そんなことから、クイックソートよりも速く動作するうえに、クイックソートが苦手にしているデータもあっさりと速くソートする技法を作ることにしたわけです。

　できあがったのが、「♪ドレミファソート」

　シングルスレッドで動作するソートの方法では、たぶん最速じゃないかと勝手に想像しています。もちろん、マルチスレッドにすることもできます。

　実は、乱数データのソートだったら、別の方法で、もう少し速い方法もあります。ですが、そちらの方法では、最悪計算量のケースを防ぎきれない特性がありました。速度を上げつつ、最悪計算量も考慮するという両方を満たす部分で落ち着いたのが、「♪ドレミファソート」です。

　このサイトでは、そんなソートの世界をとりあげてみたいと思います。

　でも、10 件をソートするのに、バブルソートなら４分ちょっとで終わるのに、クイックソートだと６分以上かかる例もあるようです。ソート法ごとに曲とダンスも覚えなきゃいけないし。プログラミングを覚えるのも大変です。学生さんにしては髪の毛の量が…

10 レコードのクイックソートが６分以上かかる例

「くろねこ」（♪ドレミファソート専用メール： doremifasortあっとまーくeri.bbiq.jp ）