ネタもと:リストボックスが正しくソートされない

ネタは、大吉末吉さんの仮説[2007/08/21(火) 21:13:08]ListBoxのソートをする時の文字の順番は一方方向ではなく、じゃんけんの様にループする場合がある。

ループするという表現は、なかなかおもしろいですね。本当は、「評価されないので、評価される順序によって順番が決まる」ってことです。

K.J.K.さんの解説[2007/08/21(火) 19:40:47]から、評価されない文字がある、ということがわかります。では、「評価されない」とは、どのようなことでしょうか。ここで、IComparable インターフェイスを調べてみます。

IComparable.CompareTo Method より：

Value	Meaning
Less than zero	This instance is less than obj.
Zero	This instance is equal to obj.
Greater than zero	This instance is greater than obj.

比較するためには、他の値と比べる必要があります。比べた結果、他方の値よりも前なのか、同じなのか、後ろなのかを、評価の結果とします。評価の結果は、ここにある通り3つです。より小さいか、同じか、より大きいか。ここでは .NET Framework を例に取りましたが、どのような言語であっても、独自に比較関数を追加できるものであれば、この3つ値のどれかを返すように定義するようになっていると思います。

いま、"a", "b", "c" の3つの文字を比較するとします。これを、"b", "a", "c" の順に追加していくとしましょう。
まず、"b" を追加します。このとき、比較の対象はありません。従って、先頭に追加されます。
次に、"a" を追加します。"b" に対して CompareTo("a") を実行すると、「Greater than zero」が返ってきます。このため、"a" は "b" より小さいと判断され、"b" の前に "a" が追加されます。
次に、"c" を追加します。"a" に対して CompareTo("c") を実行すると、「Less than zero」が返ってきます。このため、"c" は "a" よりも大きいと判断されます。そして "a" の次にある "b" と比較されます。これも「Less than zero」が返ってくるので、"b" の後ろに "c" が追加されることになります。

さて、問題の "［", "a", "「" です。この場合、"［" と "「" が、「評価されない文字」となっています。先ほどの評価の結果には「評価しない」がないため、「評価しない」ための方法が、いくつか考えられます。

まず、「評価できる文字よりも、小さいと判断する。評価できない文字同士では、同じと判断する」。
そして、「評価できる文字よりも、大きいと判断する。評価できない文字同士では、同じと判断する」。
最後に、「どの文字に対しても同じと判断する」。

実装するには、最後の「どの文字に対しても同じと判断する」のが、とても楽です。そして、Windows の実装は、そのようになっているようです。

では、「同じ」と判断されるとして、どうなるか追ってみましょう。

まず、"［" です。最初なので、先頭に追加されます。
次に、"a" です。CompareTo("［") の結果は「Zero」です。同じなので、次の項目との比較に回します。しかし、次はないので、後ろに追加します。
そして、"「" です。CompareTo("［") の結果は「Zero」です。同じなので、次の項目との比較に回します。CompareTo("a") の結果は「Zero」です。同じなので次の項目…がないので、後ろに追加します。

どうも、こんな実装になっているようですね。K.J.K.さんの[2007/08/22(水) 11:06:25]にある、3,でたらめ。しかも再現性なし。同じ入力でもやるたびに出力が変わる。に注目です。件の ListBox は、同じ入力であれば同じ順序で表示されるため、「ソートされている」と言えるわけです。

さて、タイトルの「ソートの結果は一定しないことがある」ですが。

「同じ」と判断されるものについては、後先どちらになるか、使用するアルゴリズムによって扱い方が決まります。様々なソート アルゴリズムについて、表示するものが違うけど、比較するものが違うオブジェクトを用意して実験してみればわかるでしょう。また、「安定ソート」について、調べてみるのもいいでしょう。ListBox のように、一つずつ追加していく場合、追加した順になることが多いです。一方、すでにある配列をソートするクイックソートでは、一定しない実装があります。

ということは、です。オリジナルなクラスの、オリジナルなソートを追加するときには、どうやって順序を決めるか、よく考えなければならない、ということです。