java:comparatorインタフェースとソートについて

Question

インタフェースcomparatorをインプリメントし、compareメソッドを実装したクラスを定義すると、インスタンスの並び替え（ソート）ができるようになると思います。
この際、compareの返り値の正負によって並び替えできますが、なぜ正負によってソートできるのでしょうか？

import java.util.ArrayList;
import java.util.Collections;

public class SortTest {
	public static void main(String[] args) {

		ArrayList<String> list = new ArrayList<String>();
		lList.add("う");
		list.add("い");
		list.add("あ");

		for(int i=0;i<list.size();i++){
			System.out.println(list.get(i));
		}

		Collections.sort(list);
		System.out.println("反転");

		for(int i=0;i<list.size();i++){
			System.out.println(list.get(i));
		}

	}
}

Answer 1

ソートアルゴリズムを調べていればわかるかと思いますが、どんなソートも共通してやってることは2つの要素の大小を比較することです。
クイックソートやバブルソートなどはその結果入れ替えるか否かを判断するし、マージソートはどちらをマージ配列に入れなおすかを判定します。
とどのつまり、2つの要素を比較してその大小が判断できれば、数値に限らずソートができるのです。
その判断を、Comparator#compareやComparable#compareToの返り値の正、負、零によって行うのです。

Comments

[ikanosasimi]

なるほど、わかりました。
例えば

Arrays.sort(studentarray, new Comparator() {
public int compare(Object student1, Object student2) {
student2.getAge() - student1.getAge()
}

このように、compareメソッドの中をいじられてしまうと昇順か降順かわからなくなってしまいます。
どうやって判断すればいいのでしょうか？

[swordone]

いろいろ書き方おかしいですが、そこらへん補完して回答すると

student1のほうが年齢が高い場合
→compare(student1, student2) < 0 つまり概念的に書けばstudent1 < student2
(不等号の向きが同じであることがポイント)
→student1のほうが「小さい」ため先に並ぶ
年齢が高いほうが先に並ぶため、降順になる

Comparatorのstaticメソッドで生成し、降順にする場合にはreversed()を使って生成したほうがわかりやすくなります。

Arrays.sort(studentArray, Comparator.comparingInt(Student::getAge).reversed());

[ikanosasimi]

ありがとうございました

Answer 2

次のページを読んでみてください。

• 並べ替えのクラス設計

http://www.aerith.net/design/sort-design-j.html

...
データの並べ替えは、たくさんのソフトウェアで必要となる機能です。しかし、ソフトウェアを作るたびに、いちいちデータを並べ替えるプログラムを書いていたのでは大変です。多くのソフトウェアから共通に利用できる、汎用的な枠組みを作っておくと便利です。

では、汎用的な並べ替えの枠組みとは、どのようなものでしょうか。どんなデータも、どのようにも並べ替えられるためには、どんなクラスを作れば良いのでしょうか。

ここでは、データの並べ替えを、クラス設計の視点から考えてみます。

...

Comments

[ikanosasimi]

ありがとうございます。
せっかく、sortメソッドがあるのにもかかわらず、compareメソッドの中身をいじっているプログラムがあります。
その場合、ソートの方法が昇順か降順かわからなくなってしまいます。
どうすれば見分けることができるのでしょうか？

例
Arrays.sort(studentarray, new Comparator() {
public int compare(Object student1, Object student2) {
student2.getAge() - student1.getAge()
}