Javaでプログラミングを書いている際、数字を並び替えたい、文字を並び替えたいということは必ずあるだろう。並び替えを整えることを、ソートという。
このページではJavaでのソートの方法についてまとめてご紹介した。
目次 [hide]
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など色々な種類がある。また、その対象に対してソート以外に追加や削除などの操作を行う必要がある場合、クラスライブラリの中には既にそうした操作を持っているものがあるので、よく調べて活用するとよい。
では、それぞれの対象に応じたソートの方法を実際にみてみよう。
独自のクラスとメソッドを定義する
ソートのために独自のクラスとメソッドを定義するために、どのようなアルゴリズムでソートするか、つまりソートする手順を決める必要がある。ここでは、よく知られているバブルソートというアルゴリズムを、サンプルプログラムに使っている。
ます、そのバブルソートについて、簡単に説明しよう。
バブルソート
バブルソートは、その様子が泡(バブル)が昇っていく様子に似ているのでそう名付けられた。その詳細をインデックスの変化とともに説明する。
一回目と二回目のループ:
一回目のループでは、array[4]とarray[3]の比較から始まって、array[1]とarray[0]の比較で終わる。もし、インデックスが小さいほうの値が大きければ入れ替える。そうすると、最も大きな値が配列の最初、つまり図の一番上に来る。二回目のループでは、既に一番上の値は決まっているので、比較をarray[4]とarray[3]の比較から始めて、array[2]とarray[1]の比較で終わればよい。
三回目と四回目のループ:
三回目、四回目と、上位の要素の値が確定していくので、比較回数は減っていく。そして、四回目でソートは終わる。
サンプルプログラム
このプログラムは、前のセクションで説明したソートでよく知られているバブルソートのアルゴリズムを使ってコードの全てを書いたものである。既存のメソッドやクラスライブラリを一切使っていない。
実行結果
プログラムの説明
それでは簡単にプログラムの解説をしておこう。
- [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] 配列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] 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] 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] 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] 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のソートの方法についてまとめてご紹介をした。もちろんゼロから書くこともできるが、既存のメソッドやコレクションの機能を使ってソートする方が手っ取り早いだろう。
使うときに参考にしていただければと思う。