001// Exercise 2.3.22 (Solution published at http://algs4.cs.princeton.edu/) 002package algs23; 003import stdlib.*; 004/* *********************************************************************** 005 * Compilation: javac QuickX.java 006 * Execution: java QuickX N 007 * 008 * Uses the Bentley-McIlroy 3-way partitioning scheme, 009 * chooses the partitioning element using Tukey's ninther, 010 * and cuts off to insertion sort. 011 * 012 * Reference: Engineering a Sort Function by Jon L. Bentley 013 * and M. Douglas McIlroy. Softwae-Practice and Experience, 014 * Vol. 23 (11), 1249-1265 (November 1993). 015 * 016 *************************************************************************/ 017 018public class XQuickX { 019 private static final int CUTOFF = 8; // cutoff to insertion sort, must be >= 1 020 021 public static <T extends Comparable<? super T>> void sort(T[] a) { 022 sort(a, 0, a.length - 1); 023 } 024 025 private static <T extends Comparable<? super T>> void sort(T[] a, int lo, int hi) { 026 int N = hi - lo + 1; 027 028 // cutoff to insertion sort 029 if (N <= CUTOFF) { 030 insertionSort(a, lo, hi); 031 return; 032 } 033 034 // use median-of-3 as partitioning element 035 else if (N <= 40) { 036 int m = median3(a, lo, lo + N/2, hi); 037 exch(a, m, lo); 038 } 039 040 // use Tukey ninther as partitioning element 041 else { 042 int eps = N/8; 043 int mid = lo + N/2; 044 int m1 = median3(a, lo, lo + eps, lo + eps + eps); 045 int m2 = median3(a, mid - eps, mid, mid + eps); 046 int m3 = median3(a, hi - eps - eps, hi - eps, hi); 047 int ninther = median3(a, m1, m2, m3); 048 exch(a, ninther, lo); 049 } 050 051 // Bentley-McIlroy 3-way partitioning 052 int i = lo, j = hi+1; 053 int p = lo, q = hi+1; 054 while (true) { 055 T v = a[lo]; 056 while (less(a[++i], v)) 057 if (i == hi) break; 058 while (less(v, a[--j])) 059 if (j == lo) break; 060 if (i >= j) break; 061 exch(a, i, j); 062 if (eq(a[i], v)) exch(a, ++p, i); 063 if (eq(a[j], v)) exch(a, --q, j); 064 } 065 exch(a, lo, j); 066 067 i = j + 1; 068 j = j - 1; 069 for (int k = lo+1; k <= p; k++) exch(a, k, j--); 070 for (int k = hi ; k >= q; k--) exch(a, k, i++); 071 072 sort(a, lo, j); 073 sort(a, i, hi); 074 } 075 076 077 // sort from a[lo] to a[hi] using insertion sort 078 private static <T extends Comparable<? super T>> void insertionSort(T[] a, int lo, int hi) { 079 for (int i = lo; i <= hi; i++) 080 for (int j = i; j > lo && less(a[j], a[j-1]); j--) 081 exch(a, j, j-1); 082 } 083 084 085 // return the index of the median element among a[i], a[j], and a[k] 086 private static <T extends Comparable<? super T>> int median3(T[] a, int i, int j, int k) { 087 return (less(a[i], a[j]) ? 088 (less(a[j], a[k]) ? j : less(a[i], a[k]) ? k : i) : 089 (less(a[k], a[j]) ? j : less(a[k], a[i]) ? k : i)); 090 } 091 092 /* ********************************************************************* 093 * Helper sorting functions 094 ***********************************************************************/ 095 096 // is v < w ? 097 private static <T extends Comparable<? super T>> boolean less(T v, T w) { 098 if (COUNT_OPS) DoublingTest.incOps (); 099 return (v.compareTo(w) < 0); 100 } 101 102 // does v == w ? 103 private static <T extends Comparable<? super T>> boolean eq(T v, T w) { 104 if (COUNT_OPS) DoublingTest.incOps (); 105 return (v.compareTo(w) == 0); 106 } 107 108 // exchange a[i] and a[j] 109 private static void exch(Object[] a, int i, int j) { 110 Object swap = a[i]; 111 a[i] = a[j]; 112 a[j] = swap; 113 } 114 115 116 /* ********************************************************************* 117 * Check if array is sorted - useful for debugging 118 ***********************************************************************/ 119 private static <T extends Comparable<? super T>> boolean isSorted(T[] a) { 120 for (int i = 1; i < a.length; i++) 121 if (less(a[i], a[i-1])) return false; 122 return true; 123 } 124 125 126 // test code 127 private static boolean COUNT_OPS = false; 128 public static void main(String[] args) { 129 130 StdIn.fromFile ("data/words3.txt"); 131 132 String[] a = StdIn.readAllStrings(); 133 sort(a); 134 135 // display results 136 for (int i = 0; i < a.length; i++) { 137 StdOut.println(a[i]); 138 } 139 StdOut.println("isSorted = " + isSorted(a)); 140 141 COUNT_OPS = true; 142 DoublingTest.run (20000, 5, N -> ArrayGenerator.integerRandomUnique (N), (Integer[] x) -> sort (x)); 143 DoublingTest.run (20000, 5, N -> ArrayGenerator.integerRandom (N, 2), (Integer[] x) -> sort (x)); 144 DoublingTest.run (20000, 5, N -> ArrayGenerator.integerPartiallySortedUnique (N), (Integer[] x) -> sort (x)); 145 } 146 147}