Q&A
比較する二つの数のうち、数列の前にあるほうが b になり、後にあるほうが a になるのはなぜかということでしょうか？
そうだとしたら、どちらでもいいことなので、そのように設計されたと言っていいと思います。
前提・実現したいこと
Listインターフェースのsortメソッドを使って数字の配列を逆転させる実装を作ろうとしたところ
実装自体はできたのですが、sortメソッドの挙動が読めずにいます。
該当のソースコード
Java
1public class Main { 2 public static void main(String[] args) { 3 List<Integer> list = Arrays.asList(new Integer[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}); 4 list.sort( 5 new Comparator<Integer>() { 6 public int compare(Integer a, Integer b) { 7 System.out.println(a + "," + b); 8 return -a.compareTo(b); 9 } 10 }); 11 } 12}
※ 見やすくするために匿名クラスで書いています！
### 出力結果
System.out.println(a + "," + b);にて出力される値を確認すると、下記のように表示されます
2,1 3,2 4,3 5,4 6,5 7,6 8,7 9,8 10,9
2,1という数値を IntegerクラスのcompareToメソッドで比較すると 2 > 1 となるので、 -1が返されますが
sortメソッドには、-a.compareTo(b); と負の符号で返しているので、1 が返されて
第二引数の順番を前にする（逆転する）ので
{10,9,8,7,6,5,4,3,2,1}と並べ替えられる流れです。
疑問点
Listインターフェースのsortメソッドにおける並び替えロジックは引数でComparatorインターフェースを実現して行いますが
該当コードでは、{1,2,3,4,5,6,7,8,9,10} という配列を並び替え対象として渡しており、
compareメソッドでは下記のような順番で引数に値が渡されるものだと思いましたが、実際は逆転して渡されているようです。
1,2 3,4 5,6...
Javaドキュメントにはそのような記述は特になく、sortメソッドの実装を見てもピンとこなかったため、この挙動はsortメソッドの仕様という理解で合っているのかを伺いたいです！
以下追記です
比較する二つの数のうち、数列の前にあるほうが b になり、後にあるほうが a になってしまうのはなぜか？という質問になります！
補足
Javaのバージョンは openjdk 11.0.6 を使用しております！
それぞれのメソッドの公式ドキュメントは下記のに貼っておきます！
sortメソッド(Listインターフェース)
compareメソッド（Comparatorインターフェース）
compareToメソッド（Integerクラス）
よろしくお願い致します！
Zuishinさん
ご確認ありがとうございます！
> 数列の前にあるほうが b になり、後にあるほうが a になるのはなぜかということでしょうか？
仰る通りです！ 配列を前から順番に引数に渡すのが自然なのかなと思ったのですが、意図的な仕様なのかが分からず伺った次第です！
回答3件
0
ベストアンサー
高速な安定ソートアルゴリズム "TimSort" の解説 | Preferred Networks Research & Development
まず最初に、入力列を小さなソート済み列へと分解します。入力列を前から順番になめ、単調増加（<=）している最大の接頭辞を求めます。
これをやった時点で「全部単調増加です!」となって終了している気がします。
java
1 } else { // Ascending 2 while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) >= 0) 3 runHi++; 4 }
単調増加しているかを調べるif文ならば、その形が 式 < 0 であるよりも 式 >=0 である方が直感的であろうという仮定がここにあるように感じます。
つまり、例えば0番目の要素と1番目の要素を比べて単調増加しているかを調べる時
java
1(A) 2if (c.comapre(a[0], a[1]) < 0) 単調増加です!
と
java
1(B) 2if (c.comapre(a[1], a[0]) >= 0) 単調増加です!
の違いです。
素直に読むと
(A)は「0番目の要素が1番目より小さいなら」単調増加です という書き方です。
(B)は「1番目の要素が0番目と同じか大きいなら」単調増加です という書き方です。
(B)の方が自然でしょう? という、書いた人の意図を感じます。
投稿2021/02/10 04:48
編集2021/02/10 04:57
総合スコア11231
quickquipさん
Timsortのコード、ドキュメントの共有までして頂きありがとうございます！
単調増加か否かであれば、2つの比較で1番目の数字の方が大きいか、同値かで比較して、大きければ増えていっているよね、という方が直感的ですね！
ちなみになんですが
Timsort内の`countRunAndMakeAscending関数`が今回の実装で動くのは、引数の型、数で判断されているのでしょうか？？
どういう意味か分かりかねます。巡り巡ってcountRunAndMakeAscendingはいずれにせよ呼ばれると思います。
https://github.com/openjdk/jdk/blob/4619f372ae5934091b0d40621a1dbcd9e4b0f80c/src/java.base/share/classes/java/util/TimSort.java#L220
https://github.com/openjdk/jdk/blob/4619f372ae5934091b0d40621a1dbcd9e4b0f80c/src/java.base/share/classes/java/util/TimSort.java#L234
> という方が直感的ですね！
意図を感じる=そういう仮定を持った人が書いたんだなと想像できる、という話であって、私自身は正直好きな方でいいと思ってます。
分かりにくくてすみません汗
Timesortコード追ってみます！
ご丁寧にありがとうございました！
分かりにくいという話ではなくて、パッと見で"いずれにせよ呼ばれる"と思えたので答えようのない質問だと感じたということです。（こちらこそ"どういう意味か分かりかねます"はわかりにくかったです。すみません）
0
配列を前から順番に引数に渡すのが自然なのかなと思ったのですが、意図的な仕様なのかが分からず伺った次第です！
ん？
配列(List)を前から順番に渡してますよね？
１は、比較対象がないので、そのまま。（compare を呼ばない）※最大値は１
２は、最大値（１）と比べて、一番後ろ（最大値が更新される）
３は、最大値（２）と比べて・・・・以下同様
2,1 3,2 4,3 5,4 6,5 7,6 8,7 9,8 10,9
という結果になってます。（第一引数がListに追加したい値＝Listの先頭から順、第二引数がListの中で比較したい値）
まぁ、この順序が逆転しても別段ロジック側が決めたことなので、疑問に思って仕方ないところですけど。
あと、これは書き間違いだと思いますが念のため
Listインターフェースのsortメソッドにおける並び替えロジックは引数でComparatorインターフェースを実現して行いますが
Comparetorはロジックの一部ではありますが、Comparetor自体は、２つのオブジェクトの大小関係を決めるだけで、ソートのロジック（アルゴリズム）とは違います。
投稿2021/02/10 05:34
総合スコア4826
momon-gaさん
ご教示ありがとうございます！
> ２は、最大値（１）と比べて、一番後ろ（最大値が更新される)
の繰り返しということで「最初に出てきた値よりも2番目の値の方が大きいか」を都度都度比較しているため、逆転する決まりがあるように勘違いしてしまったようです。。
> Comparetorはロジックの一部ではありますが、Comparetor自体は、２つのオブジェクトの大小関係を決めるだけで、ソートのロジック（アルゴリズム）とは違います。
こちらも、ご指摘ありがとうございます！ロジックの一部という認識もれていました汗
0
順番に一回ずつ比較すればソートできること自体が稀で、
逆転しているように見えるのはたまたまソート済みのリストを渡しているからです。
リストをシャッフルして渡してみれば、逆順というわけではないのが分かる筈です。
アルゴリズムに沿って比較・入れ替えされます。
今回一回比較するだけで済んでいるのは、
- JavaはTimSortを利用している
- TimSortは最初に挿入ソートを利用して荒くソートする
- 挿入ソートは、整列済みの数列に対してO(n)である
で説明できそうな気がします。あんまり詳しくないので自信は無いですが。
投稿2021/02/10 04:06
編集2021/02/10 06:58
総合スコア35668
あなたの回答
tips
プレビュー
