Come eseguire correttamente l'ordinamento in Java

Analizzando il codice sorgente di molti progetti Java open source, ho scoperto che la maggior parte degli sviluppatori implementa l'ordinamento solo in due modi diversi. Uno di questi si basa sull'uso del metodo sort()della classe Collectionso Arrays, mentre l'altro si basa sull'uso di strutture dati auto-ordinanti come TreeMape TreeSet.

Utilizzando il metodo sort()

Se devi ordinare una raccolta, utilizza il formato 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());
	}
});

Se è necessario ordinare un array, utilizzare 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());
	}
});

Il metodo sort()è molto comodo quando la raccolta o l'array è già pieno di valori.

Utilizzo di strutture dati auto-ordinanti

Se è necessario ordinare un elenco ( List) o un insieme ( Set), utilizzare una TreeSetstruttura di ordinamento.

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

Se è necessario ordinare un dizionario ( Map), utilizzare una TreeMapstruttura di ordinamento. TreeMapordinati per chiave ( 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);

L'approccio sopra descritto è molto utile nei casi in cui è necessario eseguire un gran numero di ricerche di elementi in una raccolta. Le strutture dati auto-ordinanti hanno un'efficienza O(log(n))migliore di O(n). Ciò significa che quando la quantità di dati nella raccolta raddoppia, il tempo di ricerca non raddoppia, ma aumenta di una quantità costante .

Cattivo approccio al problema di ordinamento

Puoi ancora trovare esempi in cui i programmatori descrivono in modo indipendente gli algoritmi di ordinamento. Considera il codice di ordinamento presentato di seguito (ordinamento di un doppio array in ordine crescente ). Questo codice non solo è inefficiente, ma anche illeggibile. E ci sono molti di questi esempi.

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