ソーティングはComparatorを定義してやるくらいがちょうどいい

ソーティング(並び替え)のためにプログラムを書く人はあまりいません。プログラミングを習うとすぐに、ソーティングの例題に出会いますが、それはあくまでアルゴリズムの勉強のためのものであって、実際の問題でソートが必要なときは、言語に組み込まれた、あるいは定評のあるライブラリを使ってソートします。

数値や文字列はそのようなライブラリですぐにソートできますが、複数の属性を持つオブジェクトなどを並び替えるためには、オブジェクト同士を比較するための関数やオブジェクト(以下ではComparatorと総称)を用意してからでないとソートできません。C++のSTLにあるsort()にはパラメータを2つ持つ関数を、JavaのCollections.sort()にはインターフェースComparatorを実装するクラスを与えなければなりません(あるいは、オブジェクトにComparableインターフェースを実装させる)。(C++本ウェブアプリ本を参照)

スクリプト系の言語だと、Comparatorを用意しなくても、なんとなく並び替えてくれるので便利です。たとえば、数値と文字列の組からなる以下のような配列を、Pythonなら簡単にソートできます。

>>> data=[(1,"a"), (2, "d"), (1,"c"), (1,"b")]
>>> data.sort()
>>> data
[(1, 'a'), (1, 'b'), (1, 'c'), (2, 'd')]

C++やJavaでは、数値と文字列の組の配列をこんなに簡単にソートすることはできないので、「やっぱスクリプト言語だよね」ということになるのは仕方ありません。

4873113644しかし、この結果をよく見ると、数値だけでなく文字列も考慮して並び替えられています。多くの場合、これはやりすぎです。たとえば、Toby Segaran『集合知プログラミング』(オライリー・ジャパン, 2008)では、映画の評価データ10万件を使った推薦システム(協調フィルタリング)の出力として、次のような例が紹介されています。

5.0 What’s Eating Gilbert Grape (1993)
5.0 Temptress Moon (Feng Yue) (1996)
5.0 Street Fighter (1994)
5.0 Spice World (1997)
5.0 Sliding Doors (1998)
5.0 Shooting Fish (1997)
5.0 Roseanna’s Grave (For Roseanna) (1997)
5.0 Rendezvous in Paris (Rendez-vous de Paris, Les) (1995)
5.0 Reluctant Debutante, The (1958)
5.0 Police Story 4: Project S (Chao ji ji hua) (1993)
5.0 Palmetto (1998)
5.0 New York Cop (1996)
5.0 Love Is All There Is (1996)
5.0 Johns (1996)
5.0 Innocents, The (1961)
5.0 Hollow Reed (1996)

これは、(スコア, タイトル)の組の配列を、ソーティングして反転したものです。反転することによって、スコアの高い物から出力されるようになっているわけですが、並び替えにはタイトルも使われているため、得られる結果はいつも、アルファベット順で後ろにあるものが優先されてしまっています。独自のComparatorを使うとかスコアに乱数を付加するなど、何らかの対策をしてからでないと、このコードを使うことはできないでしょう。

ソーティングはComparatorを定義してやるくらいがちょうどいい、というわけです。