Javaで正しくソートを行う方法

多くのオープンソース Java プロジェクトのソース コードを分析したところ、ほとんどの開発者が 2 つの異なる方法でソートを実装しているだけであることがわかりました。sort()1 つはクラスメソッドCollectionsまたはの使用に基づいており、もう 1 つはや などArraysの自己ソート データ構造の使用に基づいています。 TreeMapTreeSet

sort() メソッドの使用

コレクションを並べ替える必要がある場合は、 を使用しますCollections.sort()。

// Collections.sort(…)
List<ObjectName> list = new ArrayList<ObjectName>();
Collections.sort(list, new Comparator<ObjectName>() {
	public int compare(ObjectName o1, ObjectName o2) {
		return o1.toString().compareTo(o2.toString());
	}
});

配列を並べ替える必要がある場合は、 を使用しますArrays.sort()。

// Arrays.sort(…)
ObjectName[] arr = new ObjectName[10];
Arrays.sort(arr, new Comparator<ObjectName>() {
	public int compare(ObjectName o1, ObjectName o2) {
		return o1.toString().compareTo(o2.toString());
	}
});

このメソッドは、sort()コレクションまたは配列にすでに値が入力されている場合に非常に便利です。

自己ソートデータ構造の使用

リスト ( List) またはセット ( Set) をソートする必要がある場合は、TreeSetソート構造を使用します。

// TreeSet
Set<ObjectName> sortedSet = new TreeSet<ObjectName>(new Comparator<ObjectName>() {
	public int compare(ObjectName o1, ObjectName o2) {
		return o1.toString().compareTo(o2.toString());
	}
});
sortedSet.addAll(unsortedSet);

辞書 ( Map) をソートする必要がある場合は、TreeMapソート構造を使用します。TreeMapキー ( key) でソートされます。

// TreeMap – использующий String ключи и компаратор (Comparator) CASE_INSENSITIVE_ORDER,
// упорядочивающий строки (String) методом compareToIgnoreCase
Map<String, Integer> sortedMap = new TreeMap<String, Integer>(String.CASE_INSENSITIVE_ORDER);
sortedMap.putAll(unsortedMap);

//TreeMap – общий случай, компаратор указывается вручную
Map<ObjectName, String> sortedMap = new TreeMap<ObjectName, String>(new Comparator<ObjectName>() {
	public int compare(ObjectName o1, ObjectName o2) {
		return o1.toString().compareTo(o2.toString());
	}
});
sortedMap.putAll(unsortedMap);

上記の方法は、コレクション内の要素に対して多数の検索を実行する必要がある場合に非常に役立ちます。自己ソート データ構造は、O(log(n))よりも効率が優れていますO(n)。これは、コレクション内のデータの量が 2 倍になった場合、検索時間は 2 倍ではなく、一定量 だけ増加することを意味します。

並べ替え問題に対する間違ったアプローチ

プログラマーが独自にソート アルゴリズムを説明する例が今でも見つかります。以下に示すソート コード (double 配列を昇順でソート) を考えてみましょう。このコードは非効率であるだけでなく、判読できません。そしてそのような例はたくさんあります。

double t;
for (int i = 0; i < N; i++)
	for (int j = i + 1; j < N; j++)
		if (r[j] < r[i]) {
			t = r[i];
			r[i] = r[j];
			r[j] = t;
		}