Javaでのソート

投稿日: 2019-10-18 2019-11-05
タグ: Java, Java Collections

1概要

この記事では、Java 7およびJava 8で

Array

、

List

、

Set

、および

Map

にソートを適用する方法について説明します。

2

Array

によるソート

まず__httpsを使用して整数配列をソートすることから始めましょう。方法。

以下の

int

配列を

@ Before

jUnitメソッドに定義します。

@Before
public void initVariables () {
    toSort = new int[]
      { 5, 1, 89, 255, 7, 88, 200, 123, 66 };
    sortedInts = new int[]
      {1, 5, 7, 66, 88, 89, 123, 200, 255};
    sortedRangeInts = new int[]
      {5, 1, 89, 7, 88, 200, 255, 123, 66};
    ...
}

2.1. 完全な配列のソート

では、単純な

Array.sort（）

APIを使用しましょう。

@Test
public void givenIntArray__whenUsingSort__thenSortedArray() {
    Arrays.sort(toSort);

    assertTrue(Arrays.equals(toSort, sortedInts));
}

ソートされていない配列は完全にソートされました。

----[1, 5, 7, 66, 88, 89, 123, 200, 255]----

公式のJavaDoc

に記載されているように、

Arrays.sort

はデュアルピボットを使用します。

プリミティブ

のクイックソートそれはO（n log（n））パフォーマンスを提供し、典型的には伝統的な（ワンピボット）Quicksort実装より速いです。

ただし、これはhttps://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#sort（java.lang.Object％5B％5D）の安定した適応的で反復的な実装を使用しています。オブジェクトの配列のマージソートアルゴリズム]。

2.2. 配列の一部をソートする

Arrays.sort

にはもう1つの

sort

APIがあります – これについてはここで説明します。

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

これは、2つのインデックスの間にある、配列の一部だけをソートします。

簡単な例を見てみましょう。

@Test
public void givenIntArray__whenUsingRangeSort__thenRangeSortedArray() {
    Arrays.sort(toSort, 3, 7);

    assertTrue(Arrays.equals(toSort, sortedRangeInts));
}

ソートは、次のサブ配列要素に対してのみ行われます（

toIndex

は排他的です）。

----[255, 7, 88, 200]----

メイン配列を含む結果のソート済みサブ配列は次のようになります。

----[5, 1, 89, 7, 88, 200, 255, 123, 66]----

2.3. Java 8

parallelSort

Java 8には、

Arrays.sort（）

APIと同様のシグネチャを持つ新しいAPI、

parallelSort

が付属しています。

@Test
public void givenIntArray__whenUsingParallelSort__thenArraySorted() {
    Arrays.parallelSort(toSort);

    assertTrue(Arrays.equals(toSort, sortedInts));
}

parallelSort（）の舞台裏では、

は（

parallelSort

のアルゴリズムの細分性に従って）さまざまな部分配列に配列を分割します。

sort

を並列に実行できるように各サブ配列は

Arrays.sort（）

でソートされ、ソートされた配列として最後にマージされます。

ForceJoin共通プール

は、これらの並列タスクを実行してから、結果。

Arrays.parallelSort

の結果はもちろん

Array.sort

と同じになるでしょう、それはマルチスレッドを利用することの問題です。

最後に、

Arrays.parallelSort

にも同様にAPI

Arrays.sort

の亜種があります。

Arrays.parallelSort (int[]a, int fromIndex, int toIndex);

3

List

をソートする

Collections.sort（）

java.utils.Collections

]

– 整数の

List__をソートするには:

@Test
public void givenList__whenUsingSort__thenSortedList() {
    List<Integer> toSortList = Ints.asList(toSort);
    Collections.sort(toSortList);

    assertTrue(Arrays.equals(toSortList.toArray(),
    ArrayUtils.toObject(sortedInts)));
}

ソート前の

List

には、以下の要素が含まれます。

----[5, 1, 89, 255, 7, 88, 200, 123, 66]----

----[1, 5, 7, 66, 88, 89, 123, 200, 255]----

Collections.Sort

については、Oracle JavaDoc

に記載されているように、変更されたものを使用します。マージソートを行い、

n log（n）

パフォーマンスを保証します。

4

Set

をソートする

次に、

Collections.sort（）

を使用して

LinkedHashSet

を並べ替えます。

挿入順序を維持するため、

LinkedHashSet

を使用しています。

Collections

–

で

sort

APIを使用するには、まずセットをリストに入れる

ことに注意してください。

@Test
public void givenSet__whenUsingSort__thenSortedSet() {
    Set<Integer> integersSet = new LinkedHashSet<>(Ints.asList(toSort));
    Set<Integer> descSortedIntegersSet = new LinkedHashSet<>(
      Arrays.asList(new Integer[]
        {255, 200, 123, 89, 88, 66, 7, 5, 1}));

    List<Integer> list = new ArrayList<Integer>(integersSet);
    Collections.sort(list, (i1, i2) -> {
        return i2 - i1;
    });
    integersSet = new LinkedHashSet<>(list);

    assertTrue(Arrays.equals(
      integersSet.toArray(), descSortedIntegersSet.toArray()));
}

5並べ替え

Map

このセクションでは、キーと値の両方でMapをソートする方法について見ていきます。

まずソートするマップを定義しましょう。

@Before
public void initVariables () {
    ....
    HashMap<Integer, String> map = new HashMap<>();
    map.put(55, "John");
    map.put(22, "Apple");
    map.put(66, "Earl");
    map.put(77, "Pearl");
    map.put(12, "George");
    map.put(6, "Rocky");
    ....
}

5.1. キーによる

Map

のソート

これで、

HashMap

から

keys

と

values

のエントリを抽出し、この例のキーの値に基づいて並べ替えます。

@Test
public void givenMap__whenSortingByKeys__thenSortedMap() {
    Integer[]sortedKeys = new Integer[]{ 6, 12, 22, 55, 66, 77 };

    List<Map.Entry<Integer, String>> entries
      = new ArrayList<>(map.entrySet());
    Collections.sort(entries, new Comparator<Entry<Integer, String>>() {
        @Override
        public int compare(
          Entry<Integer, String> o1, Entry<Integer, String> o2) {
            return o1.getKey().compareTo(o2.getKey());
        }
    });
    Map<Integer, String> sortedMap = new LinkedHashMap<>();
    for (Map.Entry<Integer, String> entry : entries) {
        sortedMap.put(entry.getKey(), entry.getValue());
    }

    assertTrue(Arrays.equals(sortedMap.keySet().toArray(), sortedKeys));
}

キーに基づいてソートされた

Entries

をコピーするときに

LinkedHashMap

をどのように使用したかに注意してください（

HashSet

はキーの順序を保証しないため）。

ソート前の

Map

:

----[Key: 66 , Value: Earl][Key: 22 , Value: Apple][Key: 6 , Value: Rocky][Key: 55 , Value: John][Key: 12 , Value: George][Key: 77 , Value: Pearl]----

キーでソートした後の

Map

:

----[Key: 6 , Value: Rocky][Key: 12 , Value: George][Key: 22 , Value: Apple][Key: 55 , Value: John][Key: 66 , Value: Earl][Key: 77 , Value: Pearl]----

5.2. 値による

Map

のソート

ここでは、

HashMap

の値に基づくソートのために

HashMap

エントリの値を比較します。

@Test
public void givenMap__whenSortingByValues__thenSortedMap() {
    String[]sortedValues = new String[]
      { "Apple", "Earl", "George", "John", "Pearl", "Rocky" };

    List<Map.Entry<Integer, String>> entries
      = new ArrayList<>(map.entrySet());
    Collections.sort(entries, new Comparator<Entry<Integer, String>>() {
        @Override
        public int compare(
          Entry<Integer, String> o1, Entry<Integer, String> o2) {
            return o1.getValue().compareTo(o2.getValue());
        }
    });
    Map<Integer, String> sortedMap = new LinkedHashMap<>();
    for (Map.Entry<Integer, String> entry : entries) {
        sortedMap.put(entry.getKey(), entry.getValue());
    }

    assertTrue(Arrays.equals(sortedMap.values().toArray(), sortedValues));
}

ソート前の

Map

:

----[Key: 66 , Value: Earl][Key: 22 , Value: Apple][Key: 6 , Value: Rocky][Key: 55 , Value: John][Key: 12 , Value: George][Key: 77 , Value: Pearl]----

値で** 並べ替えた後の

Map

:

----[Key: 22 , Value: Apple][Key: 66 , Value: Earl][Key: 12 , Value: George][Key: 55 , Value: John][Key: 77 , Value: Pearl][Key: 6 , Value: Rocky]----

6. カスタムオブジェクトの並べ替え

カスタムオブジェクトを使ってみましょう。

public class Employee implements Comparable {
    private String name;
    private int age;
    private double salary;

    public Employee(String name, int age, double salary) {
        ...
    }

   //standard getters, setters and toString
}

次のセクションでは、ソートの例として次の

Employee

配列を使用します。

@Before
public void initVariables () {
    ....
    employees = new Employee[]{
      new Employee("John", 23, 5000), new Employee("Steve", 26, 6000),
      new Employee("Frank", 33, 7000), new Employee("Earl", 43, 10000),
      new Employee("Jessica", 23, 4000), new Employee("Pearl", 33, 6000)};

    employeesSorted = new Employee[]{
      new Employee("Earl", 43, 10000), new Employee("Frank", 33, 70000),
      new Employee("Jessica", 23, 4000), new Employee("John", 23, 5000),
      new Employee("Pearl", 33, 4000), new Employee("Steve", 26, 6000)};

    employeesSortedByAge = new Employee[]{
      new Employee("John", 23, 5000), new Employee("Jessica", 23, 4000),
      new Employee("Steve", 26, 6000), new Employee("Frank", 33, 70000),
      new Employee("Pearl", 33, 4000), new Employee("Earl", 43, 10000)};
}

カスタムオブジェクトの配列またはコレクションを並べ替えることができます。

自然な順序で（

Comparable

インタフェースを使用）または
Comparator

Interface

によって提供された順序で

6.1. 比較可能____

javaの自然順序

は、指定された配列またはコレクション内でプリミティブまたはオブジェクトを正しい順序でソートする順序を意味します。

java.util.Arrays

とhttps://docs.oracle.com/javase/7/docsの両方/api/java/util/Collections.html[

java.util.Collections

]には

sort（）

メソッドがあります。

自然順序は

equals

のセマンティクスと一致させることを強くお勧めします。

この例では、同じ

name

を持つ従業員に等しいと見なします。

@Test
public void givenEmpArray__SortEmpArray__thenSortedArrayinNaturalOrder() {
    Arrays.sort(employees);

    assertTrue(Arrays.equals(employees, employeesSorted));
}

現在のオブジェクトと引数として渡されたオブジェクトを比較するための

compareTo（）

メソッドを持つ

Comparable

インターフェースを実装することで、要素の自然順序を定義できます。

これを明確に理解するために、

Comparable

Interfaceを実装する

Employee

クラスの例を見ましょう。

public class Employee implements Comparable {
    ...

    @Override
    public boolean equals(Object obj) {
        return ((Employee) obj).getName().equals(getName());
    }

    @Override
    public int compareTo(Object o) {
        Employee e = (Employee) o;
        return getName().compareTo(e.getName());
    }
}

一般的に、比較のためのロジックは

compareTo

というメソッドで書かれます。ここでは、従業員の注文または従業員フィールドの

name

を比較しています。 2人の従業員が同じ名前を持っていれば平等になります。

上記のコードで

Arrays.sort（employees）;

が呼び出されると、年齢別に従業員をソートする際のロジックと順序がわかります。

----[("Earl", 43, 10000),("Frank", 33, 70000), ("Jessica", 23, 4000),
 ("John", 23, 5000),("Pearl", 33, 4000), ("Steve", 26, 6000)]----

配列が従業員の名前でソートされているのがわかります。これが

Employee

Classの自然順序になります。

6.2.

Comparator

を使う

それでは、

Comparator

インターフェース実装を使用して要素をソートしましょう。ここでは、無名の内部クラスをその場で

Arrays.sort（）

APIに渡します。

@Test
public void givenIntegerArray__whenUsingSort__thenSortedArray() {
    Integer[]integers = ArrayUtils.toObject(toSort);
    Arrays.sort(integers, new Comparator<Integer>() {
        @Override
        public int compare(Integer a, Integer b) {
            return a - b;
        }
    });

    assertTrue(Arrays.equals(integers, ArrayUtils.toObject(sortedInts)));
}

では、従業員を

salary

に基づいてソートし、別のコンパレータ実装を渡します。

Arrays.sort(employees, new Comparator<Employee>() {
    @Override
    public int compare(Employee o1, Employee o2) {
       return (int) (o1.getSalary() - o2.getSalary());
    }
 });

salary

に基づいてソートされたEmployees配列は次のようになります。

----[(Jessica,23,4000.0), (John,23,5000.0), (Pearl,33,6000.0), (Steve,26,6000.0),
(Frank,33,7000.0), (Earl,43,10000.0)]----

Collections.sort（）

を使用して、オブジェクトの

List

と

Set

をNaturalまたはカスタムの順序で並べ替えることができます。

7. ラムダによるソート

Java 8から始めて、Lambdasを使用して

Comparator

Functional Interfaceを実装できます。

あなたはリンクを見てみることができます:/java8＃lambda[Java 8におけるLambdas]の書き方で構文を磨きます。

古いコンパレータを置き換えましょう。

Comparator<Integer> c  = new Comparator<>() {
    @Override
    public int compare(Integer a, Integer b) {
        return a - b;
    }
}

同等の実装では、Lambda式を使用します。

Comparator<Integer> c = (a, b) -> a - b;

最後に、テストを書きましょう。

@Test
public void givenArray__whenUsingSortWithLambdas__thenSortedArray() {
    Integer[]integersToSort = ArrayUtils.toObject(toSort);
    Arrays.sort(integersToSort, (a, b) -> {
        return a - b;
    });

    assertTrue(Arrays.equals(integersToSort,
      ArrayUtils.toObject(sortedInts)));
}

お分かりのように、ここではもっとクリーンでより簡潔なロジックを見てください。

8

Comparator.comparing

と

Comparator.thenComparing

を使用する

Java 8には、ソートに役立つ2つの新しいAPIが付属しています。https://docs.oracle.com/javase/8/docs/api/java/util/Comparator.html#comparing-java.util.function.Function-[

Comparator

インタフェースの//および

thenComparing（）

これらは

Comparator

の複数の条件を連鎖させるのに非常に便利です。

Employee

と

age

を比較し、次に

name

と比較するシナリオがあるとします。

@Test
public void givenArrayObjects__whenUsingComparing__thenSortedArrayObjects() {
    List<Employee> employeesList = Arrays.asList(employees);
    employees.sort(Comparator.comparing(Employee::getAge));

    assertTrue(Arrays.toString(employees.toArray())
      .equals(sortedArrayString));
}

この例では、__Employee: getAge

が、比較機能を備えた機能インターフェースを実装する

Comparator__インターフェースのソートキーです。

並べ替え後の従業員の数は次のとおりです。

----[(John,23,5000.0), (Jessica,23,4000.0), (Steve,26,6000.0), (Frank,33,7000.0),
(Pearl,33,6000.0), (Earl,43,10000.0)]----

ここでは、従業員は

age

に基づいてソートされています。

John

と

Jessica

は同じ年齢であることがわかります – これは、順序ロジックがそれらの名前を考慮に入れる必要があることを意味します。これは

thenComparing（）

を使用して実現できます。

...
employees.sort(Comparator.comparing(Employee::getAge)
  .thenComparing(Employee::getName));
...

上記のコードスニペットで並べ替えた後、従業員配列の要素は次のように並べ替えられます。

----[(Jessica,23,4000.0),
 (John,23,5000.0),
 (Steve,26,6000.0),
 (Frank,33,7000.0),
 (Pearl,33,6000.0),
 (Earl,43,10000.0)]----

したがって、

comparing（）

と

thenComparing（）

を使用すると、より複雑な並べ替えシナリオを確実に実装しやすくなります。

getdocs

13036

1概要

2 Array によるソート

2.1. 完全な配列のソート

2.2. 配列の一部をソートする

2.3. Java 8 parallelSort

3 List をソートする

4 Set をソートする

5並べ替え Map

5.1. キーによる Map のソート

5.2. 値による Map のソート