בניתוח קוד המקור של פרויקטי 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;
}
GO TO FULL VERSION