aririn0528
@aririn0528

Are you sure you want to delete the question?

Leaving a resolved question undeleted may help others!

Comparatorインタフェースのcompareメソッドについて

現在JavaSilver SE11を勉強中のJava初学者でございます。

某問題集を勉強していた際に、以下のコードにて不明な点があり、
自分なりに検索はしてみたものの解決に至らなかったため、
こちらで質問をさせていただいた次第でございます。

お手数おかけしますが、ご助力のほどよろしくお願いいたします。

解決したいこと

以下に記載するコードのSampleComparatorクラス内のcompareメソッドの引数についてです。
1回目の処理 (正確な書き方ではないかと思います…) では、s1内のid 2とs2内のid 3を比較して1を戻しているところまではわかりました。

しかし、2回目の処理で、s1内のid 3とs2内のid 1を比較するという動作をしており、どうしてs1とs2にそれぞれリストsamplesの1番目の要素と2番目の要素が入るのかがピンと来ていません。

このような動作をするのであれば、0番目の要素と3番目の要素も同じく受け取ってidの値同士を比較も行われるべきではないだろうか?と思いました。

該当のコード

Sample.java
public class Sample {
    private int id;
    private String name;
    public Sample(int id, String name) {
        super();
        this.id = id;
        this.name = name;
    }
    public int getId() {
        return id;
    }
    public String getName() {
        return name;
    }
}
SampleComparator.java
import java.util.Comparator;

public class SampleComparator implements Comparator<Sample> {
    @Override
    public int compare(Sample s1, Sample s2) {
        if (s1.getId() < s2.getId()) {
            return 1;
        }
        if (s2.getId() < s1.getId()) {
            return -1;
        }
        return 0;
    }
}
Main.java
import java.util.Comparator;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        Sample[] samples = {
            new Sample(2, "B"),
            new Sample(3, "C"),
            new Sample(1, "A")
        };
        List<Sample> list = new ArrayList<Sample>(Arrays.asList(samples));
        list.sort(new SampleComparator());
        for (Sample s : list) {
            System.out.println(s.getName());
        }
    }
}
0

2Answer

バラバラのデータを規則正しく並べることをソートといい、コンピュータで扱う代表的な問題であることから、さまざまな実現方法=アルゴリズムが考案されています。

しかし、2回目の処理で、s1内のid 3とs2内のid 1を比較するという動作をしており、どうしてs1とs2にそれぞれリストsamplesの1番目の要素と2番目の要素が入るのかがピンと来ていません。
このような動作をするのであれば、0番目の要素と3番目の要素も同じく受け取ってidの値同士を比較も行われるべきではないだろうか?と思いました。

データを効率よく並べ替えたい場合、データの比較する順番を調整したり、データの比較回数を減らしたりします。「データの比較順や比較回数が直感と違う」とのことですが、これはJavaが採用しているソートアルゴリズムが効率化のため、データの比較順や比較回数を工夫した結果だと思われます。

なお、環境によって異なる可能性はありますが、今回のケースではTimsortが採用されているはずです。関心がある場合は以下のリンクを参考にされるとよいと思います。

0Like

Comments

  1. @aririn0528

    Questioner

    とても詳細に回答していただきありがとうございます。
    おかげさまで理解することができました。

    ソートについていろいろと調べることができました。
    どうやら自分はバブルソートという手法で考えていたのが原因で混乱していたようです。

    ソースまで貼っていただきありがとうございます。

解決してるようですが、調べ方が書いてなかったので、記載しておきます。
以下のようになります。

(1)ソースコードの修正

少し仕込みを入れました。デバッガがあれば別にデバッガで止めても大丈夫です。

import java.util.Comparator;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Main {
    private static List<Sample> list;
    public static void printList() {
        System.out.print("[Main.list]: {");
        for (Sample s : list) {
            System.out.print(String.format("{%d: %s},", s.getId(), s.getName()));
        }
        System.out.println("}");
    }
    public static void main(String[] args) {
        System.out.println(String.format("version: %s", System.getProperty("java.version")));
        Sample[] samples = {
            new Sample(2, "B"),
            new Sample(3, "C"),
            new Sample(1, "A")
        };
        list = new ArrayList<Sample>(Arrays.asList(samples));
        list.sort(new SampleComparator());
        printList();
    }
}
class Sample {
    private int id;
    private String name;
    public Sample(int id, String name) {
        super();
        this.id = id;
        this.name = name;
    }
    public int getId() {
        return id;
    }
    public String getName() {
        return name;
    }
}
class SampleComparator implements Comparator<Sample> {
    @Override
    public int compare(Sample s1, Sample s2) {
        new Exception().printStackTrace();
        Main.printList();
        System.out.println(String.format("Compare: {%d: %s} vs {%d: %s}", s1.getId(), s1.getName(), s2.getId(), s2.getName()));
        if (s1.getId() < s2.getId()) {
            return 1;
        }
        if (s2.getId() < s1.getId()) {
            return -1;
        }
        return 0;
    }
}

実行結果は以下のとおりです。

version: 11.0.7
java.lang.Exception
	at SampleComparator.compare(Main.java:44)
	at SampleComparator.compare(Main.java:41)
	at java.base/java.util.TimSort.countRunAndMakeAscending(TimSort.java:355)
	at java.base/java.util.TimSort.sort(TimSort.java:220)
	at java.base/java.util.Arrays.sort(Arrays.java:1515)
	at java.base/java.util.ArrayList.sort(ArrayList.java:1749)
	at Main.main(Main.java:22)
java.lang.Exception
	at SampleComparator.compare(Main.java:44)
	at SampleComparator.compare(Main.java:41)
	at java.base/java.util.TimSort.countRunAndMakeAscending(TimSort.java:356)
	at java.base/java.util.TimSort.sort(TimSort.java:220)
	at java.base/java.util.Arrays.sort(Arrays.java:1515)
	at java.base/java.util.ArrayList.sort(ArrayList.java:1749)
	at Main.main(Main.java:22)
java.lang.Exception
	at SampleComparator.compare(Main.java:44)
	at SampleComparator.compare(Main.java:41)
	at java.base/java.util.TimSort.binarySort(TimSort.java:296)
	at java.base/java.util.TimSort.sort(TimSort.java:221)
	at java.base/java.util.Arrays.sort(Arrays.java:1515)
	at java.base/java.util.ArrayList.sort(ArrayList.java:1749)
	at Main.main(Main.java:22)
[Main.list]: {{2: B},{3: C},{1: A},}
Compare: {3: C} vs {2: B}
[Main.list]: {{2: B},{3: C},{1: A},}
Compare: {1: A} vs {3: C}
[Main.list]: {{3: C},{2: B},{1: A},}
Compare: {1: A} vs {2: B}
[Main.list]: {{3: C},{2: B},{1: A},}

(2)コードの調査

https://github.com/AdoptOpenJDK/openjdk-jdk11/blob/master/src/java.base/share/classes/java/util/ArrayList.java#L1749
https://github.com/AdoptOpenJDK/openjdk-jdk11/blob/master/src/java.base/share/classes/java/util/Arrays.java#L1515
https://github.com/AdoptOpenJDK/openjdk-jdk11/blob/master/src/java.base/share/classes/java/util/TimSort.java#L220-L221
https://github.com/AdoptOpenJDK/openjdk-jdk11/blob/master/src/java.base/share/classes/java/util/TimSort.java#L355-L356
https://github.com/AdoptOpenJDK/openjdk-jdk11/blob/master/src/java.base/share/classes/java/util/TimSort.java#L296

(3)仕様の確認

https://docs.oracle.com/javase/jp/11/docs/api/java.base/java/util/List.html#sort(java.util.Comparator)
https://svn.python.org/projects/python/trunk/Objects/listsort.txt

0Like

Comments

  1. @aririn0528

    Questioner

    詳細なコードやソースなど書いていただきありがとうございます。
    非常に助かりました。

Your answer might help someone💌