compareメソッドについて

Question

javaの学習をしている初学者になります。
比較の部分でABCと出力されるのですが、なぜABCと出力されるのかがわかりません。
最初にif(s1.getId()<s2.getId())の部分で2，3を比較した後、3，1を比較し2，3，1という順番になり次に
if(s2.getId()<s1.getId()) が処理され2，3，1が2，1，3になりBACという答えではないのでしょうか。
ご教授いただけると幸いです。

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;
}
}

import java.util.Comparator;

public class SampleComparator implements Comparator<Sample> {

	@Override
	public int compare(Sample s1, Sample s2) {

		if(s1.getId()<s2.getId()) {
			System.out.println(s1.getId()+" "+s2.getId());
			return -1;
		}
		if(s2.getId()<s1.getId()) {
			//System.out.println(s2.getId()+" "+s1.getId());
			return 1;
		}

		return 0;
	}

}
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());
	 }


	}

}

Comments

[jimbe]

コードをご提示の場合はマークダウンをファイル毎に分けて頂けますか。

[jimbe]

> ～BACという答えではないのでしょうか

それでは id によるソートが出来ていないということになります。
結果が ABC とソート出来ているということは、想像されている処理が間違っているということです。

ご提示のコードでは二つ目の if 内の println がコメントになっていますので表示に不足があるでしょうし、コメントになっていなかったとしても 一つ目の if 内の println と同じフォーマットのため区別が付かないでしょう。
さらに両者を区別したとしても、それぞれの判定の結果によって何が行われるかはソートメソッドの実装次第です。
どのようにソートが行われているかをお調べになっているのでしたら、直接ソースコードを探されたほうが良いのではないでしょうか。

[xebme]

list.sort(new SampleComparator());のなかで何が起きているのか？
これは、ソートアルゴリズムによって比較箇所が異なります。
以前、調べたとき、挿入ソートを使っていたと思います。Javaのソースコードを読んでください。型パラメータが登場してわかりにくいですが。

Answer 1

ご提示のJavaソースプログラムは、質問者さん自身が書かれたものですよね？　それを前提に回答します。
疑問の出どころが少し謎なのですが、おそらく質問者さんの発想が反対なのです。

まず、オブジェクトのリストを収めるインターフェースList<T>を実装した具象クラスArrayList<T>が使われています。このクラスにはsortメソッドがあります。質問者さんが使っているものです。

このsortメソッド内で行っているソート処理は、どのようにソートをしているか、使う者、つまりプログラマーが意識する必要はありません。JavaのAPIとして適切なソートアルゴリズムが採用され、実装されています。APIの仕様に沿って使えば、結果的に要望通りにリストの要素をソートしたものが出来上がります。ソートの実行中に各要素がどのようにかき回されているか意識する必要はありません。つまり、

2，3を比較した後、3，1を比較し2，3，1という順番になり次にif(s2.getId()<s1.getId()) が処理され2，3，1が2，1，3になり...

などと意識する必要はないのです。

ArrayList<T>は総称型でその要素として様々なクラスを格納することができますが、その各要素の昇順、降順を知っているのはそのクラスを書いたプログラマー、すなわち質問者さん自身だけです。その昇順、降順を決めるためのインターフェースが、Comparator<T>です。このインターフェースを仕様に従ってプログラマーである質問者さんが適切に実装し、sortメソッドの呼び出し時に「比較する為の関数型インターフェースのオブジェクト」として引き渡せば、ソート処理の中でそれを利用し並び替えを行ってくれる、ということなのです。

Comments

[xebme]

気になったので、Java APIのソースコードを調べてみました。基本戦略はマージソートです。

ArrayListのsortは、Arrays#sortに処理を委譲します。特に指定しなければTimSortクラスを利用します。今回は要素数が256より小さいのでマージは行わず内部でbinarySortを呼びます。ソート方法はbinary insertion sortと呼ばれ、挿入ソートの一種ですが、2分探索のような比較を行い、要素をずらします。(Tim Peterのアルゴリズムを利用。作者は Josh Bloch でした)

このような実装ですが、よりよいアルゴリズムが発見されれば、実装が変わる可能性があり、dodox86さんのおっしゃるように、ソートはAPIのなかで行われ、アルゴリズムは利用者が知る必要なく、ソートに要素の比較方法だけを知らせれば良い。というのが妥当な回答です。

[dodox86]

@xebmeさん

詳細なフォロー情報、どうもありがとうございます。私も大変参考になります。
「質問への追記・修正、ベストアンサー選択の依頼」欄でのxebmeさんの[2021/10/23 07:36]のコメントを気にしてはいたのですが、興味深いお話です。Javaの前のバージョン、処理系でも変わってきているかもしれませんね。