1681 |
|
l+h, n-h, l, g, null).compute(); |
1682 |
|
} |
1683 |
|
else |
1684 |
< |
Arrays.sort(a, l, l+n, cmp); |
1684 |
> |
oquickSort(a, cmp, l, l+n-1); |
1685 |
|
} |
1686 |
|
} |
1687 |
|
|
1717 |
|
l+h, n-h, l, g, null).compute(); |
1718 |
|
} |
1719 |
|
else |
1720 |
< |
Arrays.sort(a, l, l+n); |
1720 |
> |
ocquickSort(a, l, l+n-1); |
1721 |
|
} |
1722 |
|
} |
1723 |
|
|
1754 |
|
l+h, n-h, l, g, null).compute(); |
1755 |
|
} |
1756 |
|
else |
1757 |
< |
Arrays.sort(a, l, l+n, cmp); |
1757 |
> |
dquickSort(a, cmp, l, l+n-1); |
1758 |
|
} |
1759 |
|
} |
1760 |
|
|
1828 |
|
l+h, n-h, l, g, null).compute(); |
1829 |
|
} |
1830 |
|
else |
1831 |
< |
Arrays.sort(a, l, l+n, cmp); |
1831 |
> |
lquickSort(a, cmp, l, l+n-1); |
1832 |
|
} |
1833 |
|
} |
1834 |
|
|
2301 |
|
} |
2302 |
|
} |
2303 |
|
} |
2304 |
+ |
|
2305 |
+ |
/** Cutoff for when to use insertion-sort instead of quicksort */ |
2306 |
+ |
static final int INSERTION_SORT_THRESHOLD = 8; |
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 && (c = cmp.compare(pivot, a[left])) >= 0){ |
2345 |
+ |
if (c != 0) |
2346 |
+ |
sameLefts = false; |
2347 |
+ |
++left; |
2348 |
+ |
} |
2349 |
+ |
if (left < right) { |
2350 |
+ |
Object t = a[left]; a[left] = a[right]; a[right] = t; |
2351 |
+ |
--right; |
2352 |
+ |
} |
2353 |
+ |
else break; |
2354 |
+ |
} |
2355 |
+ |
|
2356 |
+ |
if (sameLefts && right == hi - 1) |
2357 |
+ |
return; |
2358 |
+ |
if (left - lo <= hi - right) { |
2359 |
+ |
oquickSort(a, cmp, lo, left); |
2360 |
+ |
lo = left + 1; |
2361 |
+ |
} |
2362 |
+ |
else { |
2363 |
+ |
oquickSort(a, cmp, right, hi); |
2364 |
+ |
hi = left; |
2365 |
+ |
} |
2366 |
+ |
} |
2367 |
+ |
} |
2368 |
+ |
|
2369 |
+ |
static void ocquickSort(Comparable[] a, int lo, int hi) { |
2370 |
+ |
for (;;) { |
2371 |
+ |
if (hi - lo <= INSERTION_SORT_THRESHOLD) { |
2372 |
+ |
for (int i = lo + 1; i <= hi; i++) { |
2373 |
+ |
Comparable t = a[i]; |
2374 |
+ |
int j = i - 1; |
2375 |
+ |
while (j >= lo && t.compareTo(a[j]) < 0) { |
2376 |
+ |
a[j+1] = a[j]; |
2377 |
+ |
--j; |
2378 |
+ |
} |
2379 |
+ |
a[j+1] = t; |
2380 |
+ |
} |
2381 |
+ |
return; |
2382 |
+ |
} |
2383 |
+ |
|
2384 |
+ |
int mid = (lo + hi) >>> 1; |
2385 |
+ |
if (a[lo].compareTo(a[mid]) > 0) { |
2386 |
+ |
Comparable t = a[lo]; a[lo] = a[mid]; a[mid] = t; |
2387 |
+ |
} |
2388 |
+ |
if (a[mid].compareTo(a[hi]) > 0) { |
2389 |
+ |
Comparable t = a[mid]; a[mid] = a[hi]; a[hi] = t; |
2390 |
+ |
if (a[lo].compareTo(a[mid]) > 0) { |
2391 |
+ |
Comparable u = a[lo]; a[lo] = a[mid]; a[mid] = u; |
2392 |
+ |
} |
2393 |
+ |
} |
2394 |
+ |
Comparable pivot = a[mid]; |
2395 |
+ |
int left = lo+1; |
2396 |
+ |
int right = hi-1; |
2397 |
+ |
boolean sameLefts = true; |
2398 |
+ |
for (;;) { |
2399 |
+ |
while (pivot.compareTo(a[right]) < 0) |
2400 |
+ |
--right; |
2401 |
+ |
int c; |
2402 |
+ |
while (left < right && (c = pivot.compareTo(a[left])) >= 0) { |
2403 |
+ |
if (c != 0) |
2404 |
+ |
sameLefts = false; |
2405 |
+ |
++left; |
2406 |
+ |
} |
2407 |
+ |
if (left < right) { |
2408 |
+ |
Comparable t = a[left]; a[left] = a[right]; a[right] = t; |
2409 |
+ |
--right; |
2410 |
+ |
} |
2411 |
+ |
else break; |
2412 |
+ |
} |
2413 |
+ |
|
2414 |
+ |
if (sameLefts && right == hi - 1) |
2415 |
+ |
return; |
2416 |
+ |
if (left - lo <= hi - right) { |
2417 |
+ |
ocquickSort(a, lo, left); |
2418 |
+ |
lo = left + 1; |
2419 |
+ |
} |
2420 |
+ |
else { |
2421 |
+ |
ocquickSort(a, right, hi); |
2422 |
+ |
hi = left; |
2423 |
+ |
} |
2424 |
+ |
} |
2425 |
+ |
} |
2426 |
+ |
|
2427 |
+ |
|
2428 |
+ |
static void dquickSort(double[] a, DoubleComparator cmp, int lo, int hi) { |
2429 |
+ |
for (;;) { |
2430 |
+ |
if (hi - lo <= INSERTION_SORT_THRESHOLD) { |
2431 |
+ |
for (int i = lo + 1; i <= hi; i++) { |
2432 |
+ |
double t = a[i]; |
2433 |
+ |
int j = i - 1; |
2434 |
+ |
while (j >= lo && cmp.compare(t, a[j]) < 0) { |
2435 |
+ |
a[j+1] = a[j]; |
2436 |
+ |
--j; |
2437 |
+ |
} |
2438 |
+ |
a[j+1] = t; |
2439 |
+ |
} |
2440 |
+ |
return; |
2441 |
+ |
} |
2442 |
+ |
|
2443 |
+ |
int mid = (lo + hi) >>> 1; |
2444 |
+ |
if (cmp.compare(a[lo], a[mid]) > 0) { |
2445 |
+ |
double t = a[lo]; a[lo] = a[mid]; a[mid] = t; |
2446 |
+ |
} |
2447 |
+ |
if (cmp.compare(a[mid], a[hi]) > 0) { |
2448 |
+ |
double t = a[mid]; a[mid] = a[hi]; a[hi] = t; |
2449 |
+ |
if (cmp.compare(a[lo], a[mid]) > 0) { |
2450 |
+ |
double u = a[lo]; a[lo] = a[mid]; a[mid] = u; |
2451 |
+ |
} |
2452 |
+ |
} |
2453 |
+ |
|
2454 |
+ |
double pivot = a[mid]; |
2455 |
+ |
int left = lo+1; |
2456 |
+ |
int right = hi-1; |
2457 |
+ |
boolean sameLefts = true; |
2458 |
+ |
for (;;) { |
2459 |
+ |
while (cmp.compare(pivot, a[right]) < 0) |
2460 |
+ |
--right; |
2461 |
+ |
int c; |
2462 |
+ |
while (left < right && (c = cmp.compare(pivot, a[left])) >= 0){ |
2463 |
+ |
if (c != 0) |
2464 |
+ |
sameLefts = false; |
2465 |
+ |
++left; |
2466 |
+ |
} |
2467 |
+ |
if (left < right) { |
2468 |
+ |
double t = a[left]; a[left] = a[right]; a[right] = t; |
2469 |
+ |
--right; |
2470 |
+ |
} |
2471 |
+ |
else break; |
2472 |
+ |
} |
2473 |
+ |
|
2474 |
+ |
if (sameLefts && right == hi - 1) |
2475 |
+ |
return; |
2476 |
+ |
if (left - lo <= hi - right) { |
2477 |
+ |
dquickSort(a, cmp, lo, left); |
2478 |
+ |
lo = left + 1; |
2479 |
+ |
} |
2480 |
+ |
else { |
2481 |
+ |
dquickSort(a, cmp, right, hi); |
2482 |
+ |
hi = left; |
2483 |
+ |
} |
2484 |
+ |
} |
2485 |
+ |
} |
2486 |
+ |
|
2487 |
+ |
static void lquickSort(long[] a, LongComparator cmp, int lo, int hi) { |
2488 |
+ |
for (;;) { |
2489 |
+ |
if (hi - lo <= INSERTION_SORT_THRESHOLD) { |
2490 |
+ |
for (int i = lo + 1; i <= hi; i++) { |
2491 |
+ |
long t = a[i]; |
2492 |
+ |
int j = i - 1; |
2493 |
+ |
while (j >= lo && cmp.compare(t, a[j]) < 0) { |
2494 |
+ |
a[j+1] = a[j]; |
2495 |
+ |
--j; |
2496 |
+ |
} |
2497 |
+ |
a[j+1] = t; |
2498 |
+ |
} |
2499 |
+ |
return; |
2500 |
+ |
} |
2501 |
+ |
|
2502 |
+ |
int mid = (lo + hi) >>> 1; |
2503 |
+ |
if (cmp.compare(a[lo], a[mid]) > 0) { |
2504 |
+ |
long t = a[lo]; a[lo] = a[mid]; a[mid] = t; |
2505 |
+ |
} |
2506 |
+ |
if (cmp.compare(a[mid], a[hi]) > 0) { |
2507 |
+ |
long t = a[mid]; a[mid] = a[hi]; a[hi] = t; |
2508 |
+ |
if (cmp.compare(a[lo], a[mid]) > 0) { |
2509 |
+ |
long u = a[lo]; a[lo] = a[mid]; a[mid] = u; |
2510 |
+ |
} |
2511 |
+ |
} |
2512 |
+ |
|
2513 |
+ |
long pivot = a[mid]; |
2514 |
+ |
int left = lo+1; |
2515 |
+ |
int right = hi-1; |
2516 |
+ |
boolean sameLefts = true; |
2517 |
+ |
for (;;) { |
2518 |
+ |
while (cmp.compare(pivot, a[right]) < 0) |
2519 |
+ |
--right; |
2520 |
+ |
int c; |
2521 |
+ |
while (left < right && (c = cmp.compare(pivot, a[left])) >= 0){ |
2522 |
+ |
if (c != 0) |
2523 |
+ |
sameLefts = false; |
2524 |
+ |
++left; |
2525 |
+ |
} |
2526 |
+ |
if (left < right) { |
2527 |
+ |
long t = a[left]; a[left] = a[right]; a[right] = t; |
2528 |
+ |
--right; |
2529 |
+ |
} |
2530 |
+ |
else break; |
2531 |
+ |
} |
2532 |
+ |
|
2533 |
+ |
if (sameLefts && right == hi - 1) |
2534 |
+ |
return; |
2535 |
+ |
if (left - lo <= hi - right) { |
2536 |
+ |
lquickSort(a, cmp, lo, left); |
2537 |
+ |
lo = left + 1; |
2538 |
+ |
} |
2539 |
+ |
else { |
2540 |
+ |
lquickSort(a, cmp, right, hi); |
2541 |
+ |
hi = left; |
2542 |
+ |
} |
2543 |
+ |
} |
2544 |
+ |
} |
2545 |
|
|
2546 |
|
/** |
2547 |
|
* Cumulative scan |