Java:インスタンスの並び替えの仕組みについて

Question

前提

javaの基礎を本で勉強中の初心者です。
下のコードは、ある入門書のサンプルコードを少し変えたものです。
インスタンスをnumberで並び替えています。
下記のコードでエラーはありませんでした。

●環境
・java version 13.0.2
・Atom 1.44.0
・script 3.25.0
・jdk 13.0.2
●OS ：windows10

###質問内容
Question.javaの下から６行目の
①Collections.sort(list);
と
Account.javaの下から１０行目の
②public int compareTo(Account obj){
の関係、というか繋がりがよく分かりません。
①のCollectionsクラスのsort()メソッドは、（）内の順番を入れ替えてくれる。
②のComparableインターフェースから継承されたcompareTo()メソッドは、大小関係を比較してくれる。
そこまでは分かるのですが、②の引数（Account obj）は、どこで渡されたのでしょうか？
Collections.sort(list);　から　public int compareTo(Account obj){
までの過程、引数の受け渡しの流れがどれだけ考えても理解ができませんでした。

そこで、collectionsクラスとComparableクラス、その他関連したソースコードを読んでみたのですが、分からないクラスを調べていたら、さらに分からないクラスが出てきて、そこでもさらに分からないクラスが出てきて・・・、と頭がパンクしてしまいました。

ソースコードくらい読めないとこれからやっていけない、という意見はごもっともなのですが、とりあえずの基礎学習としては、ここはさらっと流した次に行った方がいいのでしょうか？それともきちんと根本まで理解してから次に進んだ方がいいのでしょうか？
また、もし①②の関係も説明していただけたら幸いです。
ご回答、よろしくお願いします。

該当のソースコード

Question.java(mainのソースコード）

import static java.lang.System.out;
import java.util.*;

public class Question{
  public static void main(String[]args){
    List<Account> list=new ArrayList<Account>();
    Account a=new Account();
    Account b=new Account();
    Account c=new Account();
    Account d=new Account();
    Account e=new Account();
    a.setAccountNo("First");
    b.setAccountNo("Second");
    c.setAccountNo("Third");
    d.setAccountNo("Fourth");
    e.setAccountNo("Fifth");
    a.setNumber(5);
    b.setNumber(4);
    c.setNumber(1);
    d.setNumber(2);
    e.setNumber(3);
    list.add(a);
    list.add(b);
    list.add(c);
    list.add(d);
    list.add(e);
    Collections.sort(list); //質問したい部分
    for(Account f:list){
    out.println(f.getAccountNo()+"   "+f.getNumber());
  }
  }
}

Account.java

import static java.lang.System.out;

public class Account implements Comparable<Account>{
  private String accountNo;
  private int number;

  public void setAccountNo(String accountNo){
    this.accountNo=accountNo;
  }

  public String getAccountNo(){
    return this.accountNo;
  }

  public void setNumber(int number){
    this.number=number;
  }

  public int getNumber(){
    return this.number;
  }

  public boolean equals(Object o){
    if(this==o){
      return true;
    }
      if(o instanceof Account){
        Account a=(Account) o;
        if(this.accountNo.equals(a.accountNo)){
          return true;
        }
      }
      return false;
    }

  public int compareTo(Account obj){　　//質問したい部分
  if(this.number<obj.number){
    return -1;
  }
  if(this.number>obj.number){
    return 1;
  }
  return 0;
}
}

実行結果

Third   1
Fourth   2
Fifth   3
Second   4
First   5

Answer 1

Collections.sort(List<T> list) の仕組みを知るには”インターフェース”と”ジェネリクス”の仕組みについて学習する必要があります。

Collections.sort() はインターフェース、ジェネリクスの仕組みを知るのにとても良い教材ですが、これをいきなり知ろうとすると難しいかもしれません。しかし頑張って説明してみます。

Javaの入門書を読んでいるとのことですが、クラスの説明の章に入る前に関数的なメソッドのプログラミング例を見てきたことと思います。その中に整数配列の並び替えのプログラムはありませんでしたか？

public static void sort(int[] target)
{
    int count = target.length;
    for(int i=0; i<count; i++)
    {
        /*
         * i ～ (count - 1) の間で最小値のインデックスを探索
         */
        int idxMin = i;
        for(int j=(i+1); j<count; j++)
        {
            if(target[idxMin] > target[j])
            {
                idxMin = j;
            }
        }

        // 最小値のインデックス idxMin の値と i を交換
        int tmp = target[i];
        target[i] = target[idxMin];
        target[idxMin] = tmp;
    }
}

上記は選択ソートと呼ばれる並び替えアルゴリズムです。Collections.sort() は上記とは違うソートアルゴリズムですが、とりあえず上記のような処理をしているとしましょう。この例では整数配列を並び替える処理ですから、sort() の引数が int[] であればどんなデータであってもOKです。このメソッドは立派なソート共通ライブラリとして公開できます。

今度はAccountリストの並び替えを上記に倣って書き換えてみましょう。

public static void sort(List<Account> list)
{
    int count = list.size();
    for(int i=0; i<count; i++)
    {
        int idxMin = i;
        for(int j=(i+1); j<count; j++)
        {
            Account min = list.get(idxMin);
            Account another = list.get(j);
            if(min.getNumber() > another.getNumber())
            {
                idxMin = j;
            }
        }

        // 最小値のインデックス idxMin の値と i を交換
        Account tmp = list.get(i);
        list.set(i, list.get(idxMin));
        list.set(idxMin, tmp);
    }
}

これで出来上がりです。しかしこれをソート共通ライブラリとして公開できるでしょうか？ できませんよね。なぜならこのメソッドは Account クラスのリストでないと並び替えが不可だからです。公開しようと思えば Account クラス以外でも並び替える必要があります。そこでジェネリクスによって、どんなクラスでも並び替えできるようにしましょう。

public static <E> void sort(List<E> list)
{
    int count = list.size();
    for(int i=0; i<count; i++)
    {
        int idxMin = i;
        for(int j=(i+1); j<count; j++)
        {
            E min = list.get(idxMin);
            E another = list.get(j);
            if(min.getNumber() > another.getNumber())  // ← getNumber() では比較できない！
            {
                idxMin = j;
            }
        }

        // 最小値のインデックス idxMin の値と i を交換
        E tmp = list.get(i);
        list.set(i, list.get(idxMin));
        list.set(idxMin, tmp);
    }
}

ジェネリクスにまだ慣れていないならば、クラス型"E"はObjectと読み替えてください。
ほとんどの処理はそのまま流用できますが、getNumber() で比較している個所だけはコンパイル・エラーです。なぜならクラス型"E"は、ここでは具体的な型が分からないため（Accountクラスかもしれないし、それ以外のクラスかもしれない）、Object型と同じと見なされ、Objectクラスで定義されているメソッドしか呼び出せません。

さて、比較処理において、”どちらが小さく、どちらが大きいか”が分かれば良いのですが、sort() メソッドはどのクラス型の比較なのか分からないため、比較のしようがありません。この比較方法を知っているのは誰かと言うと… 当然呼び出し側となりますよね。だって呼び出す側は何のクラス型か、を知っている訳ですから。

List<Account> list = Arrays.asList(new Account("First", 3), new Account("Second", 1), new Account("Third", 2));
Sorter.sort(list);  // ← ソートメソッドの呼び出し

呼び出し側が Account クラスで並び替えることを知っていて、更に number で比較したい、と考えている訳です。つまり２つのAccountオブジェクトをどう比較すればよいか、を知っているのです。で、あれば比較処理だけ呼び出し側に任せよう、となるのです。
このように共通処理のある処理だけを切り出して呼び出し側に任せる仕組みがインターフェースです。

この比較処理を担うインターフェースが Comparable であり、その比較処理は compareTo() です。ではこの Comparable を組み込んでみましょう。

public static <E extends Comparable<E>> void sort(List<E> list)
{
    int count = list.size();
    for(int i=0; i<count; i++)
    {
        int idxMin = i;
        for(int j=(i+1); j<count; j++)
        {
            E min = list.get(idxMin);
            E another = list.get(j);
            if(min.compareTo(another) > 0)  // ← compareTo() が返す値で比較！
            {
                idxMin = j;
            }
        }

        // 最小値のインデックス idxMin の値と i を交換
        E tmp = list.get(i);
        list.set(i, list.get(idxMin));
        list.set(idxMin, tmp);
    }
}

事前に Account クラスは Comparable インターフェースを実装しているものとします。そしてクラス型"E"はこれまでの Object 型扱いではなく、Comparable 型で扱えるよう、"E extends Comparable<E>" としました。これで "E" は compareTo() を呼び出せるようになります。

比較処理に注目してください。min はクラス型 "E" として扱われるので、compareTo() を呼び出すことができます。そしてこの compareTo() は、まさにあなたが Account クラスで実装した compareTo() なのです！

…とは言え、まだボヤッとしか見えてないかもしれません。焦らないでください。インターフェースを１から理解すれば、いずれ分かることです。

以下の本がインターフェースの理解につながると思います。私自身、とても助かりましたのでお勧めします。道は長いですが、頑張れば必ずプログラミングの考え方に広がりが持てますので。では！

「先輩、Javaのインターフェースって何ですか？」の答えに窮した時に読む本

Comments

[karakorum]

おおまかには理解できましたが、まだ随所わからない部分もあるので、ゆっくり考えていきたいと思います。
紹介してもらった本は、基礎学習が終わったら読んでみようと思います。
ありがとうございました。

[Mirko_Mug_Cup]

私も以前、なぜ compareTo() を実装しただけなのに並び替えができてしまうのか不思議でした。
多分、ネットで調べても分からない疑問だろうと思います。ソースを調べてまで知ろうとする姿に昔の自分を思い出しし、思わず頑張って書いてしまいました…
他の方も仰るように、この並び替えの詳細の理解は後回しでいいと思います。また紹介した本は仰る通り、ある程度Javaプログラムに慣れてからの方が良いでしょう。最初の内は分からなくても、何度も読み返せば理解できるようになると思いますよ。

[karakorum]

最初に言い忘れていましたが、とてもたくさんのコードを丁寧に書いていただき、とても助かりました！
分からないところは考えて、あまりにも難しかったら割り切って進めていきたいと思います。
色々とありがとうございました！

Answer 2

ソートアルゴリズムは数あれど、やっていることは基本的に2つの値を比較して、どちらが大きいかを判定し、それをもとに入れ替えなどを行うことです。基本的にソートアルゴリズムの説明をするところでは数値の比較・並べ替えを行うものがほとんどだと思いますが、数値でなくてもこの大小比較さえできれば、同様のアルゴリズムでソートができることになります。
ソートのメソッドsortの実行中、この大小比較が必要な時に、compareToメソッドを呼び出して、大小比較をすることになります。
例えばクイックソートの場合、基準値よりも大きいか小さいか、というチェックが入りますが、このチェック時に、数値を不等号で比較する代わりに、compareToを呼び出し、その結果から大小を判断します。

Comments

[karakorum]

単純な数値などはsortで比較ができるが、インスタンスの比較など、数値以外の大小関係を比較するときに、compareToが呼び出される、ということなんですね。
ありがとうございます。

Answer 3

あくまで私の考えと前置きしつつ、
javaの基礎を本で勉強中の初心者です。って人が現場に来たとして、
Collectionのソースコードくらい読めないとこれからやっていけない、とは思わないので安心してください。
なのでさらっと流したほうがいいと思います。

しかし、ソースから読めなくとも使い方がわかっている必要はあります。
Java13の日本語が見当たらなかったので、日本語がいい場合は8の方を参考にしてください。
Java13ドキュメント
Java8ドキュメント

ドキュメントを参考にすると、
・Listをソートしたい時にはsortを使う
・sortを使うためにはListの要素すべてにComparableを実装していなくてはいけない
・Accountにimplements Comparable<Account>とするとcompareTo()メソッドを実装しなくてはいけない
・compareTo()で順位付けを定義しているため
ぐらいのことをドキュメントなりから調べて使えば問題ないと思います。

また、Collectionの中でもよく使うものはしっかり使い方を押さえておきましょう。（List,Map,Setなど）

経験を積んで勉強していけばそのうち読めるようになるので、今は表面的に理解してい

Comments

[karakorum]

Listでソートをしてから、compareToまでのおおまかな流れがつかめました！
ありがとうございます。

Answer 4

sort と compareTo メソッドの関係、確かにややこしい部分ではありますね。

まず compareTo メソッドを考えます。これは二つのオブジェクトの大小関係を調べるメソッドです。
せっかく a, b, c, d, e の 5 つのオブジェクトを作ってるので、これらの大小関係を表示してみましょう。

    System.out.println("a vs b: " + a.compareTo(b));
    System.out.println("b vs c: " + b.compareTo(c));
    System.out.println("c vs d: " + c.compareTo(d));
    System.out.println("d vs e: " + d.compareTo(e));
    System.out.println("e vs e: " + e.compareTo(e));

実行結果

a vs b: 1
b vs a: -1
c vs d: -1
d vs c: 1
e vs e: 0

次に、二つのオブジェクトが入った配列を並べ替えるメソッドを考えます。例えば二つの整数なら、

    public static void sort2int(int[] array) {
        if (array[0] > array[1]) {
            int tmp = array[0];
            array[0] = array[1];
            array[1] = tmp;
        }
    }

ですが、二つの Account オブジェクトの場合は、compareTo メソッドを使って

    public static void sort2(Account[] array) {
        if (array[0].compareTo(array[1]) > 0) {
            Account tmp = array[0];
            array[0] = array[1];
            array[1] = tmp;
        }
    }

となります。Collections.sort() の中ではこんな風に compareTo メソッドが使われています。

Comments

[karakorum]

配列ではなく、インスタンスを比較するためにsortを使う場合は、compareToメソッドを呼び出し、上のような操作が行われている、ということなんですね。
ありがとうございました。