equal
deleted
inserted
replaced
34 * |
34 * |
35 * @author Vladimir Yaroslavskiy |
35 * @author Vladimir Yaroslavskiy |
36 * @author Jon Bentley |
36 * @author Jon Bentley |
37 * @author Josh Bloch |
37 * @author Josh Bloch |
38 * |
38 * |
39 * @version 2009.10.22 m765.827.v4 |
39 * @version 2009.10.29 m765.827.v5 |
40 */ |
40 */ |
41 final class DualPivotQuicksort { |
41 final class DualPivotQuicksort { |
42 |
42 |
43 // Suppresses default constructor, ensuring non-instantiability. |
43 // Suppresses default constructor, ensuring non-instantiability. |
44 private DualPivotQuicksort() {} |
44 private DualPivotQuicksort() {} |
471 if (a[k] == pivot2) { |
471 if (a[k] == pivot2) { |
472 a[k] = a[great]; |
472 a[k] = a[great]; |
473 a[great--] = pivot2; |
473 a[great--] = pivot2; |
474 } |
474 } |
475 } |
475 } |
476 } else { // Use Dual-Pivot Quicksort on large arrays |
476 } |
477 dualPivotQuicksort(a, left, right); |
477 |
478 } |
478 // Sort center part recursively, excluding known pivot values |
|
479 sort(a, less, great); |
479 } |
480 } |
480 |
481 |
481 /** The number of distinct short values */ |
482 /** The number of distinct short values */ |
482 private static final int NUM_SHORT_VALUES = 1 << 16; |
483 private static final int NUM_SHORT_VALUES = 1 << 16; |
483 |
484 |
505 int[] count = new int[NUM_SHORT_VALUES]; |
506 int[] count = new int[NUM_SHORT_VALUES]; |
506 |
507 |
507 for (int i = left; i <= right; i++) { |
508 for (int i = left; i <= right; i++) { |
508 count[a[i] - Short.MIN_VALUE]++; |
509 count[a[i] - Short.MIN_VALUE]++; |
509 } |
510 } |
510 for (int i = 0, k = left; i < count.length && k < right; i++) { |
511 for (int i = 0, k = left; i < count.length && k <= right; i++) { |
511 short value = (short) (i + Short.MIN_VALUE); |
512 short value = (short) (i + Short.MIN_VALUE); |
512 |
513 |
513 for (int s = count[i]; s > 0; s--) { |
514 for (int s = count[i]; s > 0; s--) { |
514 a[k++] = value; |
515 a[k++] = value; |
515 } |
516 } |
721 a[j + 1] = a[j]; |
722 a[j + 1] = a[j]; |
722 } |
723 } |
723 a[j + 1] = ak; |
724 a[j + 1] = ak; |
724 } |
725 } |
725 } else if (right - left + 1 > COUNTING_SORT_THRESHOLD_FOR_BYTE) { |
726 } else if (right - left + 1 > COUNTING_SORT_THRESHOLD_FOR_BYTE) { |
726 // Use counting sort on large arrays |
727 // Use counting sort on huge arrays |
727 int[] count = new int[NUM_BYTE_VALUES]; |
728 int[] count = new int[NUM_BYTE_VALUES]; |
728 |
729 |
729 for (int i = left; i <= right; i++) { |
730 for (int i = left; i <= right; i++) { |
730 count[a[i] - Byte.MIN_VALUE]++; |
731 count[a[i] - Byte.MIN_VALUE]++; |
731 } |
732 } |
732 for (int i = 0, k = left; i < count.length && k < right; i++) { |
733 for (int i = 0, k = left; i < count.length && k <= right; i++) { |
733 byte value = (byte) (i + Byte.MIN_VALUE); |
734 byte value = (byte) (i + Byte.MIN_VALUE); |
734 |
735 |
735 for (int s = count[i]; s > 0; s--) { |
736 for (int s = count[i]; s > 0; s--) { |
736 a[k++] = value; |
737 a[k++] = value; |
737 } |
738 } |
949 int[] count = new int[NUM_CHAR_VALUES]; |
950 int[] count = new int[NUM_CHAR_VALUES]; |
950 |
951 |
951 for (int i = left; i <= right; i++) { |
952 for (int i = left; i <= right; i++) { |
952 count[a[i]]++; |
953 count[a[i]]++; |
953 } |
954 } |
954 for (int i = 0, k = left; i < count.length && k < right; i++) { |
955 for (int i = 0, k = left; i < count.length && k <= right; i++) { |
955 for (int s = count[i]; s > 0; s--) { |
956 for (int s = count[i]; s > 0; s--) { |
956 a[k++] = (char) i; |
957 a[k++] = (char) i; |
957 } |
958 } |
958 } |
959 } |
959 } else { // Use Dual-Pivot Quicksort on large arrays |
960 } else { // Use Dual-Pivot Quicksort on large arrays |