نحوه صحیح مرتب سازی در جاوا

با تجزیه و تحلیل کد منبع بسیاری از پروژه های منبع باز جاوا، متوجه شدم که اکثر توسعه دهندگان مرتب سازی را تنها به دو روش مختلف اجرا می کنند. یکی از آنها بر اساس استفاده از متد 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;
		}