כיצד לבצע מיון נכון ב-Java

בניתוח קוד המקור של פרויקטי Java רבים בקוד פתוח, גיליתי שרוב המפתחים מיישמים מיון בשתי דרכים שונות בלבד. אחד מהם מבוסס על שימוש בשיטת sort()המחלקה Collectionsאו Arrays, והשני מבוסס על שימוש במבני נתונים מיון עצמי כגון TreeMapו TreeSet.

שימוש בשיטת 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). המשמעות היא שכאשר כמות הנתונים באוסף מכפילה את עצמה, זמן החיפוש אינו מוכפל, אלא עולה בכמות קבועה .

גישה גרועה לבעיית מיון

אתה עדיין יכול למצוא דוגמאות שבהן מתכנתים מתארים באופן עצמאי אלגוריתמי מיון. שקול את קוד המיון המוצג להלן (מיון מערך כפול בסדר עולה ) . קוד זה לא רק לא יעיל, אלא גם בלתי קריא. ויש הרבה דוגמאות כאלה.

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