Bagaimana cara melakukan pengurutan dengan benar di Java

Saat menganalisis kode sumber dari banyak proyek Java sumber terbuka, saya menemukan bahwa sebagian besar pengembang mengimplementasikan pengurutan hanya dalam dua cara berbeda. Salah satunya didasarkan pada penggunaan metode sort()kelas Collectionsatau Arrays, dan yang lainnya didasarkan pada penggunaan struktur data pengurutan mandiri seperti TreeMapdan TreeSet.

Menggunakan metode sortir()

Jika Anda perlu mengurutkan koleksi, gunakan 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());
	}
});

Jika Anda perlu mengurutkan array, gunakan 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());
	}
});

Metode ini sort()sangat mudah digunakan ketika koleksi atau array sudah diisi dengan nilai.

Menggunakan struktur data penyortiran mandiri

Jika Anda perlu mengurutkan daftar ( List) atau set ( Set), gunakan TreeSetstruktur pengurutan.

// 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);

Jika Anda perlu mengurutkan kamus ( Map), gunakan TreeMapstruktur pengurutan. TreeMapdiurutkan berdasarkan kunci ( 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);

Pendekatan di atas sangat berguna jika Anda perlu melakukan pencarian elemen dalam koleksi dalam jumlah besar. Struktur data penyortiran mandiri memiliki efisiensi O(log(n))yang lebih baik daripada O(n). Artinya ketika jumlah data dalam koleksi berlipat ganda, waktu pencarian tidak berlipat ganda, namun bertambah dengan jumlah yang konstan .

Pendekatan yang buruk untuk menyortir masalah

Anda masih dapat menemukan contoh di mana pemrogram mendeskripsikan algoritma pengurutan secara mandiri. Pertimbangkan kode pengurutan yang disajikan di bawah ini (mengurutkan array ganda dalam urutan menaik ). Kode ini tidak hanya tidak efisien, tetapi juga tidak dapat dibaca. Dan masih banyak lagi contohnya.

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;
		}