ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/extra166y/PAS.java

Comparing jsr166/src/extra166y/PAS.java (file contents):
Revision 1.12 by jsr166, Fri Oct 22 05:18:30 2010 UTC vs.
Revision 1.13 by dl, Thu Nov 25 12:40:16 2010 UTC

#	Line 1681 | Line 1681 | class PAS {
1681		l+h, n-h, l, g, null).compute();
1682		}
1683		else
1684	<	oquickSort(a, cmp, l, l+n-1);
1684	>	Arrays.sort(a, l, l+n, cmp);
1685		}
1686		}
1687
#	Line 1717 | Line 1717 | class PAS {
1717		l+h, n-h, l, g, null).compute();
1718		}
1719		else
1720	<	ocquickSort(a, l, l+n-1);
1720	>	Arrays.sort(a, l, l+n);
1721		}
1722		}
1723
#	Line 2307 | Line 2307 | class PAS {
2307
2308		// versions of quicksort with comparators
2309
2310	–	static void oquickSort(Object[] a, Comparator cmp, int lo, int hi) {
2311	–	for (;;) {
2312	–	if (hi - lo <= INSERTION_SORT_THRESHOLD) {
2313	–	for (int i = lo + 1; i <= hi; i++) {
2314	–	Object t = a[i];
2315	–	int j = i - 1;
2316	–	while (j >= lo && cmp.compare(t, a[j]) < 0) {
2317	–	a[j+1] = a[j];
2318	–	--j;
2319	–	}
2320	–	a[j+1] = t;
2321	–	}
2322	–	return;
2323	–	}
2324	–
2325	–	int mid = (lo + hi) >>> 1;
2326	–	if (cmp.compare(a[lo], a[mid]) > 0) {
2327	–	Object t = a[lo]; a[lo] = a[mid]; a[mid] = t;
2328	–	}
2329	–	if (cmp.compare(a[mid], a[hi]) > 0) {
2330	–	Object t = a[mid]; a[mid] = a[hi]; a[hi] = t;
2331	–	if (cmp.compare(a[lo], a[mid]) > 0) {
2332	–	Object u = a[lo]; a[lo] = a[mid]; a[mid] = u;
2333	–	}
2334	–	}
2335	–
2336	–	Object pivot = a[mid];
2337	–	int left = lo+1;
2338	–	int right = hi-1;
2339	–	boolean sameLefts = true;
2340	–	for (;;) {
2341	–	while (cmp.compare(pivot, a[right]) < 0)
2342	–	--right;
2343	–	int c;
2344	–	while (left < right &&
2345	–	(c = cmp.compare(pivot, a[left])) >= 0) {
2346	–	if (c != 0)
2347	–	sameLefts = false;
2348	–	++left;
2349	–	}
2350	–	if (left < right) {
2351	–	Object t = a[left]; a[left] = a[right]; a[right] = t;
2352	–	--right;
2353	–	}
2354	–	else break;
2355	–	}
2356	–
2357	–	if (sameLefts && right == hi - 1)
2358	–	return;
2359	–	if (left - lo <= hi - right) {
2360	–	oquickSort(a, cmp, lo, left);
2361	–	lo = left + 1;
2362	–	}
2363	–	else {
2364	–	oquickSort(a, cmp, right, hi);
2365	–	hi = left;
2366	–	}
2367	–	}
2368	–	}
2369	–
2370	–	static void ocquickSort(Comparable[] a, int lo, int hi) {
2371	–	for (;;) {
2372	–	if (hi - lo <= INSERTION_SORT_THRESHOLD) {
2373	–	for (int i = lo + 1; i <= hi; i++) {
2374	–	Comparable t = a[i];
2375	–	int j = i - 1;
2376	–	while (j >= lo && t.compareTo(a[j]) < 0) {
2377	–	a[j+1] = a[j];
2378	–	--j;
2379	–	}
2380	–	a[j+1] = t;
2381	–	}
2382	–	return;
2383	–	}
2384	–
2385	–	int mid = (lo + hi) >>> 1;
2386	–	if (a[lo].compareTo(a[mid]) > 0) {
2387	–	Comparable t = a[lo]; a[lo] = a[mid]; a[mid] = t;
2388	–	}
2389	–	if (a[mid].compareTo(a[hi]) > 0) {
2390	–	Comparable t = a[mid]; a[mid] = a[hi]; a[hi] = t;
2391	–	if (a[lo].compareTo(a[mid]) > 0) {
2392	–	Comparable u = a[lo]; a[lo] = a[mid]; a[mid] = u;
2393	–	}
2394	–	}
2395	–	Comparable pivot = a[mid];
2396	–	int left = lo+1;
2397	–	int right = hi-1;
2398	–	boolean sameLefts = true;
2399	–	for (;;) {
2400	–	while (pivot.compareTo(a[right]) < 0)
2401	–	--right;
2402	–	int c;
2403	–	while (left < right && (c = pivot.compareTo(a[left])) >= 0) {
2404	–	if (c != 0)
2405	–	sameLefts = false;
2406	–	++left;
2407	–	}
2408	–	if (left < right) {
2409	–	Comparable t = a[left]; a[left] = a[right]; a[right] = t;
2410	–	--right;
2411	–	}
2412	–	else break;
2413	–	}
2414	–
2415	–	if (sameLefts && right == hi - 1)
2416	–	return;
2417	–	if (left - lo <= hi - right) {
2418	–	ocquickSort(a, lo, left);
2419	–	lo = left + 1;
2420	–	}
2421	–	else {
2422	–	ocquickSort(a, right, hi);
2423	–	hi = left;
2424	–	}
2425	–	}
2426	–	}
2427	–
2310
2311		static void dquickSort(double[] a, DoubleComparator cmp, int lo, int hi) {
2312		for (;;) {

Diff Legend

–	Removed lines
+	Added lines
<	Changed lines
>	Changed lines