|
| 1 | +/** |
| 2 | + * Uses the Bentley-McIlroy 3-way partition schema, chooses the partitioning element using Tukey's ninther, |
| 3 | + * and cuts off to insertion sort. |
| 4 | + * |
| 5 | + * The `QuickSortThreeWaysOptimized` class provides static methods for sorting an array using an optimized |
| 6 | + * version of quicksort. |
| 7 | + * |
| 8 | + */ |
| 9 | +public QuickSortThreeWaysOptimized { |
| 10 | + private static final int INSERTION_SORT_CUTOFF = 8; |
| 11 | + |
| 12 | + private static final int MEDIAN_OF_3_CUTOFF = 40; |
| 13 | + |
| 14 | + private QuickSortThreeWaysOptimized() {} |
| 15 | + |
| 16 | + public static void sort(Comparable[] a) { |
| 17 | + sort(a, 0, a.length - 1); |
| 18 | + } |
| 19 | + |
| 20 | + private static void sort(Comparable[] a, int low, int high) { |
| 21 | + int n = high - low + 1; |
| 22 | + if(n <= INSERTION_SORT_CUTOFF) { |
| 23 | + insertionSort(a, low, high); |
| 24 | + |
| 25 | + return; |
| 26 | + } else if(n <= MEDIAN_OF_3_CUTOFF) { |
| 27 | + int m = median3(a, low, low + n / 2, high); |
| 28 | + exchange(a, m, low); |
| 29 | + } else { |
| 30 | + int eps = n / 8; |
| 31 | + int mid = low + n / 2; |
| 32 | + int m1 = median3(a, low, low + eps, low + eps + eps); |
| 33 | + int m2 = median3(a, mid - eps, mid, mid + eps); |
| 34 | + int m3 = median3(a, high - eps * 2, high - eps, high); |
| 35 | + int ninther = median3(a, m1, m2, m3); |
| 36 | + exchange(a, ninther, low); |
| 37 | + } |
| 38 | + |
| 39 | + // Bentley-McIlroy 3-way partitioning |
| 40 | + int i = low, j = high + 1; |
| 41 | + int p = low, q = high + 1; |
| 42 | + Comparable v = a[low]; |
| 43 | + while(1) { |
| 44 | + while(less(a[++i], v)) { |
| 45 | + if(i == high) |
| 46 | + break; |
| 47 | + } |
| 48 | + while(less(v, a[--j])) |
| 49 | + if(j == low) |
| 50 | + break; |
| 51 | + |
| 52 | + // pointers cross |
| 53 | + if(i == j && eq(a[i], v)) |
| 54 | + exchange(a, ++p, i); |
| 55 | + if(i >= j) |
| 56 | + break; |
| 57 | + |
| 58 | + exchange(a, i, j); |
| 59 | + if(eq(a[i], v)) |
| 60 | + exchange(a, ++p, i); |
| 61 | + if(eq(a[j], v)) |
| 62 | + exchange(a, --q, j); |
| 63 | + } |
| 64 | + |
| 65 | + i = j + 1; |
| 66 | + for(int k = low; k <= p; k++) |
| 67 | + exchange(a, k, j--); |
| 68 | + for(int k = high; k >= q; k--) |
| 69 | + exchange(a, k, i++); |
| 70 | + |
| 71 | + sort(a, low, j); |
| 72 | + sort(a, i, high); |
| 73 | + } |
| 74 | + |
| 75 | + // sort from a[low] to a[high] using insertion sort |
| 76 | + private static void insertionSort(Comparable[] a, int low, int high) { |
| 77 | + for(int i = low; i <= high; i++) |
| 78 | + for(int j = i; j > low && less(a[j], a[j - 1]); j--) |
| 79 | + exchange(a, j, j - 1); |
| 80 | + } |
| 81 | + |
| 82 | + // return the index of the median element among a[i], ap[j], and a[k] |
| 83 | + private static int median3(Comparable[] a, int i, int j, int k) { |
| 84 | + return (less(a[i], a[j]) ? (less(a[j], a[k]) ? j : less(a[i], a[k]) ? k : i) : (less(a[k], a[j]) ? less(a[k], a[i]) ? k : i)); |
| 85 | + } |
| 86 | + |
| 87 | + // is v < w? |
| 88 | + private static boolean less(Comparable v, Comparable w) { |
| 89 | + if(v == w) |
| 90 | + return false; |
| 91 | + return v.compareTo(w) < 0; |
| 92 | + } |
| 93 | + |
| 94 | + private static boolean eq(Comparable v, Comparable w) { |
| 95 | + if(v == w) |
| 96 | + return true; |
| 97 | + return v.compareTo(w) == 0; |
| 98 | + } |
| 99 | + |
| 100 | + // exchange a[i] and a[j] |
| 101 | + private static void exchange(Object[] a, int i, int j) { |
| 102 | + Object swap = a[i]; |
| 103 | + a[i] = a[j]; |
| 104 | + a[j] = swap; |
| 105 | + } |
| 106 | + |
| 107 | + private static boolean isSorted(Comparable[] a) { |
| 108 | + for(int i = 1; i < a.length; i++) |
| 109 | + if(less(a[i], a[i - 1])) |
| 110 | + return false; |
| 111 | + |
| 112 | + return true; |
| 113 | + } |
| 114 | + |
| 115 | + // print |
| 116 | + private static void show(Comparable[] a) { |
| 117 | + for(int i = 0; i < a.length; i++) |
| 118 | + StdOut.println(a[i]); |
| 119 | + } |
| 120 | + |
| 121 | + // test |
| 122 | + public static void main(String[] args) { |
| 123 | + String[] a = StdIn.readAllStrings(); |
| 124 | + QuickSortThreeWaysOptimized.sort(a); |
| 125 | + assert isSorted(a); |
| 126 | + |
| 127 | + show(a); |
| 128 | + } |
| 129 | +} |
0 commit comments