1. /
  2. /
  3. Javaのソートの方法を一通り確認できるページ

Javaのソートの方法を一通り確認できるページ

  • このエントリーをはてなブックマークに追加
  • Pocket

Javaでプログラミングを書いている際、数字を並び替えたい、文字を並び替えたいということは必ずあるだろう。並び替えを整えることを、ソートという。

このページではJavaでのソートの方法についてまとめてご紹介した。

Javaソート

ソートとは、値を小さい値から大きい値へ、また大きい値から小さい値へなどある規則に従って並べることである。例えば、[ 4 3 2 5 1 ]という数字の並びを小さい値から大きい値へソートすると[ 1 2 3 4 5 ]となる。

Javaでこのようなソートを行う方法はたくさんある。コードをすべて一から書くこともできるし、既にあるクラスのメソッドやクラスライブラリを活用する方法もある。これらをまとめてみると以下のようになる。

クラス名

対象

ソートの方法

独自のクラス

独自に設定

独自のメソッドを定義

詳細は、「独自のクラスとメソッドを定義する」を見てください。

java.util.Arrays

配列

オブジェクトのメソッドsort()を呼び出す。

詳細は、「java.util.Arrays使ってソートする」のセクションを見てください。

ArrayList

List

オブジェクトのメソッドsort()を呼び出す。

詳細は、別の記事の「Java 配列の容量と順序を簡単に扱う(ArrayList)」にあるソートのセクションを見てください。

TreeSet

Set

要素を追加する時に自動的に行われる。

詳細は、「TreeSetによるソートする」のセクションを見てください。

TreeMap

Map

要素を追加する時に自動的に行われる。

詳細は、「TreeMapによりソートする」のセクションを見てください。

Collections

List

ソート対象を引数として、クラスメソッドsort()を呼び出す

ソートの対象が配列で、その大きさが固定であれば、「java.util.Arraysのsort()メソッド」が使える。しかし、ソートの対象にもList/Set/Mapなど色々な種類がある。また、その対象に対してソート以外に追加や削除などの操作を行う必要がある場合、クラスライブラリの中には既にそうした操作を持っているものがあるので、よく調べて活用するとよい。

では、それぞれの対象に応じたソートの方法を実際にみてみよう。

独自のクラスとメソッドを定義する

ソートのために独自のクラスとメソッドを定義するために、どのようなアルゴリズムでソートするか、つまりソートする手順を決める必要がある。ここでは、よく知られているバブルソートというアルゴリズムを、サンプルプログラムに使っている。

ます、そのバブルソートについて、簡単に説明しよう。

バブルソート

バブルソートは、その様子が泡（バブル）が昇っていく様子に似ているのでそう名付けられた。その詳細をインデックスの変化とともに説明する。

一回目と二回目のループ：

sort01

一回目のループでは、array[4]とarray[3]の比較から始まって、array[1]とarray[0]の比較で終わる。もし、インデックスが小さいほうの値が大きければ入れ替える。そうすると、最も大きな値が配列の最初、つまり図の一番上に来る。二回目のループでは、既に一番上の値は決まっているので、比較をarray[4]とarray[3]の比較から始めて、array[2]とarray[1]の比較で終わればよい。

三回目と四回目のループ：

sort02

三回目、四回目と、上位の要素の値が確定していくので、比較回数は減っていく。そして、四回目でソートは終わる。

サンプルプログラム

このプログラムは、前のセクションで説明したソートでよく知られているバブルソートのアルゴリズムを使ってコードの全てを書いたものである。既存のメソッドやクラスライブラリを一切使っていない。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import java.util.Arrays;
 
public class BubbleSort {
    public static void main(String[] args) {
        int[] array = {4, 1 ,3 ,2, 0};//[1]
        sort(array);//[2]
        System.out.println("[3] " + Arrays.toString(array));
    }
    private static void sort(int[] array) {//[10]
        int elementEndIndex = array.length - 1;//[11]
        for (int comparisonEndIndex = 0; comparisonEndIndex < elementEndIndex; comparisonEndIndex++) {//[12]
            swapIfGreaterThan(array, comparisonEndIndex, elementEndIndex);//[13]
        }
    }
    private static void swapIfGreaterThan(int[] array, int comparisonEndIndex, int elementEndIndex) {//[20]
        for (int comparisonIndex = elementEndIndex; comparisonIndex > comparisonEndIndex; comparisonIndex--) {//[21]
            if(array[comparisonIndex] < array[comparisonIndex - 1]) {//[22]
                swapElementOfArray(array, comparisonIndex);//[23]
            }
        }
    }
    private static void swapElementOfArray(int[] array, int index) {//[30]
        int temp = array[index];//[31]
        array[index] = array[index - 1];//[32]
        array[index - 1] = temp;//[33]
    }
}

実行結果

プログラムの説明

それでは簡単にプログラムの解説をしておこう。

  • [1] 整数型の配列を宣言し、要素に5, 1 ,3 ,2, 4, 0を代入する。
  • [2] メソッドsort()を呼び出す。
  • [3] 配列要素を表示する。
  • [10] メソッドsort()を定義する。
  • [11]-[13] 比較終了位置comparisonEndIndexをインクリメントしながら最終要素位置elementEndIndexと共に引数としてswapIfGreaterThan()を呼び出す。
  • [20] メソッドswapIfGreaterThan()を定義する。
  • [21]-[23] 最終要素位置elementEndIndexを比較開始インデックスとし、比較終了位置comparisonEndIndexまでデクリメントしながら比較を行う。もし、インデックスが小さいほうの値が大きければ、メソッドswapElementOfArray()を呼び出す。
  • [30] メソッドswapElementOfArray ()を定義する。
  • [31]-[33] 配列の要素を交換する。

java.util.Arrays使ってソートする

固定の配列をそのままソートするのであれば、java.util.Arraysのsort()メソッドを使える。配列全てを対象とするか、それとも範囲を指定するかによって二つのメソッドから選べるようになっている。

それらのメソッドの仕様を見てみよう。

メソッドの仕様

ここではint型のみを記載するが、以下の要素に対してsort()メソッドは同じ仕様でオーバーロードされている。

  • プリミティブ型：byte, char, short, int, float, double型
  • オブジェクト

つまり、以下のAPI仕様の中の「int」の部分を他の型、byteやcharなどに置き換えて考えればよい。

sort(int[] a)

戻り値の型

public static void

内容

指定された配列を昇順にソートする。

 

実装のための留意点：分類するアルゴリズムには、ウラジミル・ヤロスラフスキー、ジョン・ベントレイ、そしてジョシュア・ブロッチによる「Dual-Pivot Quicksort」である。このアルゴリズムは、他のクイックソートの性能を二次方程式の性能に下げるたくさんのデータセットにO(n log(n))の性能を提供する。それは、通常従来の（one-pivot）クイックソートより速い。

 

引数：

a – ソートされる配列

sort(int[] a, int fromIndex, int toIndex))

戻り値の型

public static void

内容

配列の指定された範囲を昇順にソートする。ソートされる範囲は、fromIndexインデックスからtoIndexインデックスまである。もしfromIndex == toIndexならば、ソートされる範囲は空になる。

実装のための留意点：上記と同じ

 

引数：

a – ソートされる配列

fromIndex – ソートされる要素を含む、最初の要素のインデックス

toIndex - ソートされる要素を除く、最後の要素のインデックス

 

例外：

IllegalArgumentException - もしfromIndex > toIndexであるならば。

ArrayIndexOutOfBoundsException - もしfromIndex < 0 又は toIndex > a.lengthであるならば。

サンプルプログラム

1
2
3
4
5
6
7
8
9
10
11
12
import java.util.Arrays;
 
public class ArraysSort {
    public static void main(String[] args) {
        int[] array1 = {4, 3, 2, 5, 1};//[1]
        int[] array2 = {4, 2, 11, 33, 55};//[2]
        Arrays.sort(array1);//[3]
        Arrays.sort(array2, 2, 4);//[4]
        System.out.println("[5] " + Arrays.toString(array1));
        System.out.println("[6] " + Arrays.toString(array2));
    }
}

実行結果

プログラムの説明

  • [1] 配列array1を定義し、配列要素を代入する。
  • [2] 配列array2を定義し、配列要素を代入する。
  • [3] メソッド：sort()でarray1をソートする。
  • [4] メソッド：sort()でarray2をインデックス2から4までの範囲でソートする。
  • [5] 配列array1の要素すべてを表示する。
  • [6] 配列aaray2の要素すべてを表示する。

java.util.Collections使ってソートする

Listクラスをソートするのであれば、java.util. Collectionsのsort()メソッドを使える。このメソッドは、List.sort()メソッドと同等である。それで、Collectionsのクラスメソッドの引数としてListクラスのオブジェクトを渡すか、それともListクラスのオブジェクトのメソッドを呼び出すかは、状況に応じて決めることになる。

メソッドの仕様

sort(List<T> list)

戻り値の型

public static <T extends Comparable<? super T>>

内容

要素の自然な順序付けに応じて、指定されたリストを小さい方から大きい方への順序でソートする。リストの中のすべての要素はComparable interfaceを実装していなければならない。さらに、リストの中のすべての要素は相互に比較可能でなければならない。（つまり、e1.compareTo(e2)は、リスト内のどんな要素e1とe2に対してもClassCastExceptionを投げてはならない。）

このソートは安定していることが保証されている。：ソートの結果として、等しい要素を再び並び替えることはしない。

指定されたリストは修正可能でなければならないが、サイズを変更可能である必要はない。

実行上の留意点：

この実行は、指定されたリストとnull comparatorによるList.sort(Comparator)メソッドと同じである。

型引数：

T - リストの中のオブジェクトのクラス

引数：

list - ソートされるリスト

例外:

ClassCastException - もしリストが相互に比較可能でない要素を含むならば（例えば、文字列群と整数群）。

UnsupportedOperationException - もし指定されたlistのlist-iteratorがsetオペレーションをサポートしないならば。

IllegalArgumentException - (オプション) もし実行が、リストの要素の自然な順序付けがComparableの契約に違反していることを検出したならば。

参照:

List.sort(Comparator)

sort(List<T> list, Comparator<? super T> c)

戻り値の型

public static <T> void

内容

指定されたcomparatorによる順序付けによって、指定されたリストをソートする。リストの中のすべての要素は、指定されたcomparatorによって相互に比較可能でなければならない。（つまり、c.compare(e1,e2)は、リストの中のどんな要素e1とe2に対してもClassCastExceptionを投げてはならない。）

このソートは安定していることが保証されている。：ソートの結果として、等しい要素を再び並び替えることはしない。

指定されたリストは修正可能でなければならないが、サイズを変更可能である必要はない。

 

実行上の留意点：

この実行は、指定されたリストとcomparatorによるList.sort(Comparator)メソッドと同じである。

 

型引数：

T - リストの中のオブジェクトのクラス

引数：

list - ソートされるリスト

c - リストの順序を決定するcomparator。null値は、要素の自然な順序付けが使用されるべきだということを示す。

例外:

ClassCastException - もしリストが相互に比較可能でない要素を含むならば（例えば、文字列群と整数群）。

UnsupportedOperationException - もし指定されたlistのlist-iteratorがsetオペレーションをサポートしないならば。

IllegalArgumentException - (オプション) もし実行が、リストの要素の自然な順序付けがComparableの契約に違反していることを検出したならば。

参照:

List.sort(Comparator)

既存のソートを使ったサンプルプログラム

このサンプルプログラムは、自動車の番号と色をフィールドに持つCarImplementedComparableクラスから生成されたオブジェクト群をソートするというものだ。ソートするためのインターフェースがCarImplementedComparableクラスに実装されている。

  • CollectionsSortWithoutComparatorクラス：util.Collections使ってソートを行う。
  • CarImplementedComparableクラス：車の番号と色をフィールドとして持つ。ソートするために車の番号を比較するインターフェースのメソッドcompareTo()が実装されている。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.ArrayList;
import java.util.Collections;
 
public class CollectionsSortWithoutComparator {
    public static void main(String[] args) {
        ArrayList <CarImplementedComparable>list = new ArrayList<CarImplementedComparable>();//[1]
        list.add(new CarImplementedComparable(105, "red"));//[2]
        list.add(new CarImplementedComparable(102, "blue"));//[3]
        list.add(new CarImplementedComparable(101, "green"));//[4]
        list.add(new CarImplementedComparable(104, "yellow"));//[5]
        list.add(new CarImplementedComparable(103, "black"));//[6]
 
        Collections.sort(list);//[7]
        for (CarImplementedComparable carNumber: list) {//[8]
            System.out.print("[9] Car Number = " + carNumber.number());//[9]
            System.out.println(", Cokor = " + carNumber.color());
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class CarImplementedComparable implements Comparable<CarImplementedComparable> {//[20]
    private int number;//[21]
    private String color;//[22]
    public CarImplementedComparable(int number, String color) {//[23]
        this.number = number;//[24]
        this.color = color;//[25]
    }
    public int number() {//[26]
        return this.number;//[27]
    }
    public String color() {//[28]
        return this.color;//[29]
    }
    @Override
    public int compareTo( CarImplementedComparable car ){//[11]
        return this.number() - car.number();//[12]
    }
}

実行結果

1
2
3
4
5
[9] Car Number = 101, Cokor = green
[9] Car Number = 102, Cokor = blue
[9] Car Number = 103, Cokor = black
[9] Car Number = 104, Cokor = yellow
[9] Car Number = 105, Cokor = red

プログラムの説明

  • [1] ArrayList型のオブジェクトcarsを生成する。
  • [2]-[6] Carクラスのオブジェクト：105-red、102- blue、101-green、104-yellow、103-blackをcarsに追加する。
  • [7] carsを番号で昇順にソートする。
  • [8]-[9] 車の番号と色を表示する。
  • [20] Carクラスを定義する。
  • [21] フィールドnumberをint型で定義する。
  • [22] フィールドcolorをStringクラスで定義する。
  • [23]-[25] コンストラクタを定義し、引数でnumberとcolorの初期値を設定する。
  • [26]-[27] numberの値を返すメソッドを定義する。
  • [28]-[29] colorメソッドを定義する。
  • [30] compareToメソッドを定義する。
  • [31] フィールドnumberから引数のオブジェクトcarのnumberを引いた値を戻す。

独自にソートを記述したサンプルプログラム

このサンプルプログラムは、自動車の番号と色をフィールドに持つCarクラスから生成されたオブジェクト群をソートするというものだ。ソートするためのComparatorもNumberComparatorとして用意している。

  • CoolectionsSortクラス：util.Collections使ってソートを行う。
  • Carクラス：車の番号と色をフィールドとして持つ。
  • NumberComparaterクラス：ソートするために車の番号を比較する。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.ArrayList;
import java.util.Collections;
 
public class CollectionsSort {
    public static void main(String[] args) {
        ArrayList<Car> cars = new ArrayList<Car>();//[1]
        cars.add(new Car(105, "red"));//[2]
        cars.add(new Car(102, "blue"));//[3]
        cars.add(new Car(101, "green"));//[4]
        cars.add(new Car(104, "yellow"));//[5]
        cars.add(new Car(103, "black"));//[6]
 
        Collections.sort(cars, new NumberComparator());//[7]
        for (Car carNumber: cars) {//[8]
            System.out.print("[9] Car Number = " + carNumber.number());//[9]
            System.out.println(", Color = " + carNumber.color());
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Car {//[20]
    private int number;//[21]
    private String color;//[22]
    public Car(int number, String color) {//[23]
        this.number = number;//[24]
        this.color = color;//[25]
    }
    public int number() {//[26]
        return this.number;//[27]
    }
    public String color() {//[28]
        return this.color;//[29]
    }
}

1
2
3
4
5
6
7
8
9
10
11
import java.util.Comparator;
 
public class NumberComparator implements Comparator<Car> {
    public int compare (Car carNumber1, Car carNumber2) {
        if (carNumber1.number() > carNumber2.number())
            return 1;
        if (carNumber1.number() > carNumber2.number())
            return 0;
        return -1;
    }
}

実行結果

プログラムの説明

  • [1] ArrayList型のオブジェクトcarsを生成する。
  • [2]-[6] Carクラスのオブジェクト：105-red、102- blue、101-green、104-yellow、103-blackをcarsに追加する。
  • [7] carsを番号で昇順にソートする。
  • [8]-[9] 車の番号と色を表示する。
  • [20] Carクラスを定義する。
  • [21] フィールドnumberをint型で定義する。
  • [22] フィールドcolorをStringクラスで定義する。
  • [23]-[25] コンストラクタを定義し、引数でnumberとcolorの初期値を設定する。
  • [26]-[27] numberの値を返すメソッドを定義する。
  • [28]-[29] colorの値を返すメソッドを定義する。
  • [40] NumberComparatorクラスを定義する。
  • [41] メソッドcompare()を定義する。
  • [42]-[43] carNumber1のnumberがcarNumber2より大きい時、1を戻す。
  • [44]-[45] carNumber1のnumberがcarNumber2と等しい時、0を戻す。
  • [46] -1を戻す。

TreeSetによりソートする

TreeSetは、要素が追加される毎に自動的にソートが実行されるクラスである。よって、メソッドsort()は存在しない。ソートされた要素の順序が必要であれば、このTreeSetに要素を入れておけばよい。

サンプルプログラム

このサンプルプログラムでは、ソートが行われるとことを示すためにLinkedHashSetのオブジェクトに要素を追加して、その後、TreeSetをLinkedHashSetのオブジェクトから生成している。結果は、追加された要素の順番がソートされた順番になっている。この点を確認してほしい。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.LinkedHashSet;
import java.util.TreeSet;
 
public class TreeSetSort {
    public static void main(String[] args) {
        LinkedHashSet<String> hashSet = new LinkedHashSet<String>();//[1]
        hashSet.add("005");//[2]
        hashSet.add("002");//[3]
        hashSet.add("004");//[4]
        hashSet.add("003");//[5]
        hashSet.add("001");//[6]
 
        System.out.println("[7] LinkedHashSet = " + hashSet.toString());
        TreeSet<String> treeSet = new TreeSet<String>(hashSet);//[8]
        System.out.println("[9] TreeSet =        " + treeSet.toString());
    }
}

実行結果

プログラムの説明

  • [1] LinkedHashSetクラスのオブジェクトlinkedHashSetを生成する。
  • [2]-[6] オブジェクトlinkedHashSetに文字列オブジェクト："005"、"003"、"004"、"002"、"001"を追加する。
  • [7]-[9] linkedHashSetの内容を全て表示する。
  • [10] linkedHashSetからTreeSetクラスのオブジェクトtreeSetを生成する。
  • [7]-[9] treeSetの内容を全て表示する。

TreeMapによりソートする

TreeMapは、要素が追加される毎に自動的にソートが実行されるクラスである。よって、メソッドsort()は存在しない。ソートされた要素の順序が必要であれば、このTreeMapに要素を入れておけばよい。

サンプルプログラム

このサンプルプログラムでは、ソートが行われるとことを示すためにLinkedHashMapのオブジェクトに要素を追加して、その後、TreeMapをLinkedHashMapのオブジェクトから生成している。結果は、追加された要素の順番がソートされた順番になっている。この点を確認してほしい。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.LinkedHashMap;
import java.util.TreeMap;
 
public class TreeMapSort {
    public static void main(String[] args) {
        LinkedHashMap<String, String> map = new LinkedHashMap<String, String>();//[1]
        map.put("005","AAA");//[2]
        map.put("003","BBB");//[3]
        map.put("004","CCC");//[4]
        map.put("002","DDD");//[5]
        map.put("001","EEE");//[6]
 
        System.out.println("[7] LinkedHashMap");
        for (String key : map.keySet()) {//[8]
            System.out.println("[9] key = " + key + " : " + map.get(key));
        }
        TreeMap<String, String> treeMap = new TreeMap(map);//[10]
        System.out.println("[11] TreeMap");
        for (String key : treeMap.keySet()) {//[12]
            System.out.println("[13] key = " + key + " : " + map.get(key));
        }
    }
}

実行結果

1
2
3
4
5
6
7
8
9
10
11
12
[7] LinkedHashMap
[9] key = 005 : AAA
[9] key = 003 : BBB
[9] key = 004 : CCC
[9] key = 002 : DDD
[9] key = 001 : EEE
[11] TreeMap
[13] key = 001 : EEE
[13] key = 002 : DDD
[13] key = 003 : BBB
[13] key = 004 : CCC
[13] key = 005 : AAA

プログラムの説明

  • [1] LinkedHashMapクラスのオブジェクトlinkedHashMapを生成する。
  • [2]-[6] オブジェクトlinkedHashMapに文字列オブジェクト："005"-"AAA"、"003"-"BBB"、"004"-"CCC"、"002"-"DDD"、"001"-"EEE"を追加する。
  • [7]-[9] linkedHashMapの内容を全て表示する。
  • [10] linkedHashMapからTreeMapクラスのオブジェクトtreeMapを生成する。
  • [11]-[13] treeMapの内容を全て表示する。

まとめ

このページではJavaのソートの方法についてまとめてご紹介をした。もちろんゼロから書くこともできるが、既存のメソッドやコレクションの機能を使ってソートする方が手っ取り早いだろう。

使うときに参考にしていただければと思う。

  • このエントリーをはてなブックマークに追加
  • Pocket

このページの続きや関連ページは下記から一覧で確認できます。

IT講師に興味はありませんか？

・「今までIT講師をやってきたが、更に多くの講義を行いたい」

・「エンジニアとしてやってきたが講師業に魅力を感じている」

・「講師として活躍するためにベースとなる知識を知りたい」

・「様々な分野や言語の講師にチャレンジしてみたい」


という方はぜひIT講師募集のページをご覧ください。


リスキルテクノロジーでは「受講している方々にITを好きになってもらう」ことを目標に、同じ目標に向かって歩んで行ける講師の方を常に探しています。


システム開発やインフラ構築などのエンジニアリング経験を活かし、新入社員などの未経験者や経験の浅い初学者の方々に対してITトレーニングを行っていただくことになります。


テキストやカリキュラムは事前に用意されており、それらを元に講義を進めていくため、IT講師をはじめて実施する方でも安心してトレーニングを実施できます。


IT講師募集のページを見る

SNSでもご購読できます。

コメントを残す

*

未経験からの育成制度も充実
IT講師に興味はありませんか？

リスキルテクノロジーでIT講師の積極募集を開始！ 経験・未経験問わずご応募可能。育成制度で講師スキル向上も目指せます

IT講師に応募する